mlsanityData to 7 Oct 2026

k-SVD with Gradient Descent

arXiv 2502.00320 ↗First posted 1 Feb 2025cs.LG math.OCcited by 0

Not on the map. Why?

Abstract (arXiv)

The emergence of modern compute infrastructure for iterative optimization has led to great interest in developing optimization-based approaches for a scalable computation of k-SVD, i.e., the k≥ 1 largest singular values and corresponding vectors of a matrix of rank d ≥ 1. Despite lots of exciting recent works, all prior works fall short in this pursuit. Specifically, the existing results are either for the exact-parameterized (i.e., k = d) and over-parameterized (i.e., k > d) settings; or only establish local convergence guarantees; or use a step-size that requires problem-instance-specific oracle-provided information. In this work, we complete this pursuit by providing a gradient-descent method with a simple, universal rule for step-size selection (akin to pre-conditioning), that provably finds k-SVD for a matrix of any rank d ≥ 1. We establish that the gradient method with random initialization enjoys global linear convergence for any k, d ≥ 1. Our convergence analysis reveals that the gradient method has an attractive region, and within this attractive region, the method behaves like Heron's method (a.k.a. the Babylonian method). Our analytic results about the said attractive region imply that the gradient method can be enhanced by means of Nesterov's momentum-based acceleration technique. The resulting improved convergence rates match those of rather complicated methods typically relying on Lanczos iterations or variants thereof. We provide an empirical study to validate the theoretical results.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 30 of its 54 references that are in the map. First posted on arXiv 1 Feb 2025.

Builds on

30 of 54 references.

References · 30

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2017How to Escape Saddle Points Efficientlycited by 284
  3. 2015Escaping From Saddle Points --- Online Stochastic Gradient for Tensor Decompositioncited by 241
  4. 2018Algorithmic Regularization in Learning Deep Homogeneous Models: Layers are Automatically Balancedcited by 172
  5. 2018Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overviewcited by 159
  6. 2017No Spurious Local Minima in Nonconvex Low Rank Problems: A Unified Geometric Analysiscited by 127
  7. 2016Matrix Completion has No Spurious Local Minimumcited by 124
  8. 2014Phase Retrieval via Wirtinger Flow: Theory and Algorithmscited by 123
  9. 2020Spectral Methods for Data Science: A Statistical Perspectivecited by 111
  10. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  11. 2018Gradient Descent with Random Initialization: Fast Global Convergence for Nonconvex Phase Retrievalcited by 71
  12. 2020Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descentcited by 70
18 more
  1. 2016Riemannian SVRG: Fast Stochastic Optimization on Riemannian Manifoldscited by 64
  2. 2015Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decompositioncited by 63
  3. 2013The Noisy Power Method: A Meta Algorithm with Applicationscited by 58
  4. 2019Noisy Matrix Completion: Understanding Statistical Guarantees for Convex Relaxation via Nonconvex Optimizationcited by 58
  5. 2021Acceleration Methodscited by 48
  6. 2022Algorithmic Regularization in Model-free Overparametrized Asymmetric Matrix Factorizationcited by 34
  7. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 32
  8. 2014Global Convergence of Stochastic Gradient Descent for Some Non-convex Matrix Problemscited by 25
  9. 2016Gradient Descent Converges to Minimizerscited by 25
  10. 2016LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Paincited by 22
  11. 2017Accelerated Stochastic Power Iterationcited by 22
  12. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  13. 2014A Stochastic PCA and SVD Algorithm with an Exponential Convergence Ratecited by 18
  14. 2016Faster Eigenvector Computation via Shift-and-Invert Preconditioningcited by 18
  15. 2015Fast and Simple PCA via Convex Optimizationcited by 16
  16. 2015Global Convergence of Non-Convex Gradient Descent for Computing Matrix Squarerootcited by 15
  17. 2024On the Crucial Role of Initialization for Matrix Factorizationcited by 15
  18. 2021Efficient GPU implementation of randomized SVD and its applicationscited by 5

Built on by

Not cited yet.