Computing Large-Scale Matrix and Tensor Decomposition with Structured Factors: A Unified Nonconvex Optimization Perspective

Abstract

The proposed article aims at offering a comprehensive tutorial for the computational aspects of structured matrix and tensor factorization. Unlike existing tutorials that mainly focus on {\it algorithmic procedures} for a small set of problems, e.g., nonnegativity or sparsity-constrained factorization, we take a {\it top-down} approach: we start with general optimization theory (e.g., inexact and accelerated block coordinate descent, stochastic optimization, and Gauss-Newton methods) that covers a wide range of factorization problems with diverse constraints and regularization terms of engineering interest. Then, we go `under the hood' to showcase specific algorithm design under these introduced principles. We pay a particular attention to recent algorithmic developments in structured tensor and matrix factorization (e.g., random sketching and adaptive step size based stochastic optimization and structure-exploiting second-order algorithms), which are the state of the art---yet much less touched upon in the literature compared to {\it block coordinate descent} (BCD)-based methods. We expect that the article to have an educational values in the field of structured factorization and hope to stimulate more research in this important and exciting direction.

Final Version; to appear in IEEE Signal Processing Magazine; title revised to comply with the journal's rule

References in corpus (17)

• Tensor Decomposition for Signal Processing and Machine Learning
• Tensor Decompositions for Signal Processing Applications From Two-way to Multiway Component Analysis
• Fast Fusion of Multi-Band Images Based on Solving a Sylvester Equation
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview
• The Why and How of Nonnegative Matrix Factorization
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Nonnegative Matrix Factorization for Signal and Data Analytics: Identifiability, Algorithms, and Applications
• A Flexible and Efficient Algorithmic Framework for Constrained Matrix and Tensor Factorization
• A Practical Randomized CP Tensor Decomposition
• Canonical polyadic decomposition of third-order tensors: reduction to generalized eigenvalue decomposition
• Robust Volume Minimization-Based Matrix Factorization for Remote Sensing and Document Clustering
• Spectrum Cartography via Coupled Block-Term Tensor Decomposition
• Joint Tensor Factorization and Outlying Slab Suppression with Applications
• Tensor Completion from Regular Sub-Nyquist Samples
• On the Complexity of Robust PCA and ${\ell }_1$-norm Low-Rank Matrix Approximation
• Pencil-based algorithms for tensor rank decomposition are not stable
• Accelerating Block Coordinate Descent for Nonnegative Tensor Factorization

Cited by in corpus (10)

• Deep Spectrum Cartography: Completing Radio Map Tensors Using Learned Neural Models
• Simplex-Structured Matrix Factorization: Sparsity-based Identifiability and Provably Correct Algorithms
• Stochastic Mirror Descent for Low-Rank Tensor Decomposition Under Non-Euclidean Losses
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Personalized Coupled Tensor Decomposition for Multimodal Data Fusion: Uniqueness and Algorithms
• Uncovering migration systems through spatio-temporal tensor co-clustering
• Dual Simplex Volume Maximization for Simplex-Structured Matrix Factorization
• Representation Theorem for Matrix Product States
• Multi-version Tensor Completion for Time-delayed Spatio-temporal Data
• Crowdsourcing via Annotator Co-occurrence Imputation and Provable Symmetric Nonnegative Matrix Factorization