Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics
This work addresses the slow convergence and rank sensitivity of Burer-Monteiro optimization for low-rank matrix problems, offering a practical speedup for matrix factorization, sensing, and completion.
The paper proposes a direction-magnitude decomposition (DMD) framework for low-rank matrix optimization that achieves exponentially faster convergence than gradient descent on the Burer-Monteiro formulation, even when the target rank is unknown. Two DMD-based approaches are developed: overparameterized DMD (faster with larger rank) and recursive DMD (lower memory and cost).
Low-rank matrix optimization is often carried out via the Burer-Monteiro (BM) formulation, but choosing the factorization rank $r$ is delicate and can substantially slow optimization. We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve optimization efficiency even when the target rank is unknown. We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization. The first, overparameterized DMD, uses a rank $r$ larger than necessary and enjoys faster convergence as $r$ increases. The second, recursive DMD, is motivated by the incremental eigenpair learning, or saddle-to-saddle, behavior of overparameterized DMD. It achieves lower memory and computational costs, complementing overparameterized DMD. Both approaches are exponentially faster than gradient descent applied to the BM formulation. Numerical experiments on matrix factorization, sensing, and completion corroborate our theoretical findings and demonstrate the practical effectiveness of DMD.