Research map / Optimization / Nonconvex and smooth optimization
Fast Algorithms for Robust PCA via Gradient Descent
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 |
|---|---|---|---|
| Replace AltProj-style alternating projection with projected gradient descent on the factorized space plus a sorting-based sparse estimator (fully observed) | Robust PCA · theoretical complexity | running time: O(rd^2 log(1/eps)) vs O(r^2 d^2 log(1/eps)) for AltProj | Helped |
| Subsample entries (partial observation, p ~ mu^2 r^2 log d / d) instead of using all entries | Fast RPCA partial observation · theoretical complexity | running time: O(mu^3 r^4 d log d log(1/eps)) cost, near-linear in d for small r | Helped |
| Use gradient descent with partial observations at sampling rate p=0.2 instead of full observations on FB separation | Fast RPCA on Restaurant/ShoppingMall · Foreground-background separation | separation quality (qualitative) | No clear effect |
| Subsampling observed entries (p) in gradient descent on synthetic data (ablation) | Fast RPCA GD · Synthetic d=5000, r=10, alpha=0.1 | convergence rate | No clear effect |
| Use approximate SVD only once in initialization instead of SVD every iteration (vs Cherapanamjeri et al.) | Partial-observation RPCA · theoretical comparison | number of SVDs | Helped |
| Increase the sparsity tolerance from alpha=O(1/(mu r^{2/3}... )) to alpha=O(1/(mu r^1.5)) via the sparse estimator | Fast RPCA · theoretical robustness | corruption fraction alpha: alpha = O(1/(mu r^1.5)) vs O(1/(mu^{2/3} r^{2/3} d)) in prior work | Helped |
Closest papers by meaning
- Nearly Optimal Robust Matrix Completion (ICML 2017 · similarity 0.93)
- Symmetric Matrix Completion with ReLU Sampling (ICML 2024 · similarity 0.89)
- RGNMR: A Gauss-Newton method for robust matrix completion with theoretical guarantees (NeurIPS 2025 · similarity 0.89)
- Fast exact recovery of noisy matrix from few entries: the infinity norm approach (NeurIPS 2025 · similarity 0.89)
- Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery (ICML 2025 · similarity 0.88)
- Semi-Random Matrix Completion via Flow-Based Adaptive Reweighting (NeurIPS 2024 · similarity 0.88)
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.