mlsanityData to 7 Oct 2026

Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA

arXiv 2305.02544 ↗First posted 4 May 2023cs.LG cs.DS math.STcited by 10

Not on the map. Why?

Abstract (arXiv)

We study principal component analysis (PCA), where given a dataset in ℝd from a distribution, the task is to find a unit vector v that approximately maximizes the variance of the distribution after being projected along v. Despite being a classical task, standard estimators fail drastically if the data contains even a small fraction of outliers, motivating the problem of robust PCA. Recent work has developed computationally-efficient algorithms for robust PCA that either take super-linear time or have sub-optimal error guarantees. Our main contribution is to develop a nearly-linear time algorithm for robust PCA with near-optimal error guarantees. We also develop a single-pass streaming algorithm for robust PCA with memory usage nearly-linear in the dimension.

Key facts. Cited by 10 papers in the map (data through 7 Oct 2026). Builds on 33 of its 47 references that are in the map. First posted on arXiv 4 May 2023.

Builds on

33 of 47 references.

References · 33

  1. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  2. 2016Agnostic Estimation of Mean and Covariancecited by 131
  3. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  4. 2016Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixturescited by 114
  5. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  6. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  7. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  8. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  9. 2018Efficient Algorithms and Lower Bounds for Robust Linear Regressioncited by 76
  10. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  11. 2017List-Decodable Robust Mean Estimation and Learning Mixtures of Spherical Gaussianscited by 70
  12. 2020Outlier Robust Mean Estimation with Subgaussian Rates via Stabilitycited by 50
21 more
  1. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  2. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  3. 2019List-Decodable Linear Regressioncited by 42
  4. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  5. 2020Robust Meta-learning for Mixed Linear Regression with Small Batchescited by 41
  6. 2018High-Dimensional Robust Mean Estimation in Nearly-Linear Timecited by 39
  7. 2019Robust subgaussian estimation of a mean vector in nearly linear timecited by 37
  8. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  9. 2020Settling the Robust Learnability of Mixtures of Gaussianscited by 32
  10. 2020Optimal Robust Linear Regression in Nearly Linear Timecited by 31
  11. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  12. 2019Outlier-Robust High-Dimensional Sparse Estimation via Iterative Filteringcited by 23
  13. 2022Robust Sparse Mean Estimation via Sum of Squarescited by 23
  14. 2021Clustering Mixture Models in Almost-Linear Time via List-Decodable Mean Estimationcited by 21
  15. 2022Streaming Algorithms for High-Dimensional Robust Statisticscited by 21
  16. 2020Robust estimation via generalized quasi-gradientscited by 19
  17. 2021Outlier-Robust Sparse Estimation via Non-Convex Optimizationcited by 14
  18. 2020Optimal Mean Estimation without a Variancecited by 13
  19. 2022Outlier-Robust Sparse Mean Estimation for Heavy-Tailed Distributionscited by 13
  20. 2019Robust Streaming PCAcited by 6
  21. 2020Robust Mean Estimation on Highly Incomplete Data with Arbitrary Outlierscited by 6

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 5; 2025: 0; 2026: 3.

10 papers.

  1. 2024Oja's Algorithm for Streaming Sparse PCAcited by 9
  2. 2023Near-Optimal Algorithms for Gaussians with Huber Contamination: Mean Estimation and Linear Regressioncited by 7
  3. 2024Black-Box k-to-1-PCA Reductions: Theory and Applicationscited by 7
  4. 2024Robust SVD Made Easy: A fast and reliable algorithm for large-scale data analysiscited by 4
  5. 2024Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contaminationcited by 2
  6. 2024Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Errorcited by 2
  7. 2026Tractable Gaussian Phase Retrieval with Heavy Tails and Adversarial Corruption with Near-Linear Sample Complexitycited by 1
  8. 2023A Combinatorial Approach to Robust PCAcited by 0
  9. 2026Discrete Double-Bracket Flows for Isotropic-Noise Invariant Eigendecompositioncited by 0
  10. 2026Convex Basins in Single-Index Model Loss Landscapes: Applications to Robust Recovery under Strong Adversarial Corruptioncited by 0