# Exponentially convergent stochastic k-PCA without variance reduction

arXiv: https://arxiv.org/abs/1904.01750 · HTML: https://mlsanity.com/paper/1904.01750/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Apr 2019.

## Built on by (most cited first, 12 of 12)

- [Personalized PCA: Decoupling Shared and Unique Features](https://mlsanity.com/paper/2207.08041/) (2022)
- [The Edge of Orthogonality: A Simple View of What Makes BYOL Tick](https://mlsanity.com/paper/2302.04817/) (2023)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Bootstrapped Representations in Reinforcement Learning](https://mlsanity.com/paper/2306.10171/) (2023)
- [A Novel Stochastic Gradient Descent Algorithm for Learning Principal Subspaces](https://mlsanity.com/paper/2212.04025/) (2022)
- [FAST-PCA: A Fast and Exact Algorithm for Distributed Principal Component Analysis](https://mlsanity.com/paper/2108.12373/) (2021)
- [Speeding up PCA with priming](https://mlsanity.com/paper/2109.03709/) (2021)
- [Self-consistent Gradient-like Eigen Decomposition in Solving Schr"odinger Equations](https://mlsanity.com/paper/2202.01388/) (2022)
- [The Symmetric Generalized Eigenvalue Problem as a Nash Equilibrium](https://mlsanity.com/paper/2206.04993/) (2022)
- [Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering](https://mlsanity.com/paper/2207.14589/) (2022)
- [Revisiting Orbital Minimization Method for Neural Operator Decomposition](https://mlsanity.com/paper/2510.21952/) (2025)
- [Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation](https://mlsanity.com/paper/2608.04406/) (2026)

## Abstract (arXiv)

We present Matrix Krasulina, an algorithm for online k-PCA, by generalizing the classic Krasulina's method (Krasulina, 1969) from vector to matrix case. We show, both theoretically and empirically, that the algorithm naturally adapts to data low-rankness and converges exponentially fast to the ground-truth principal subspace. Notably, our result suggests that despite various recent efforts to accelerate the convergence of stochastic-gradient based methods by adding a O(n)-time variance reduction step, for the k-PCA problem, a truly online SGD variant suffices to achieve exponential convergence on intrinsically low-rank data.