Oja's Algorithm for Streaming Sparse PCA

Oja's algorithm for Streaming Principal Component Analysis (PCA) for n data-points in a d dimensional space achieves the same sin-squared error O(r_mathsfeff/n) as the offline algorithm in O(d) space and O(nd) time and a single pass through the datapoints. Here r_mathsfeff is the effective rank (ratio of the trace and the principal eigenvalue of the population covariance matrix Sigma). Under this computational budget, we consider the problem of sparse PCA, where the principal eigenvector of Sigma is s-sparse, and r_mathsfeff can be large. In this setting, to our knowledge, textitthere are no known single-pass algorithms that achieve the minimax error bound in O(d) space and O(nd) time without either requiring strong initialization conditions or assuming further structure (e.g., spiked) of the covariance matrix. We show that a simple single-pass procedure that thresholds the output of Oja's algorithm (the Oja vector) can achieve the minimax error bound under some regularity conditions in O(d) space and O(nd) time. We present a nontrivial and novel analysis of the entries of the unnormalized Oja vector, which involves the projection of a product of independent random matrices on a random initial vector. This is completely different from previous analyses of Oja's algorithm and matrix products, which have been done when the r_mathsfeff is bounded.