# Fast Algorithms for Robust PCA via Gradient Descent

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

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2016.

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

- [LQ-LoRA: Low-rank Plus Quantized Matrix Decomposition for Efficient Language Model Finetuning](https://mlsanity.com/paper/2311.12023/) (2023)
- [Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection](https://mlsanity.com/paper/2110.05649/) (2021)
- [Robust CUR Decomposition: Theory and Imaging Applications](https://mlsanity.com/paper/2101.05231/) (2021)
- [OATS: Outlier-Aware Pruning Through Sparse and Low Rank Decomposition](https://mlsanity.com/paper/2409.13652/) (2024)
- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorization](https://mlsanity.com/paper/2504.09708/) (2025)
- [RPCANet++: Deep Interpretable Robust PCA for Sparse Object Segmentation](https://mlsanity.com/paper/2508.04190/) (2025)
- [Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descent](https://mlsanity.com/paper/2206.09109/) (2022)
- [GNMR: A provable one-line algorithm for low rank matrix recovery](https://mlsanity.com/paper/2106.12933/) (2021)
- [GaLore+: Boosting Low-Rank Adaptation for LLMs with Cross-Head Projection](https://mlsanity.com/paper/2412.19820/) (2024)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Riemannian CUR Decompositions for Robust Principal Component Analysis](https://mlsanity.com/paper/2206.09042/) (2022)
- [Deep Unfolding: Recent Developments, Theory, and Design Guidelines](https://mlsanity.com/paper/2512.03768/) (2025)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Bandits](https://mlsanity.com/paper/2410.02068/) (2024)
- [Matrix Completion with Hierarchical Graph Side Information](https://mlsanity.com/paper/2201.01728/) (2022)
- [Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descent](https://mlsanity.com/paper/2305.17224/) (2023)
- [On the Robustness of Cross-Concentrated Sampling for Matrix Completion](https://mlsanity.com/paper/2401.15566/) (2024)
- [Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithms](https://mlsanity.com/paper/2102.02837/) (2021)
- [Matrix Completion in Almost-Verification Time](https://mlsanity.com/paper/2308.03661/) (2023)
- [Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysis](https://mlsanity.com/paper/2402.09754/) (2024)
- [Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2202.04026/) (2022)
- [Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descent](https://mlsanity.com/paper/2406.07409/) (2024)
- [Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensing](https://mlsanity.com/paper/2101.05113/) (2021)
- [rSVDdpd: A Robust Scalable Video Surveillance Background Modelling Algorithm](https://mlsanity.com/paper/2109.10680/) (2021)
- [Quantization Avoids Saddle Points in Distributed Optimization](https://mlsanity.com/paper/2403.10423/) (2024)
- [Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functions](https://mlsanity.com/paper/2407.19446/) (2024)
- [Optimization Can Learn Johnson Lindenstrauss Embeddings](https://mlsanity.com/paper/2412.07242/) (2024)
- [A Dual Basis Approach for Structured Robust Euclidean Distance Geometry](https://mlsanity.com/paper/2505.18414/) (2025)
- [Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizers](https://mlsanity.com/paper/2109.12713/) (2021)

## Abstract (arXiv)

We consider the problem of Robust PCA in the fully and partially observed settings. Without corruptions, this is the well-known matrix completion problem. From a statistical standpoint this problem has been recently well-studied, and conditions on when recovery is possible (how many observations do we need, how many corruptions can we tolerate) via polynomial-time algorithms is by now understood. This paper presents and analyzes a non-convex optimization approach that greatly reduces the computational complexity of the above problems, compared to the best available algorithms. In particular, in the fully observed case, with r denoting rank and d dimension, we reduce the complexity from O(r2d2log(1/varepsilon)) to O(rd2log(1/varepsilon)) -- a big savings when the rank is big. For the partially observed case, we show the complexity of our algorithm is no more than O(r4d log d log(1/varepsilon)). Not only is this the best-known run-time for a provable algorithm under partial observation, but in the setting where r is small compared to d, it also allows for near-linear-in-d run-time that can be exploited in the fully-observed case as well, by simply running our algorithm on a subset of the observations.