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:
- 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.
- 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