Robust PCA via Non-convex Methods: Provable Bounds

on YouTube ↗49m

" summary

Claims a provable non‑convex algorithm that exactly recovers a low‑rank plus sparse decomposition under the same deterministic incoherence and sparsity regimes as convex methods, using an initial thresholding of large entries followed by alternating rank projections with stage‑wise rank growth and rank‑r SVD per iteration. Tolerates up to Θ(n/r) corruptions per row/column under incoherence, runs in roughly O(r^2 n^2) versus O(n^3) for full SVD convex solvers, converges in O(log(1/ε)) steps, and shows faster, cleaner foreground/background recovery in experiments.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 1:38Learning with Big Data
3. 2:28PCA: Classical Method
4. 3:20Robust PCA Problem
5. 6:02History
6. 8:16Why is Robust PCA difficult?
7. 9:28Convex Relaxation Techniques
8. 10:29Other Alternatives for Robust PCA?
9. 13:59Proposal for Non-convex Robust PCA
10. 16:50Observations regarding non-convex analysis
11. 18:17Non-convex success stories
12. 22:40Outline
13. 24:14Toy example: Rank-1 case
14. 28:55Rank-1 Analysis Contd.
15. 38:17Extension to general rank: challenges
16. 40:56Improved Algorithm for General Rank Setting
17. 45:16Synthetic Results
18. 46:17Real data: Foreground/background Separation
19. 48:21Conclusion

" related talks

• 28mRandomized Constrained Matrix DecompositionsBenjamin Erichson · Randomized Numerical Linear Algebra and Applications 2018
• 45mHigh Dimensional Robust Sparse RegressionConstantine Caramanis · Sublinear Algorithms and Nearest-Neighbor Search
• 17mTowards Practical Algorithms for Outlier-Robust EstimationAnkit Pensia · Meet the Fellows Welcome Event Fall 2024
• 44mSome Problems of Robust High-dimensional StatisticsGilad Lerman · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 51mTwo Concise Representations for High-Dimensional Visual DataJohn Wright · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 40mOptimally Weighted PCA for High-Dimensional Heteroscedastic DataLaura Balzano · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 45mNoisy Estimation of Simultaneously Structured ModelsMaryam Fazel · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 39mMemory Limited, Streaming PCAConstantine Caramanis · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)