Research map / Learning theory and algorithms / Matrix and tensor methods
Fast Stochastic Algorithms for SVD and PCA: Convergence Properties and Convexity
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 block updates with an alignment transformation to generalize VR-PCA to rank k | VR-PCA · Top-k SVD/PCA | runtime: \mathcal{O}\left(dk(n+\frac{r^2k^3}{\lambda^2})\log(1/\epsilon)\right) | Helped |
| Initialize with a Gaussian vector followed by one exact power iteration | VR-PCA · Leading eigenvector from random initialization | runtime: \mathcal{O}\left(nd+\frac{d}{\lambda^2}\log^4(d)\right) | Helped |
| Use the constrained convex region only after obtaining an initialization within O(lambda) of the optimum | Negative Rayleigh quotient optimization · Leading eigenvector | strong convexity: \lambda | Helped |
| Optimize the negative Rayleigh quotient over the entire Euclidean space instead of a constrained local set | Negative Rayleigh quotient optimization · A = [[1, 0], [0, 0]] | convexity: not positive semidefinite for all but a measure-zero set | Hurt |
| Use one power iteration before stochastic updates rather than random initialization alone | Stochastic PCA initialization · Leading eigenvector initialization | squared alignment with the leading eigenvector: \frac{1}{d} -> on the order of 1/\text{nrank}(A) | Helped |
| Expect the constrained convex region to yield a substantially better overall runtime after VR-PCA warm-starting | Two-stage VR-PCA followed by convex optimization · High-accuracy leading eigenvector | runtime: d\left(\left(n+\frac{1}{\lambda^2}\right)\log\left(\frac{1}{\lambda}\right)+\left(n+\sqrt{\frac{n}{\lambda}}\right)\log\ | No clear effect |
Closest papers by meaning
- Stochastic PCA with $\ell_2$ and $\ell_1$ Regularization (ICML 2018 · similarity 0.90)
- Convergence of Stochastic Gradient Descent for PCA (ICML 2016 · similarity 0.89)
- Exponentially convergent stochastic k-PCA without variance reduction (NeurIPS 2019 · similarity 0.88)
- Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA (ICML 2026 · similarity 0.88)
- Efficient Convex Relaxations for Streaming PCA (NeurIPS 2019 · similarity 0.88)
- Rethinking PCA Through Duality (NeurIPS 2025 · similarity 0.85)
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.