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

Ehsan Amid, Manfred K. Warmuth

Introduction

Principal Component Analysis (PCA) is a fundamental tool in data science, essential for dimensionality reduction, noise filtering, and visualization. However, traditional batch PCA methods are computationally prohibitive for modern massive datasets. Online PCA algorithms, which process data points sequentially, offer a scalable alternative.

The most widely used online methods, such as Oja’s and Krasulina’s updates, are "explicit" gradient-based approaches. These methods face two primary challenges: extreme sensitivity to the choice of learning rate and the high computational cost of maintaining orthonormal projection matrices, which typically requires $O(dk^2)$ QR decompositions at every step.

The Implicit Krasulina Update

This research introduces an implicit Krasulina update that addresses these limitations. Unlike explicit updates that use the gradient at the current parameter, implicit updates utilize the gradient at the future parameter value, which inherently provides greater stability.

The key innovation lies in dropping the strict orthonormality constraint during the update process. The authors demonstrate that this relaxation allows for a tractable, closed-form solution that is "self-correcting." Furthermore, they establish a theoretical bridge between this update and online Expectation-Maximization (EM) for probabilistic PCA. This connection justifies the algorithm's performance without explicit orthonormalization and provides a principled foundation for distributed learning.

Experimental Results

The proposed method was evaluated on the MNIST (784 dimensions) and CIFAR-10 (3,072 dimensions) datasets.

Runtime and Convergence

The Implicit Krasulina update demonstrates superior convergence speed compared to Oja, standard Krasulina, and incremental methods. By avoiding frequent QR decompositions and utilizing a rank-1 update, the algorithm significantly reduces runtime, particularly as the number of components ($k$) increases.

Figure 1: Comparison of online k-PCA algorithms on MNIST and CIFAR-10. The proposed Implicit Krasulina method (orange diamonds) consistently achieves lower loss in less runtime.

Robustness and Distributed Scaling

A major advantage of the implicit formulation is its robustness to hyperparameters. In empirical tests, the method's performance remained stable even when learning rates were varied by an order of magnitude ($0.1\times$ to $10\times$), whereas competing methods often diverged or stalled.

Furthermore, the relaxation of the orthonormality constraint simplifies distributed PCA. Because the weight matrices do not need to be orthonormal at every step, models trained on separate machines can be combined through simple averaging. In a 10-machine setup, this approach yielded a global model nearly as effective as one trained on a single machine with the full dataset.

Figure 2: Performance in distributed settings across MNIST and CIFAR-10. The proposed method (orange) effectively integrates information from multiple machines via simple averaging, outperforming other distributed baselines.

Conclusion

The implicit Krasulina update offers a faster, more stable, and more flexible framework for online $k$-PCA. By bypassing the orthonormality constraint and leveraging the stability of implicit updates, it enables efficient processing of high-dimensional data in both centralized and distributed environments. Future work may explore fully implicit updates and applications to other latent variable models.

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},
}
Figure