# Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees

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

## Key facts

- Cited by 70 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2015.

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

- [GaLore: Memory-Efficient LLM Training by Gradient Low-Rank Projection](https://mlsanity.com/paper/2403.03507/) (2024)
- [Large Learning Rate Tames Homogeneity: Convergence and Balancing Effect](https://mlsanity.com/paper/2110.03677/) (2021)
- [Fira: Can We Achieve Full-rank Training of LLMs Under Low-rank Constraint?](https://mlsanity.com/paper/2410.01623/) (2024)
- [PDPP: Projected Diffusion for Procedure Planning in Instructional Videos](https://mlsanity.com/paper/2303.14676/) (2023)
- [On the computational and statistical complexity of over-parameterized matrix sensing](https://mlsanity.com/paper/2102.02756/) (2021)
- [Scaling and Scalability: Provable Nonconvex Low-Rank Tensor Estimation from Incomplete Measurements](https://mlsanity.com/paper/2104.14526/) (2021)
- [Mind Mappings: Enabling Efficient Algorithm-Accelerator Mapping Space Search](https://mlsanity.com/paper/2103.01489/) (2021)
- [Convergence of gradient descent for deep neural networks](https://mlsanity.com/paper/2203.16462/) (2022)
- [Inference for Heteroskedastic PCA with Missing Data](https://mlsanity.com/paper/2107.12365/) (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)
- [VeLoRA: Memory Efficient Training using Rank-1 Sub-Token Projections](https://mlsanity.com/paper/2405.17991/) (2024)
- [Subspace based Federated Unlearning](https://mlsanity.com/paper/2302.12448/) (2023)
- [Noisy Gradient Descent Converges to Flat Minima for Nonconvex Matrix Factorization](https://mlsanity.com/paper/2102.12430/) (2021)
- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [Propulsion: Steering LLM with Tiny Fine-Tuning](https://mlsanity.com/paper/2409.10927/) (2024)
- [Federated Learning and Meta Learning: Approaches, Applications, and Directions](https://mlsanity.com/paper/2210.13111/) (2022)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [Implicit Regularization in Matrix Sensing via Mirror Descent](https://mlsanity.com/paper/2105.13831/) (2021)
- [Gradient Weight-normalized Low-rank Projection for Efficient LLM Training](https://mlsanity.com/paper/2412.19616/) (2024)
- [Multi-source Learning via Completion of Block-wise Overlapping Noisy Matrices](https://mlsanity.com/paper/2105.10360/) (2021)
- [Parameter-Efficient Fine-Tuning of Large Language Models using Semantic Knowledge Tuning](https://mlsanity.com/paper/2410.08598/) (2024)
- [Approximate message passing from random initialization with applications to mathbbZ2 synchronization](https://mlsanity.com/paper/2302.03682/) (2023)
- [A Validation Approach to Over-parameterized Matrix and Image Recovery](https://mlsanity.com/paper/2209.10675/) (2022)
- [COAP: Memory-Efficient Training with Correlation-Aware Gradient Projection](https://mlsanity.com/paper/2412.00071/) (2024)
- [Low-Tubal-Rank Tensor Recovery via Factorized Gradient Descent](https://mlsanity.com/paper/2401.11940/) (2024)
- [Model-free Neural Lyapunov Control for Safe Robot Navigation](https://mlsanity.com/paper/2203.01190/) (2022)
- [Accelerating SGD for Highly Ill-Conditioned Huge-Scale Online Matrix Completion](https://mlsanity.com/paper/2208.11246/) (2022)
- [Towards a Theoretical Foundation of Policy Optimization for Learning Control Policies](https://mlsanity.com/paper/2210.04810/) (2022)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Convergence of Gradient Descent with Small Initialization for Unregularized Matrix Completion](https://mlsanity.com/paper/2402.06756/) (2024)

## Abstract (arXiv)

Optimization problems with rank constraints arise in many applications, including matrix regression, structured PCA, matrix completion and matrix decomposition problems. An attractive heuristic for solving such problems is to factorize the low-rank matrix, and to run projected gradient descent on the nonconvex factorized optimization problem. The goal of this problem is to provide a general theoretical framework for understanding when such methods work well, and to characterize the nature of the resulting fixed point. We provide a simple set of conditions under which projected gradient descent, when given a suitable initialization, converges geometrically to a statistically useful solution. Our results are applicable even when the initial solution is outside any region of local convexity, and even when the problem is globally concave. Working in a non-asymptotic framework, we show that our conditions are satisfied for a wide range of concrete models, including matrix regression, structured PCA, matrix completion with real and quantized observations, matrix decomposition, and graph clustering problems. Simulation results show excellent agreement with the theoretical predictions.