mlsanityData to 7 Oct 2026

Fast Algorithms for Robust PCA via Gradient Descent

arXiv 1605.07784 ↗First posted 25 May 2016cs.IT cs.LG math.ITcited by 39

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 8; 2022: 6; 2023: 5; 2024: 12; 2025: 6; 2026: 2.

39 papers.

Sort:

By area:

  1. 2023LQ-LoRA: Low-rank Plus Quantized Matrix Decomposition for Efficient Language Model Finetuningcited by 92
  2. 2021Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detectioncited by 34
  3. 2021Robust CUR Decomposition: Theory and Imaging Applicationscited by 20
  4. 2024OATS: Outlier-Aware Pruning Through Sparse and Low Rank Decompositioncited by 19
  5. 2021Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approachcited by 14
  6. 2025Preconditioned Gradient Descent for Over-Parameterized Nonconvex Matrix Factorizationcited by 12
  7. 2022Fast and Provable Tensor Robust Principal Component Analysis via Scaled Gradient Descentcited by 11
  8. 2025RPCANet++: Deep Interpretable Robust PCA for Sparse Object Segmentationcited by 11
  9. 2021GNMR: A provable one-line algorithm for low rank matrix recoverycited by 10
  10. 2024GaLore+: Boosting Low-Rank Adaptation for LLMs with Cross-Head Projectioncited by 8
  11. 2022Low-Rank Approximation with 1/ε1/3 Matrix-Vector Productscited by 7
  12. 2022Riemannian CUR Decompositions for Robust Principal Component Analysiscited by 7
27 more
  1. 2025Deep Unfolding: Recent Developments, Theory, and Design Guidelinescited by 7
  2. 2023Provably Accelerating Ill-Conditioned Low-rank Estimation via Scaled Gradient Descent, Even with Overparameterizationcited by 6
  3. 2024Fast and Sample Efficient Multi-Task Representation Learning in Stochastic Contextual Banditscited by 6
  4. 2022Matrix Completion with Hierarchical Graph Side Informationcited by 5
  5. 2023Fast and Accurate Estimation of Low-Rank Matrices from Noisy Measurements via Preconditioned Non-Convex Gradient Descentcited by 5
  6. 2024On the Robustness of Cross-Concentrated Sampling for Matrix Completioncited by 5
  7. 2021Escaping Saddle Points for Nonsmooth Weakly Convex Functions via Perturbed Proximal Algorithmscited by 4
  8. 2023Matrix Completion in Almost-Verification Timecited by 4
  9. 2024Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysiscited by 4
  10. 2022Low-Rank Extragradient Method for Nonsmooth and Low-Rank Matrix Optimization Problemscited by 3
  11. 2024Accelerating Ill-conditioned Hankel Matrix Recovery via Structured Newton-like Descentcited by 3
  12. 2021Beyond Procrustes: Balancing-Free Gradient Descent for Asymmetric Low-Rank Matrix Sensingcited by 2
  13. 2021rSVDdpd: A Robust Scalable Video Surveillance Background Modelling Algorithmcited by 2
  14. 2024Quantization Avoids Saddle Points in Distributed Optimizationcited by 2
  15. 2024Leave-One-Out Analysis for Nonconvex Robust Matrix Completion with General Thresholding Functionscited by 1
  16. 2024Optimization Can Learn Johnson Lindenstrauss Embeddingscited by 1
  17. 2025A Dual Basis Approach for Structured Robust Euclidean Distance Geometrycited by 1
  18. 2021Provable Low Rank Plus Sparse Matrix Separation Via Nonconvex Regularizerscited by 0
  19. 2022Low-Rank Mirror-Prox for Nonsmooth and Low-Rank Matrix Optimization Problemscited by 0
  20. 2023Byzantine-Resilient Federated PCA and Low Rank Column-wise Sensingcited by 0
  21. 2024CURATRON: Complete and Robust Preference Data for Rigorous Alignment of Large Language Modelscited by 0
  22. 2024Efficient Federated Low Rank Matrix Completioncited by 0
  23. 2024Towards stable training of parallel continual learningcited by 0
  24. 2025AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimizationcited by 0
  25. 2025RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guaranteescited by 0
  26. 2026Robust Principal Component Completioncited by 0
  27. 2026Robust Low-Tubal-Rank Tensor Completion under Cross-Concentrated Samplingcited by 0