The Fast Convergence of Incremental PCA

2015/01/15 by Akshay Balsubramani, Balsubramani, Akshay, Sanjoy Dasgupta +3 · 2 citations
Mathematics · #Advanced Statistical Methods and Models #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Statistical Methods and Bayesian Inference #Statistical Methods and Inference

paper · pdf · doi:10.48550/arxiv.1501.03796

openalex publication_date 2015/01/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a situation in which we see samples in ℝ^d drawn i.i.d. from some distribution with mean zero and unknown covariance A. We wish to compute the top eigenvector of A in an incremental fashion - with an algorithm that maintains an estimate of the top eigenvector in O(d) space, and incrementally adjusts the estimate with each new data point that arrives. Two classical such schemes are due to Krasulina (1969) and Oja (1983). We give finite-sample convergence rates for both.

Cited by

• Implicitly Normalized Online PCA: A Regularized Algorithm with Exact High-Dimensional Dynamics
• Low-Precision Streaming PCA

Related

• Augmented sparse principal component analysis for high dimensional data
• Convergence Rate of Krasulina Estimator
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• Rates of Bootstrap Approximation for Eigenvalues in High-Dimensional PCA
• Tracy-Widom, Gaussian, and Bootstrap: Approximations for Leading Eigenvalues in High-Dimensional PCA