mlsanityData to 7 Oct 2026

Global Optimality of Local Search for Low Rank Matrix Recovery

arXiv 1605.07221 ↗First posted 23 May 2016stat.ML cs.LG math.OCcited by 81

Not on the map. Why?

Abstract (arXiv)

We show that there are no spurious local minima in the non-convex factorized parametrization of low-rank matrix recovery from incoherent linear measurements. With noisy measurements we show all local minima are very close to a global optimum. Together with a curvature bound at saddle points, this yields a polynomial time global convergence guarantee for stochastic gradient descent em from random initialization.

Key facts. Cited by 81 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 May 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2019: 1; 2020: 0; 2021: 22; 2022: 20; 2023: 11; 2024: 10; 2025: 11; 2026: 6.

81 papers.

Sort:

By area:

  1. 2021A Geometric Analysis of Neural Collapse with Unconstrained Featurescited by 226
  2. 2022On the Optimization Landscape of Neural Collapse under MSE Loss: Global Optimality with Unconstrained Featurescited by 97
  3. 2022Are All Losses Created Equal: A Neural Collapse Perspectivecited by 78
  4. 2021Small random initialization is akin to spectral learning: Optimization and generalization guarantees for overparameterized low-rank matrix reconstructioncited by 77
  5. 2023Saddle-to-Saddle Dynamics in Diagonal Linear Networkscited by 54
  6. 2022Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimizationcited by 40
  7. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  8. 2022Implicit Full Waveform Inversion with Deep Neural Representationcited by 26
  9. 2024Compressible Dynamics in Deep Overparameterized Low-Rank Learning & Adaptationcited by 26
  10. 2021Rank Overspecified Robust Matrix Recovery: Subgradient Method and Exact Recoverycited by 21
  11. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  12. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
38 more
  1. 2019On the Global Convergence of Imitation Learning: A Case for Linear Quadratic Regulatorcited by 20
  2. 2023The Law of Parsimony in Gradient Descent for Learning Deep Linear Networkscited by 19
  3. 2025LoRA Training Provably Converges to a Low-Rank Global Minimum or It Fails Loudly (But it Probably Won't Fail)cited by 19
  4. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  5. 2021Finding Second-Order Stationary Points in Nonconvex-Strongly-Concave Minimax Optimizationcited by 12
  6. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  7. 2021Active manifolds, stratifications, and convergence to local minima in nonsmooth optimizationcited by 11
  8. 2021Escape saddle points by a simple gradient-descent based algorithmcited by 11
  9. 2022Randomly Initialized Alternating Least Squares: Fast Convergence for Matrix Sensingcited by 11
  10. 2021Sign-RIP: A Robust Restricted Isometry Property for Low-rank Matrix Recoverycited by 10
  11. 2023Global Optimality in Bivariate Gradient-based DAG Learningcited by 10
  12. 2021Fundamental limits for rank-one matrix estimation with groupwise heteroskedasticitycited by 8
  13. 2022A Validation Approach to Over-parameterized Matrix and Image Recoverycited by 8
  14. 2021Sharp Restricted Isometry Property Bounds for Low-rank Matrix Recovery Problems with Corrupted Measurementscited by 7
  15. 2021Escaping strict saddle points of the Moreau envelope in nonsmooth optimizationcited by 7
  16. 2022Noisy Low-rank Matrix Optimization: Geometry of Local Minima and Convergence Ratecited by 7
  17. 2021Group-Sparse Matrix Factorization for Transfer Learning of Word Embeddingscited by 6
  18. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  19. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  20. 2021Fast quantum state reconstruction via accelerated non-convex programmingcited by 5
  21. 2021Rank-one matrix estimation: analytic time evolution of gradient descent dynamicscited by 5
  22. 2022Intrinsic dimensionality and generalization properties of the R-norm inductive biascited by 5
  23. 2022Gradient descent provably escapes saddle points in the training of shallow ReLU networkscited by 5
  24. 2022Semidefinite Programming versus Burer-Monteiro Factorization for Matrix Sensingcited by 5
  25. 2022Simple and Optimal Stochastic Gradient Methods for Nonsmooth Nonconvex Optimizationcited by 5
  26. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  27. 2022Rank-1 Matrix Completion with Gradient Descent and Small Random Initializationcited by 4
  28. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  29. 2021Riemannian Perspective on Matrix Factorizationcited by 3
  30. 2021Escaping Saddle Points in Distributed Newton's Method with Communication Efficiency and Byzantine Resiliencecited by 3
  31. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 3
  32. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 3
  33. 2022Joint Learning-Based Stabilization of Multiple Unknown Linear Systemscited by 3
  34. 2022Blessing of Nonconvexity in Deep Linear Models: Depth Flattens the Optimization Landscape Around the True Solutioncited by 3
  35. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 3
  36. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  37. 2024Bilinear Sequence Regression: A Model for Learning from Long Sequences of High-dimensional Tokenscited by 3
  38. 2025One Rank at a Time: Cascading Error Dynamics in Sequential Learningcited by 3

50 most cited of 81 All 81 (JSON)