Exponentially convergent stochastic k-PCA without variance reduction

2019/04/03 by Cheng Tang, Tang, Cheng · 10 citations
Computer Science · Engineering · Mathematics · #Applied mathematics #Blind Source Separation Techniques #Econometrics #Economics #Exponential growth #FOS: Computer and information sciences #Geometry #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Mathematical analysis #Mathematics #Monte Carlo method #Reduction (mathematics) #Sparse and Compressive Sensing Techniques #Statistical Methods and Inference #Statistics #Variance (accounting) #Variance reduction #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1904.01750

published in arXiv (Cornell University) (Cornell University)

arxiv created 2019/04/03 · openalex publication_date 2019/04/03 · arxiv updated 2019/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Non-convex Robust PCA
• Finding Structure with Randomness: Probabilistic Algorithms for Constructing Approximate Matrix Decompositions
• Robust principal component analysis?
• Stochastic Optimization of PCA with Capped MSG
• The Noisy Power Method: A Meta Algorithm with Applications
• Simplified neuron model as a principal component analyzer
• Noise-adaptive Margin-based Active Learning and Lower Bounds under Tsybakov Noise Condition

Cited by

• Revisiting Orbital Minimization Method for Neural Operator Decomposition
• Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation

Related

• A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
• Convergence of Stochastic Gradient Descent for PCA
• Accelerated Stochastic Power Iteration
• Stochastic Gauss-Newton Algorithms for Online PCA
• Stochastic Approximation Algorithms for Principal Component Analysis