Search papers, labs, and topics across Lattice.
This paper introduces direction-magnitude decomposition (DMD), a novel framework for low-rank matrix optimization that enhances efficiency by decomposing the optimization variable, even when the target rank is unknown. The authors present two DMD-based methods: overparameterized DMD, which accelerates convergence by utilizing a larger-than-necessary rank, and recursive DMD, which reduces memory and computational costs while leveraging saddle-to-saddle dynamics. Experimental results demonstrate that both DMD approaches significantly outperform traditional gradient descent applied to the Burer-Monteiro formulation in various matrix factorization tasks.
Overparameterized DMD achieves exponential speedups in convergence for low-rank matrix optimization, even when the target rank is uncertain.
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.
