Introduction
Principal Component Analysis (PCA) is a foundational technique for dimensionality reduction. While batch methods like Singular Value Decomposition (SVD) are standard, they become computationally prohibitive for massive datasets that cannot fit in memory. Online PCA algorithms process data points sequentially, but they typically struggle with two issues: the computational overhead of maintaining orthonormal basis vectors (often requiring QR decomposition at each step) and extreme sensitivity to the choice of learning rate.
This paper introduces the Stochastic Implicit Krasulina Algorithm, a novel approach that reframes online $k$-PCA as an online Expectation-Maximization (EM) task. By abandoning the strict orthonormality constraint and adopting an implicit update rule, the algorithm achieves superior stability, speed, and parallelizability.
Methods
The proposed method makes two fundamental shifts from traditional online PCA solvers like Oja’s or Krasulina’s:
- Implicit Updates: Traditional "explicit" methods update parameters based on the gradient at the current estimate. The authors derive a "partially implicit" closed-form update based on the gradient at the future parameter position. This naturally incorporates a normalized learning rate, significantly reducing sensitivity to initial hyperparameters.
- Relaxed Constraints: Instead of forcing the component matrix $C$ to satisfy $C^T C = I$ at every iteration, the algorithm treats $C$ as an arbitrary matrix. Projections are handled via the matrix pseudo-inverse. To maintain $O(kd)$ efficiency, the authors utilize the Sherman-Morrison formula for rank-1 updates on the matrix inverse, bypassing expensive QR-decomposition steps.
Mathematically, the authors demonstrate that this update is equivalent to an online EM algorithm applied to a probabilistic PCA model. This connection provides a robust probabilistic foundation and simplifies distributed implementation.
Experimental Setup
The algorithm was benchmarked against Oja’s method, the original Krasulina’s algorithm, and other incremental solvers using two standard datasets:
- MNIST: 70,000 images of handwritten digits (784 dimensions).
- CIFAR-10: 60,000 color images (3,072 dimensions).
The evaluation focused on "percent excess loss" (a measure of regret relative to optimal batch PCA) across varying numbers of components ($k$) and different learning rate scales.
Results
The Stochastic Implicit Krasulina Algorithm consistently outperformed competing methods across several dimensions.
Speed and Convergence
The implicit update is significantly faster than traditional methods. By avoiding the QR step and converging in fewer iterations, it reaches lower error rates in a fraction of the runtime.
Robustness to Learning Rates
A major advantage of the implicit formulation is its stability. While Oja’s and Krasulina’s methods often diverge or slow down significantly when the learning rate is poorly tuned, the Implicit Krasulina method remains remarkably stable.
Scalability
In distributed settings, the ability to work with non-orthonormal matrices allows for simple averaging of models across machines. Tests with 10 parallel machines showed that the combined model converged to the optimal solution more reliably than methods requiring complex orthonormal merging.
Discussion and Future Work
The Stochastic Implicit Krasulina Algorithm represents a significant step forward for large-scale PCA. Its EM-based framework provides both theoretical elegance and practical performance gains. However, the current update is "partially implicit" because the initial projection still relies on the previous parameter estimate. Future research may explore fully implicit updates or extending this framework to sparse and kernel-based PCA variants.
Summary updated