Spurious Valleys, Spurious Minima and NP-hardness of Sparse Matrix Factorization With Fixed Support

Quoc-Tung Le, Elisa Riccietti, Rémi Gribonval

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.

Visualizing the FSMF problem: (a) shows a standard low-rank approximation where factors are dense, while (b) illustrates the FSMF setting where factors must adhere to a specific, fixed support pattern.

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.
Numerical results showing the convergence of the proposed algorithm. Plot (c) highlights the rapid, stable decrease in factor error (log10 scale) over 5000 iterations.

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

Abstract

The problem of approximating a dense matrix by a product of sparse factors is a fundamental problem for many signal processing and machine learning tasks. It can be decomposed into two subproblems: finding the position of the non-zero coefficients in the sparse factors, and determining their values. While the first step is usually seen as the most challenging one due to its combinatorial nature, this paper focuses on the second step, referred to as sparse matrix approximation with fixed support. First, we show its NP-hardness, while also presenting a nontrivial family of supports making the problem practically tractable with a dedicated algorithm. Then, we investigate the landscape of its natural optimization formulation, proving the absence of spurious local valleys and spurious local minima, whose presence could prevent local optimization methods to achieve global optimality. The advantages of the proposed algorithm over state-of-the-art first-order optimization methods are discussed.
BibTeX
@article{le2023spurious,
  author = {Quoc-Tung Le and Elisa Riccietti and Rémi Gribonval},
  title = {{Spurious Valleys, Spurious Minima and NP-hardness of Sparse Matrix Factorization With Fixed Support}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2023},
  doi = {10.1137/22m1496657},
}
Figure