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

arXiv: https://arxiv.org/abs/1506.06081 · HTML: https://mlsanity.com/paper/1506.06081/

## Key facts

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

## Built on by (most cited first, 30 of 34)

- [The Power of Preconditioning in Overparameterized Low-Rank Matrix Sensing](https://mlsanity.com/paper/2302.01186/) (2023)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Global Convergence of Sub-gradient Method for Robust Matrix Recovery: Small Initialization, Noisy Measurements, and Over-parameterization](https://mlsanity.com/paper/2202.08788/) (2022)
- [Preconditioned Gradient Descent for Overparameterized Nonconvex Burer--Monteiro Factorization with Global Optimality Certification](https://mlsanity.com/paper/2206.03345/) (2022)
- [How Over-Parameterization Slows Down Gradient Descent in Matrix Sensing: The Curses of Symmetry and Initialization](https://mlsanity.com/paper/2310.01769/) (2023)
- [Tensor-on-Tensor Regression: Riemannian Optimization, Over-parameterization, Statistical-computational Gap, and Their Interplay](https://mlsanity.com/paper/2206.08756/) (2022)
- [Low-rank Tensor Estimation via Riemannian Gauss-Newton: Statistical Optimality and Second-Order Convergence](https://mlsanity.com/paper/2104.12031/) (2021)
- [Improved Global Guarantees for the Nonconvex Burer--Monteiro Factorization via Rank Overparameterization](https://mlsanity.com/paper/2207.01789/) (2022)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Fast quantum state reconstruction via accelerated non-convex programming](https://mlsanity.com/paper/2104.07006/) (2021)
- [Sharp Global Guarantees for Nonconvex Low-rank Recovery in the Noisy Overparameterized Regime](https://mlsanity.com/paper/2104.10790/) (2021)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [Nonconvex Factorization and Manifold Formulations are Almost Equivalent in Low-rank Matrix Optimization](https://mlsanity.com/paper/2108.01772/) (2021)
- [Bayesian Low-rank Matrix Completion with Dual-graph Embedding: Prior Analysis and Tuning-free Inference](https://mlsanity.com/paper/2203.10044/) (2022)
- [Nonconvex Matrix Factorization is Geodesically Convex: Global Landscape Analysis for Fixed-rank Matrix Optimization From a Riemannian Perspective](https://mlsanity.com/paper/2209.15130/) (2022)
- [Computationally Efficient and Statistically Optimal Robust High-Dimensional Linear Regression](https://mlsanity.com/paper/2305.06199/) (2023)
- [Efficient Over-parameterized Matrix Sensing from Noisy Measurements via Alternating Preconditioned Gradient Descent](https://mlsanity.com/paper/2502.00463/) (2025)
- [Non-convex matrix sensing: Breaking the quadratic rank barrier in the sample complexity](https://mlsanity.com/paper/2408.13276/) (2024)
- [One Rank at a Time: Cascading Error Dynamics in Sequential Learning](https://mlsanity.com/paper/2505.22602/) (2025)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [Error Bound of Empirical ℓ2 Risk Minimization for Noisy Standard and Generalized Phase Retrieval Problems](https://mlsanity.com/paper/2205.13827/) (2022)
- [Exponentially Convergent Algorithms for Supervised Matrix Factorization](https://mlsanity.com/paper/2311.11182/) (2023)
- [On Stochastic Variance Reduced Gradient Method for Semidefinite Optimization](https://mlsanity.com/paper/2101.00236/) (2021)
- [Deep learned SVT: Unrolling singular value thresholding to obtain better MSE](https://mlsanity.com/paper/2105.06934/) (2021)
- [Low-rank Tensor Learning with Nonconvex Overlapped Nuclear Norm Regularization](https://mlsanity.com/paper/2205.03059/) (2022)
- [Supervised Dictionary Learning with Auxiliary Covariates](https://mlsanity.com/paper/2206.06774/) (2022)
- [Q3R: Quadratic Reweighted Rank Regularizer for Effective Low-Rank Training](https://mlsanity.com/paper/2511.04485/) (2025)

## 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.