The Fast Convergence of Incremental PCA

By Akshay Balsubramani, Sanjoy Dasgupta, Yoav Freund. 2013

148 citations recorded by the source corpus.

We consider a situation in which we see samples in $\mathbb{R}^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.

Subfields: Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Statistics and Probability

Citations in the corpus

Batch Stationary Distribution Estimation (2020, methodology): “Many existing works have focused on the ﬁnite-dimension setting (Balsubramani et al., 2013; Hardt and Price, 2014; Yang et al., 2017), while Kim et al. (2005) and Xie et al. (2015) have extended the power method to the inﬁnite-dimension case using RKHS.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “[20, 7, 17, 13]), but these do not consider lower bounds or provable trade-offs.”
Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis (2017, unknown): “SGD for PCA was studied in several results in recent years [4, 20, 21, 12, 3].”
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients (2015, methodology): “These rules have been extended to the generalized Hebbian update rules [19, 20, 3] that compute the top k eigenvectors (the subspace case).”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, methodology): “leviate this issue, a popular line of research over the past several decades has been to consider streaming algorithms for PCA under the assumption that the data has reasonable statistical properties [5, 6, 7, 8, 9]. There have been signiﬁcant breakthroughs in getting near-optimal streaming PCA algo”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “This viewpoint is particularly useful for understanding algorithms such as Incremental SVD [15], Karasalo’s method [16], Oja’s method [17], Krasulina’s method [18], [19], and other algorithms based on power iterations [20], [21], to name a few.”
SketchOGD: Memory-Efficient Continual Learning (2023, unknown): “Incremental PCA [32–34] could be directly applied to OGD to compress the memory to a fixed size in an online manner.”
Fast and Simple PCA via Convex Optimization (2015, methodology): “Recently Shamir [24, 25] made headway in the non-convex spectral world by suggesting a stochastic optimization method for the problem, that is based Oja’s randomized Power method [19, 4] with an application of the variance reduction principle demonstrated in [14].”