TL;DR
Researchers have developed a new "implicit" update for online $k$-PCA that bypasses the computationally expensive requirement of maintaining orthonormal matrices. By reinterpreting classical algorithms through the lens of probabilistic models and Expectation-Maximization (EM), this new approach achieves faster convergence, greater stability against learning rate tuning, and seamless scaling in distributed environments.
What Problem Does This Paper Address?
Principal Component Analysis (PCA) is a cornerstone of data science, used to find the most informative "directions" in high-dimensional data. However, as datasets grow to massive scales, traditional "batch" PCA (which looks at all data at once) becomes impossible.
Online PCA solvers process data one point at a time. The two most famous algorithms for this are Krasulina’s and Oja’s updates. While elegant, they face two major hurdles:
- The Orthonormality Constraint: To ensure the directions found are truly orthogonal (at right angles), these algorithms typically require a "QR-decomposition" step at every iteration. This is a costly $O(dk^2)$ operation that slows down training significantly as the number of components ($k$) or dimensions ($d$) increases.
- Stability: These are "explicit" updates, meaning they use the gradient from the current state to move to the next state. This often makes them sensitive to the choice of learning rate, leading to slow convergence or instability.
Methods
The authors first show that Krasulina’s and Oja’s updates are actually forms of stochastic gradient descent on the Stiefel manifold (the mathematical space of orthonormal matrices).
To improve upon this, they derive an Implicit Krasulina update. In optimization, "implicit" updates use information about the gradient at the future (updated) parameter. While usually harder to solve, the authors found a way to make this tractable by abandoning the hard orthonormality constraint during the update steps. Instead of forcing the matrix $C$ to be orthonormal, they use the Moore-Penrose pseudo-inverse ($C^\dagger$) to handle projections.
Crucially, they prove that this new update is equivalent to an online Expectation-Maximization (EM) step for a probabilistic PCA model. This theoretical bridge allows them to use a simple averaging technique to combine models trained on different machines—a task that is notoriously difficult when dealing with strictly orthonormal matrices.
Datasets
The authors evaluated their algorithm on two standard computer vision benchmarks:
- MNIST: 70,000 handwritten digit images (784 dimensions).
- CIFAR-10: 60,000 real-world images (3,072 dimensions).
Key Insights and Ideas
- Bypassing QR is a Game Changer: By allowing the matrix to deviate from orthonormality during training (and only projecting back at the very end), the algorithm achieves a massive speedup. The complexity drops to $O(dk)$, making it much more efficient for high-dimensional tasks.
- The Power of Implicitness: The implicit nature of the update acts as a natural regularizer. As shown in Table 1, the algorithm is remarkably stable even when the initial learning rate is off by a factor of 10.
- Distributed PCA Made Easy: In a distributed setting, you can't just average two orthonormal matrices and expect the result to be orthonormal. However, because the implicit Krasulina update works with arbitrary matrices, you can simply average them. This makes it highly effective for parallel processing.
Key Results
The experimental results demonstrate that the Implicit Krasulina algorithm consistently outperforms Oja, Krasulina, and Incremental PCA in both speed and accuracy.
As seen in Figure 1, the advantage of the implicit update becomes more pronounced as the number of components ($k$) increases. Furthermore, in distributed settings (Figure 2), the method shows superior stability. While other methods struggle or provide poor results when models are combined across machines, the implicit Krasulina update consistently improves over time.
Limitations and Future Work
The authors note that their update is "partially implicit" because they still use the old parameter matrix to calculate the initial projection of the data point. A "fully implicit" update would be even more stable but currently lacks a closed-form solution, requiring iterative solvers that might negate the speed benefits.
Future research could explore applying this online EM framework to other latent variable models beyond PCA, potentially bringing similar speed and stability gains to a wider array of machine learning tasks.
Summary updated