通过分解方向与大小，提升低秩矩阵优化速度与效率。
Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics
- 将变量拆分为方向和大小两部分，优化更高效。
- 在矩阵分解等任务中，收敛速度比传统方法快得多。
- 适合对低秩矩阵优化有性能要求的场景。
低秩矩阵优化通常采用Burer-Monteiro（BM）形式化，但因子分解秩r的选择很关键，可能显著减慢优化过程。本文提出统一框架——方向-大小分解（DMD），将优化变量分解以提升效率，即使目标秩未知也有效。我们发展了两种基于DMD的方法：过参数化DMD使用大于必要值的秩r，且随r增大收敛更快；递归DMD则受过参数化DMD的增量特征值学习行为启发，具有更低内存与计算开销，弥补前者不足。两者均比应用于BM形式的梯度下降快得多。在矩阵分解、感知和补全任务上的数值实验验证了理论结果，展示了DMD的实际有效性。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。