Sparse Matrix Factorization (SMF) is a fundamental task in signal processing and machine learning, essential for applications ranging from dictionary learning to the acceleration of deep neural networks. Traditionally, SMF is approached as a two-stage process: first, identifying the optimal support (the positions of non-zero entries), and second, determining the optimal values for those entries. While the first stage is a well-known combinatorial challenge, the second stage—Fixed Support Matrix Factorization (FSMF)—has often been overlooked as the "easy" part of the problem. This paper challenges that assumption, providing a rigorous analysis of the complexity and optimization landscape of FSMF.
The Complexity of Fixed Support
The authors investigate whether knowing the support pattern is sufficient to make the optimization problem tractable. They prove that FSMF is generally NP-hard by reducing it from the "Matrix Completion with Noise" problem. This hardness stems from the non-convex coupling between the matrix factors, even when the sparsity pattern is pre-defined.
Identifying Tractable Structures
Despite the general hardness, the paper identifies specific families of supports that are computationally efficient to solve. These include structures where rank-one contributions are disjoint or follow specific hierarchical patterns, such as those found in Hierarchically Off-Diagonal Low-Rank (HODLR) matrices and "butterfly" transforms (common in Fast Fourier Transforms).
For these tractable families, the authors propose a dedicated SVD-based algorithm. This approach decomposes the global optimization problem into a sequence of smaller, independent Singular Value Decompositions, ensuring that a global minimum can be reached in polynomial time.
The Optimization Landscape: Spurious Valleys
A key contribution of this work is the analysis of the optimization landscape. The authors introduce the concept of "path-connectivity" to identify spurious valleys—suboptimal regions where local search methods like Gradient Descent can become trapped.
One of the paper's most striking insights is that tractability does not guarantee a benign landscape. For example, while LU decomposition is a form of FSMF that is solvable in polynomial time by specialized algorithms, its standard optimization landscape contains spurious objects that can cause first-order optimizers to diverge or fail. However, for the hierarchical and butterfly supports identified by the authors, they prove that the landscape is free of such trapping valleys.
Key Results and Numerical Performance
The theoretical findings are supported by numerical experiments on synthetic benchmarks, including Hadamard and HODLR matrices.
- Efficiency: On Hadamard matrices up to size $1024 \times 1024$, the proposed SVD-based algorithm reached a precision of $10^{-10}$ significantly faster than standard optimizers like Adam or Gradient Descent.
- Robustness: Unlike first-order methods, the SVD-based approach is hyperparameter-free, requiring no learning rate tuning.
- Convergence: The experiments demonstrate that while standard heuristics can struggle with local minima, the proposed method consistently finds the global optimum for structured supports.
Limitations and Future Work
While the paper provides a breakthrough in understanding two-factor FSMF ($N=2$), several avenues for future research remain. The current analysis primarily addresses the product of two factors; extending these landscape guarantees to deeper factorizations ($N > 2$) is a natural next step. Additionally, while this work assumes the support is known, real-world applications often require learning the support and values simultaneously. Integrating these landscape insights into support-finding heuristics could lead to more robust and efficient SMF algorithms.
Summary updated