# Non-convex Robust PCA

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

## Key facts

- Cited by 41 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2014.

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

- [Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection](https://mlsanity.com/paper/2110.05649/) (2021)
- [Stochastic Continuous Submodular Maximization: Boosting via Non-oblivious Function](https://mlsanity.com/paper/2201.00703/) (2022)
- [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)
- [Restarted Nonconvex Accelerated Gradient Descent: No More Polylogarithmic Factor in the O(ε-7/4) Complexity](https://mlsanity.com/paper/2201.11411/) (2022)
- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [Submodular + Concave](https://mlsanity.com/paper/2106.04769/) (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)
- [Robust Tensor CUR Decompositions: Rapid Low-Tucker-Rank Tensor Recovery with Sparse Corruption](https://mlsanity.com/paper/2305.04080/) (2023)
- [Stable Recovery of Entangled Weights: Towards Robust Identification of Deep Neural Networks from Minimal Samples](https://mlsanity.com/paper/2101.07150/) (2021)
- [Fast Robust Tensor Principal Component Analysis via Fiber CUR Decomposition](https://mlsanity.com/paper/2108.10448/) (2021)
- [Riemannian CUR Decompositions for Robust Principal Component Analysis](https://mlsanity.com/paper/2206.09042/) (2022)
- [Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterization](https://mlsanity.com/paper/2310.06159/) (2023)
- [On the Robustness of Cross-Concentrated Sampling for Matrix Completion](https://mlsanity.com/paper/2401.15566/) (2024)
- [Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery](https://mlsanity.com/paper/2410.16826/) (2024)
- [Unveiling and Mitigating Adversarial Vulnerabilities in Iterative Optimizers](https://mlsanity.com/paper/2504.19000/) (2025)
- [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)
- [HASSLE-free: A unified Framework for Sparse plus Low-Rank Matrix Decomposition for LLMs](https://mlsanity.com/paper/2502.00899/) (2025)
- [Deep Unrolling for Nonconvex Robust Principal Component Analysis](https://mlsanity.com/paper/2307.05893/) (2023)
- [Sparse corruption in low-rank matrix inference: the PCA benchmark](https://mlsanity.com/paper/2511.11927/) (2025)
- [Low Rank Forecasting](https://mlsanity.com/paper/2101.12414/) (2021)
- [Square Root Principal Component Pursuit: Tuning-Free Noisy Robust Matrix Recovery](https://mlsanity.com/paper/2106.09211/) (2021)
- [Self-paced Principal Component Analysis](https://mlsanity.com/paper/2106.13880/) (2021)
- [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)
- [Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problems](https://mlsanity.com/paper/2206.11523/) (2022)
- [Favour: FAst Variance Operator for Uncertainty Rating](https://mlsanity.com/paper/2311.13036/) (2023)

## Abstract (arXiv)

We propose a new method for robust PCA -- the task of recovering a low-rank matrix from sparse corruptions that are of unknown value and support. Our method involves alternating between projecting appropriate residuals onto the set of low-rank matrices, and the set of sparse matrices; each projection is em non-convex but easy to compute. In spite of this non-convexity, we establish exact recovery of the low-rank matrix, under the same conditions that are required by existing methods (which are based on convex optimization). For an m × n input matrix (m ≤ n), our method has a running time of O(r2mn) per iteration, and needs O(log(1/ε)) iterations to reach an accuracy of ε. This is close to the running time of simple PCA via the power method, which requires O(rmn) per iteration, and O(log(1/ε)) iterations. In contrast, existing methods for robust PCA, which are based on convex optimization, have O(m2n) complexity per iteration, and take O(1/ε) iterations, i.e., exponentially more iterations for the same accuracy. Experiments on both synthetic and real data establishes the improved speed and accuracy of our method over existing convex implementations.