Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics

• URL: http://arxiv.org/abs/2606.31390v1
• Date: Tue, 30 Jun 2026 09:19:16 GMT
• Title: Direction-Magnitude Decomposition for Low-Rank Matrix Optimization: Faster Convergence and Saddle-to-saddle Dynamics
• Abstract summary: We propose a unified framework, termed direction-magnitude decomposition (DMD), that decomposes the optimization variable to improve efficiency.<n>We develop two DMD-based approaches and establish their theoretical advantages on the canonical problem of matrix factorization.
• Score: 32.90061456124932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Diff3R: Feed-forward 3D Gaussian Splatting with Uncertainty-aware Differentiable Optimization [76.38917994186733]
  Diff3R is a novel framework that bridges feed-forward prediction and test-time optimization.<n>We show that it can be seamlessly integrated into existing feed-forward 3DGS architectures for both pose-given and pose-free methods.
  arXiv  Detail & Related papers  (2026-04-01T15:40:20Z)
• ODELoRA: Training Low-Rank Adaptation by Solving Ordinary Differential Equations [54.886931928255564]
  Low-rank adaptation (LoRA) has emerged as a widely adopted parameter-efficient fine-tuning method in deep transfer learning.<n>We propose a novel continuous-time optimization dynamic for LoRA factor matrices in the form of an ordinary differential equation (ODE)<n>We show that ODELoRA achieves stable feature learning, a property that is crucial for training deep neural networks at different scales of problem dimensionality.
  arXiv  Detail & Related papers  (2026-02-07T10:19:36Z)
• Automatic Rank Determination for Low-Rank Adaptation via Submodular Function Maximization [56.78271181959529]
  SubLoRA is a rank determination method for Low-Rank Adaptation (LoRA) based on submodular function.<n>Our method combines solid theoretical foundations, second-order accuracy, and practical computational efficiency.
  arXiv  Detail & Related papers  (2025-07-02T15:56:40Z)
• Efficient algorithms for the Hadamard decomposition [14.653207365119796]
  The Hadamard decomposition is a powerful technique for data analysis and matrix compression.<n>In this paper, we develop a framework that decomposes a given matrix into the product of two or more low-rank approximations.<n>We conduct experiments to compare our method with the existing descent-based approaches for the Hadamard decomposition.
  arXiv  Detail & Related papers  (2025-04-18T11:14:25Z)
• DiffoRA: Enabling Parameter-Efficient Fine-Tuning via Differential Module Selection [32.369133126167085]
  Low-Rank Adaptation (LoRA) has gained popularity for its streamlined design by incorporating low-rank matrices into existing pre-trained models.<n>We propose DiffoRA, which enables adaptive adoption of the low-rank decomposition matrices.
  arXiv  Detail & Related papers  (2025-02-13T02:41:34Z)
• A Stochastic Approach to Bi-Level Optimization for Hyperparameter Optimization and Meta Learning [74.80956524812714]
  We tackle the general differentiable meta learning problem that is ubiquitous in modern deep learning. These problems are often formalized as Bi-Level optimizations (BLO) We introduce a novel perspective by turning a given BLO problem into a ii optimization, where the inner loss function becomes a smooth distribution, and the outer loss becomes an expected loss over the inner distribution.
  arXiv  Detail & Related papers  (2024-10-14T12:10:06Z)
• Accelerating Matrix Factorization by Dynamic Pruning for Fast Recommendation [0.49399484784577985]
  Matrix factorization (MF) is a widely used collaborative filtering algorithm for recommendation systems (RSs) With the dramatically increased number of users/items in current RSs, the computational complexity for training a MF model largely increases. We propose algorithmic methods to accelerate MF, without inducing any additional computational resources.
  arXiv  Detail & Related papers  (2024-03-18T16:27:33Z)
• Sparse high-dimensional linear regression with a partitioned empirical Bayes ECM algorithm [62.997667081978825]
  We propose a computationally efficient and powerful Bayesian approach for sparse high-dimensional linear regression. Minimal prior assumptions on the parameters are used through the use of plug-in empirical Bayes estimates. The proposed approach is implemented in the R package probe.
  arXiv  Detail & Related papers  (2022-09-16T19:15:50Z)
• Reducing the Variance of Gaussian Process Hyperparameter Optimization with Preconditioning [54.01682318834995]
  Preconditioning is a highly effective step for any iterative method involving matrix-vector multiplication. We prove that preconditioning has an additional benefit that has been previously unexplored. It simultaneously can reduce variance at essentially negligible cost.
  arXiv  Detail & Related papers  (2021-07-01T06:43:11Z)
• On the Efficient Implementation of the Matrix Exponentiated Gradient Algorithm for Low-Rank Matrix Optimization [26.858608065417663]
  Convex optimization over the spectrahedron has important applications in machine learning, signal processing and statistics. We propose efficient implementations of MEG, which are tailored for optimization with low-rank matrices, and only use a single low-rank SVD on each iteration. We also provide efficiently-computable certificates for the correct convergence of our methods.
  arXiv  Detail & Related papers  (2020-12-18T19:14:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.