An Implicit Form of Krasulina's k-PCA Update without the Orthonormality Constraint

Ehsan Amid, Manfred K. Warmuth

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:

  1. 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.
  2. 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.

Figure 1: Centered online k-PCA: the results of different algorithms on the MNIST (top) and CIFAR-10 (bottom). The value of k is shown on top of each figure. We plot the percentage of the excess loss which is defined as the normalized regret w.r.t to the best offline comparator (i.e. full-batch PCA). Each dot shows the progress of the algorithm in 1000 iteration intervals. Our proposed implicit Krasulina algorithm achieves the best convergence and provides the best runtime overall, especially when the values of d and k are large.

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.

Figure 2: Distributed setting: the results of different algorithms in a distributed setting. The value of k is shown on top of each figure. The updates are carried out across M = 10 machines and the models are combined and propagated back every 1000 iterations. The average loss of the machines for each algorithm is shown with a dashed line. The loss of the combined model is shown with a solid line. Note that our implicit Krasulina update consistently improves over time by combining the partial model. The remamining methods are less stable and provide poor results.

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

Abstract

We shed new insights on the two commonly used updates for the online $k$-PCA problem, namely, Krasulina's and Oja's updates. We show that Krasulina's update corresponds to a projected gradient descent step on the Stiefel manifold of the orthonormal $k$-frames, while Oja's update amounts to a gradient descent step using the unprojected gradient. Following these observations, we derive a more \emph{implicit} form of Krasulina's $k$-PCA update, i.e. a version that uses the information of the future gradient as much as possible. Most interestingly, our implicit Krasulina update avoids the costly QR-decomposition step by bypassing the orthonormality constraint. We show that the new update in fact corresponds to an online EM step applied to a probabilistic $k$-PCA model. The probabilistic view of the updates allows us to combine multiple models in a distributed setting. We show experimentally that the implicit Krasulina update yields superior convergence while being significantly faster. We also give strong evidence that the new update can benefit from parallelism and is more stable w.r.t. tuning of the learning rate.
BibTeX
@inproceedings{amid2020implicit,
  author = {Ehsan Amid and Manfred K. Warmuth},
  title = {{An Implicit Form of Krasulina's k-PCA Update without the Orthonormality Constraint}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=G5jIrKNu1cW},
}

Loading related content...

Figure