Oja's Streaming PCA Algorithm with Matrix-Bernstein-Matching Finite-Sample Guarantees

Oja's Streaming PCA Algorithm with Matrix-Bernstein-Matching Finite-Sample Guarantees is a single-pass O(d)-space, linear-time streaming eigenvector estimation procedure and operator-theoretic convergence analysis established by Jain, Jin, Kakade, Netrapalli, and Sidford (2016) that initializes w_0 uniformly at random on the unit sphere in R^d and applies the normalized rank-1/matrix update w_i <- (w_{i-1} + eta_i A_i w_{i-1}) / ||w_{i-1} + eta_i A_i w_{i-1}||_2 over independent streaming samples A_1, ..., A_n satisfying E[A_i] = Sigma, ||A_i - Sigma||_2 <= M, and max{||E[(A_i-Sigma)(A_i-Sigma)^T]||_2, ||E[(A_i-Sigma)^T(A_i-Sigma)]||_2} <= V, using a shifted inverse-linear step size sequence eta_i = alpha / ((lambda_1 - lambda_2)(beta + i)) to match (and asymptotically improve by O(log d) upon) the batch Matrix Bernstein + Wedin sample complexity without warm-start initialization.