Research map / Learning theory and algorithms / Matrix and tensor methods
Nearly-Linear Time and Streaming Algorithms for Outlier-Robust PCA
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use randomized power-iteration directions instead of filtering only along the top empirical eigenvector | Robust PCA · Strong contamination model | runtime: \widetilde{O}(nd/\epsilon^{4.5} {+} ndm/\epsilon^{1.5}) -> \widetilde{O}(nd/\epsilon^{2}) | Helped |
| Use randomized directions sampled from the leading empirical spectrum rather than deterministically testing top eigenvectors | Robust PCA · Robust PCA without eigenvalue separation | runtime | Helped |
| Track the trace-power potential across large-eigenvalue directions | Robust PCA · Stable contaminated distribution | potential decrease: (1-\gamma) | Helped |
| Increase the power parameter in stages, using smaller powers before the certification stage | Robust PCA · Stable contaminated distribution | runtime: \widetilde{O}(nd/\gamma^3) -> O(\frac{n d}{\gamma^2} \log^4(d/\epsilon)) | Helped |
| Require eigenvalue separation between the largest and the m-th largest eigenvalues | Prior nearly-linear-time robust PCA · Robust PCA | runtime applicability | Hurt |
| Replace the stronger variance-comparison stopping condition with a Schatten-p norm stopping condition (ablation) | Robust PCA · Robust PCA without eigenvalue separation | runtime: m = \Omega(d-r) | Hurt |
| Use the single-large-power algorithm rather than the staged-power schedule (ablation) | Robust PCA · Stable contaminated distribution | runtime: \widetilde{O}(nd/\gamma^3) -> O(\frac{n d}{\gamma^2} \log^4(d/\epsilon)) | Hurt |
Closest papers by meaning
- Robust Streaming PCA (NeurIPS 2022 · similarity 0.93)
- Oja's Algorithm for Streaming Sparse PCA (NeurIPS 2024 · similarity 0.88)
- Low Precision Streaming PCA (NeurIPS 2025 · similarity 0.88)
- Capturing the denoising effect of PCA via compression ratio (NeurIPS 2024 · similarity 0.87)
- Efficient Sparse PCA via Block-Diagonalization (ICLR 2025 · similarity 0.87)
- Fast and Provable Algorithms for Sparse PCA with Improved Sample Complexity (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.