mlsanityData to 14 Oct 2026

A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements

arXiv 1506.06081 ↗First posted 19 Jun 2015stat.ML cs.LGcited by 34

Not on the map. Why?

Abstract (arXiv)

We propose a simple, scalable, and fast gradient descent algorithm to optimize a nonconvex objective for the rank minimization problem and a closely related family of semidefinite programs. With O(r3 kappa2 n log n) random measurements of a positive semidefinite n × n matrix of rank r and condition number kappa, our method is guaranteed to converge linearly to the global optimum.

Key facts. Cited by 34 papers in the map (data through 14 Oct 2026). First posted on arXiv 19 Jun 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 9; 2022: 11; 2023: 6; 2024: 2; 2025: 5; 2026: 1.

34 papers.

Sort:

  1. 2023The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensingcited by 33
  2. 2021On the computational and statistical complexity of over-parameterized matrix sensingcited by 31
  3. 2022Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterizationcited by 21
  4. 2022Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certificationcited by 21
  5. 2023How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initializationcited by 18
  6. 2022Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplaycited by 15
  7. 2021Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergencecited by 13
  8. 2022Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterizationcited by 13
  9. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  10. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  11. 2022Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completioncited by 6
  12. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
22 more
  1. 2021Fast quantum state reconstruction via accelerated non-convex programmingcited by 5
  2. 2021Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regimecited by 5
  3. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  4. 2021Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimizationcited by 4
  5. 2022Bayesian Low-rank Matrix Completion with Dual-graph Embedding: Prior Analysis and Tuning-free Inferencecited by 4
  6. 2022Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspectivecited by 4
  7. 2023Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regressioncited by 4
  8. 2025Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descentcited by 4
  9. 2024Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexitycited by 3
  10. 2025One Rank at a Time: Cascading Error Dynamics in Sequential Learningcited by 3
  11. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  12. 2022Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problemscited by 2
  13. 2023Exponentially Convergent Algorithms for Supervised Matrix Factorizationcited by 2
  14. 2021On Stochastic Variance Reduced Gradient Method for Semidefinite Optimizationcited by 1
  15. 2021Deep learned SVT: Unrolling singular value thresholding to obtain better MSEcited by 1
  16. 2022Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularizationcited by 1
  17. 2022Supervised Dictionary Learning with Auxiliary Covariatescited by 1
  18. 2025Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Trainingcited by 1
  19. 2022Unrolling SVT to obtain computationally efficient SVT for n-qubit quantum state tomographycited by 0
  20. 2024Near-Optimal differentially private low-rank trace regression with guaranteed private initializationcited by 0
  21. 2025Phase retrieval with rank d measurements -- descending algorithms phase transitionscited by 0
  22. 2026AdaPaD: Adaptive Parallel Deflation for PEFT with Self-Correcting Rank Discoverycited by 0