Nonconvex Optimization Tools for Large-Scale Matrix and Tensor Decomposition with Structured Factors

Xiao Fu, Nico Vervliet, Lieven De Lathauwer, Kejun Huang, Nicolas Gillis

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 algorithmic procedures for a small set of problems, e.g., nonnegativity or sparsity-constrained factorization, we take a 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 block coordinate descent (BCD)-based methods. We expect that the article will have educational value in the field of structured factorization and hope to stimulate more research in this important and exciting direction.

Introduction

In fields ranging from hyperspectral imaging to social network analysis, data is increasingly represented as high-dimensional arrays, or tensors. To extract actionable insights from this "big data," researchers utilize Low-Rank Decomposition Models (LRDMs) to identify latent factors—the hidden variables driving observed phenomena. However, standard mathematical decompositions often yield results that are physically impossible, such as negative chemical concentrations in spectroscopy or illogical community structures in social networks.

To address this, physical "structure" must be imposed on the factors, such as nonnegativity, sparsity, or smoothness. While these constraints make the models more realistic, they transform the decomposition into a challenging NP-hard nonconvex optimization problem. As datasets scale to the terabyte level, traditional batch algorithms become computationally prohibitive, necessitating new algorithmic frameworks that can handle both structure and scale.

Structured decomposition in hyperspectral imaging, where a data cube is decomposed into physically meaningful spectral signatures and abundance maps.

Algorithmic Frameworks for Structured Decomposition

The authors categorize modern solutions into three primary algorithmic families, each offering unique trade-offs between computational complexity and convergence speed.

1. Block Coordinate Descent (BCD)

BCD is the traditional "workhorse" of the field, updating one factor matrix at a time while keeping others fixed. The paper highlights Inexact BCD, where subproblems are only partially solved to save computational time, and Extrapolation (Nesterov-style acceleration), which can drastically speed up convergence in multi-block settings.

2. Second-Order Gauss-Newton Methods

These methods exploit the "curvature" of the optimization landscape. While more complex to implement, they are significantly faster at converging near the optimal solution and are more robust against "swamps"—flat regions where first-order methods often stall. A key innovation discussed is a Parameterization trick that allows these solvers to handle constraints like nonnegativity within an unconstrained optimization framework.

3. Stochastic Optimization

For massive datasets, stochastic approaches sample random entries, subtensors, or "fibers" (vectors along one dimension). The paper specifically highlights AdaCPD, which employs adaptive step sizes—similar to techniques used in deep learning—to eliminate the need for manual hyperparameter tuning, a common bottleneck in large-scale optimization.

Key Insights and Empirical Results

A central insight of this tutorial is that structure is a solution, not a burden. Constraints often make the problem "well-posed," ensuring the uniqueness of the decomposition, which is essential for identifying specific signals in a mixture.

Empirical benchmarks demonstrate the efficiency of these frameworks:

  • Acceleration: Extrapolation techniques provide massive speedups for BCD, reaching lower error rates in fewer iterations.
  • Gauss-Newton Superiority: In scenarios with highly correlated factors, the Gauss-Newton approach converged in 0.6 seconds, while the standard Alternating Least Squares (ALS) took 5.5 seconds—a nearly 10x improvement.
  • Stochastic Efficiency: Stochastic "Fiber Sampling" (AdaCPD) achieves high estimation accuracy using significantly fewer operations than traditional batch algorithms.
Convergence comparison between Gauss-Newton (GN) and Alternating Least Squares (ALS), showing the significant speedup and precision of second-order methods.

Conclusion

The paper bridges the gap between classical algebraic tensor theory and modern machine learning optimization. While challenges remain—such as proving convergence for stochastic methods with nonsmooth constraints—the unified nonconvex optimization perspective provided here offers a robust roadmap for handling structured large-scale data decomposition. We expect these tools to become increasingly vital as data dimensionality continues to grow across engineering and scientific disciplines.

Summary updated

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.
BibTeX
@inproceedings{fu2020nonconvex,
  author = {Xiao Fu and Nico Vervliet and Lieven De Lathauwer and Kejun Huang and Nicolas Gillis},
  title = {{Nonconvex Optimization Tools for Large-Scale Matrix and Tensor Decomposition with Structured Factors}},
  booktitle = {Lirias},
  year = {2020},
  doi = {10.1109/msp.2020.3003544},
}
Figure