Structured Support Exploration for Multilayer Sparse Matrix Factorization

Quoc-Tung Le, Rémi GribonvalICASSP 2021 · OpenReview

TL;DR

This paper tackles a key limitation of proximal algorithms for sparse matrix factorization: premature convergence of the "support" (the locations of non-zero entries). They introduce a new algorithm, Bilinear Hard Thresholding Pursuit (BHTP), to encourage exploration of the support. Additionally, they propose a novel "Generalized Hungarian Method" for projecting matrices onto a specific structured sparsity class, enabling efficient factorization of matrices like the Hadamard Transform.

What Problem Does This Paper Address?

Matrix factorization, especially with sparsity constraints, is fundamental to many machine learning and signal processing tasks like dictionary learning and dimension reduction. Proximal algorithms are popular for these tasks, but they suffer from a critical flaw: the set of non-zero elements (the "support") in the factorized matrices can get stuck in a suboptimal configuration early in the optimization process. This "premature convergence of the support" hinders the algorithm's ability to find the true sparse structure. Furthermore, factorizing matrices that arise from fast linear transforms (like the Hadamard Transform) requires specific structured sparsity patterns in the factors, and existing methods struggle to enforce these.

Methods

The paper introduces two main contributions:

  1. Bilinear Hard Thresholding Pursuit (BHTP): To combat premature support convergence, the authors adapt the "Hard Thresholding Pursuit" (HTP) algorithm, originally for sparse linear regression, to the matrix factorization setting. BHTP iteratively fixes one factor and optimizes the other, explicitly forcing the exploration of the support. It then uses a standard proximal update to refine the solution.
  2. Generalized Hungarian Method (GHM): For structured sparsity, particularly for matrices like the Hadamard Transform, the authors define "k-regular matrices" (matrices where each row and column has at most k non-zero entries). They then develop the GHM, a novel algorithm that projects a given matrix onto this set of k-regular matrices. This GHM is crucial for enabling proximal algorithms to correctly factorize matrices with these specific structured sparsity requirements.

Datasets

Not discussed in the paper. The paper focuses on synthetic data (Hadamard Transform) and a real-world dataset from functional brain imaging (magnetoencephalography - MEG).

Key Insights and Ideas

  • Support Exploration is Crucial: The paper strongly emphasizes that simply finding some sparse factors isn't enough; the algorithm must actively search for the correct sparse structure. Premature convergence of the support is a significant bottleneck.
  • HTP Adaptation for Matrix Factorization: Adapting HTP, a successful technique for linear regression, to the matrix factorization problem is a clever way to directly address the support exploration issue.
  • k-Regular Matrices and GHM: The concept of k-regular matrices provides a well-defined target for structured sparsity. The GHM is a significant algorithmic contribution, offering a tractable way to enforce this structure, which was a limitation in prior work.
  • Direct Multilayer Factorization: The GHM allows proximal algorithms to directly tackle multilayer factorization problems without resorting to hierarchical factorization (HF) methods, which can have their own limitations.

Key Results

  • BHTP Performance: In experiments on MEG data, BHTP consistently outperformed standard PALM (Proximal Alternating Linearized Minimization) in terms of approximation error, especially when the desired sparsity level (k₀) was low. This indicates BHTP's effectiveness in finding better sparse supports.
  • Hadamard Transform Factorization: Using the GHM projection operator within PALM enabled an "exact" factorization of the Hadamard Transform (achieving a very low error of 2 × 10⁻¹⁶), a feat that prior methods with SPLINCOL struggled with.
  • HF vs. Direct Factorization: The paper suggests that while HF might avoid issues with non-factorizable intermediate matrices, direct factorization using PALM with GHM is more robust and potentially advantageous.

Limitations and Future Work

  • Step Size Tuning: The authors acknowledge the need for better understanding and methods for setting step sizes in their algorithms.
  • Intrinsic Scaling Ambiguities: The paper notes that matrix factorization problems often have inherent scaling ambiguities that need to be addressed.
  • Extension to Complex-Valued Data: Future work could extend BHTP to handle complex-valued matrices.
  • Speedup for Large Matrices: Developing faster versions of their algorithms to handle very large matrices is a key area for future research.

Summary updated

Abstract

Matrix factorization with sparsity constraints plays an important role in many machine learning and signal processing problems such as dictionary learning, data visualization, dimension reduction. Among the most popular tools for sparse matrix factorization are proximal algorithms, a family of algorithms based on proximal operators. In this paper, we address two problems with the application of proximal algorithms to sparse matrix factorization. On the one hand, we analyze a weakness of proximal algorithms in sparse matrix factorization: the premature convergence of the support. A remedy is also proposed to address this problem. On the other hand, we describe a new tractable proximal operator called Generalized Hungarian Method, associated to so-called k-regular matrices, which are useful for the factorization of a class of matrices associated to fast linear transforms. We further illustrate the effectiveness of our proposals by numerical experiments on the Hadamard Transform and magnetoencephalography matrix factorization.
BibTeX
@inproceedings{le2021structured,
  author = {Quoc-Tung Le and Rémi Gribonval},
  title = {{Structured Support Exploration for Multilayer Sparse Matrix Factorization}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=tpTYqyiQlSE},
}

Loading related content...

Figure