Intrinsic Grassmann Averages for Online Linear, Robust and Nonlinear Subspace Learning

Rudrasis Chakraborty, Søren Hauberg, Baba C. Vemuri

Abstract

Principal Component Analysis (PCA) and Kernel Principal Component Analysis (KPCA) are fundamental methods in machine learning for dimensionality reduction. The former is a technique for finding this approximation in finite dimensions and the latter is often in an infinite dimensional Reproducing Kernel Hilbert-space (RKHS). In this paper, we present a geometric framework for computing the principal linear subspaces in both situations as well as for the robust PCA case, that amounts to computing the intrinsic average on the space of all subspaces: the Grassmann manifold. Points on this manifold are defined as the subspaces spanned by $K$-tuples of observations. The intrinsic Grassmann average of these subspaces are shown to coincide with the principal components of the observations when they are drawn from a Gaussian distribution. We show similar results in the RKHS case and provide an efficient algorithm for computing the projection onto the this average subspace. The result is a method akin to KPCA which is substantially faster. Further, we present a novel online version of the KPCA using our geometric framework. Competitive performance of all our algorithms are demonstrated on a variety of real and synthetic data sets.

Introduction

Dimensionality reduction is a cornerstone of modern machine learning, with Principal Component Analysis (PCA) serving as its most ubiquitous tool. However, standard PCA faces significant challenges in contemporary applications: batch processing requires massive datasets to reside entirely in memory, iterative online versions like Oja’s rule are sensitive to manually tuned learning rates, and non-linear extensions like Kernel PCA (KPCA) suffer from cubic computational complexity ($O(N^3)$).

This research reimagines PCA not as an algebraic eigenvalue problem, but as a geometric averaging problem on the Grassmann manifold—the space of all linear subspaces. By calculating recursive "intrinsic" averages on this curved manifold, the authors develop a suite of online algorithms for linear, robust, and kernel PCA that are faster, more stable, and parameter-free.

The Geometric Framework: PCA as an Average

The core innovation is the Intrinsic Grassmann Average (IGA). Instead of averaging raw data points, the framework partitions data into blocks, treats each block as a subspace (a point on the Grassmannian), and identifies the "Fréchet mean." This is the unique point on the manifold that minimizes the sum of squared geodesic distances to all other points.

The average subspace as the geometric mean of subspaces spanned by data points.

A profound insight of this work is that for Gaussian-distributed data, the leading $K$ principal components are exactly the intrinsic average of the subspaces spanned by the observations. This realization transforms a linear algebra problem into one of differential geometry, providing a more stable foundation for streaming data.

Recursive Subspace Learning Algorithms

The authors introduce three primary algorithms based on this geometric foundation:

  1. RIGA (Recursive IGA): A linear PCA estimator that updates the subspace estimate by moving along the shortest path (geodesic) toward each new data point. Crucially, it is parameter-free; the step size is automatically determined by the number of samples processed ($1/(k+1)$), preventing the oscillations common in Oja's rule.
  2. KRIGA (Kernel RIGA): An extension for non-linear subspaces. To bypass the $O(N^3)$ bottleneck of standard KPCA, KRIGA utilizes Random Fourier Features to approximate the kernel. This converts an infinite-dimensional problem into a manageable finite-dimensional one, achieving $O(N)$ complexity.
  3. RRIGA (Recursive Robust IGA): To handle outliers, such as shadows in video or corrupted pixels, the Fréchet mean is replaced with the Fréchet median. This robust variant effectively ignores data points that deviate significantly from the consensus subspace.

Experimental Validation

The framework was evaluated across diverse datasets, ranging from synthetic Gaussian data to high-dimensional real-world benchmarks:

  • 3D Human Motion (Dyna): On over 21,000 meshes (20,670 dimensions each), RIGA achieved a reconstruction error of 1.0 mm, significantly outperforming Oja’s rule (16.8 mm) and EM-PCA (1.9 mm).
  • High-Dimensional Video: Processing every frame of the film Santa Claus Conquers the Martians ($D = 230,400$), KRIGA maintained a nearly flat runtime per frame, whereas standard KPCA's computation time grew cubically.
  • Robust Background Subtraction: In the Wallflower and UCSD Anomaly Detection benchmarks, RRIGA successfully separated backgrounds from foregrounds even with 10% outlier pixels, outperforming specialized algorithms like GRASTA in both speed and error rate.

Conclusion and Limitations

By shifting the perspective of PCA to geometric averaging, this work provides a robust, scalable, and parameter-free framework for online learning. While the theoretical convergence relies on a Gaussian assumption, empirical results demonstrate strong performance on real-world, non-Gaussian data. Future work may address the complexities of updating the data mean in truly online scenarios and further optimizing the trade-off between random feature resolution and speed in KRIGA.

Summary updated

Abstract

Principal Component Analysis (PCA) and Kernel Principal Component Analysis (KPCA) are fundamental methods in machine learning for dimensionality reduction. The former is a technique for finding this approximation in finite dimensions and the latter is often in an infinite dimensional Reproducing Kernel Hilbert-space (RKHS). In this paper, we present a geometric framework for computing the principal linear subspaces in both situations as well as for the robust PCA case, that amounts to computing the intrinsic average on the space of all subspaces: the Grassmann manifold. Points on this manifold are defined as the subspaces spanned by $K$-tuples of observations. The intrinsic Grassmann average of these subspaces are shown to coincide with the principal components of the observations when they are drawn from a Gaussian distribution. We show similar results in the RKHS case and provide an efficient algorithm for computing the projection onto the this average subspace. The result is a method akin to KPCA which is substantially faster. Further, we present a novel online version of the KPCA using our geometric framework. Competitive performance of all our algorithms are demonstrated on a variety of real and synthetic data sets.
BibTeX
@article{chakraborty2021intrinsic,
  author = {Rudrasis Chakraborty and Søren Hauberg and Baba C. Vemuri and Baba C. Vemuri},
  title = {{Intrinsic Grassmann Averages for Online Linear, Robust and Nonlinear Subspace Learning}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2021},
  doi = {10.1109/tpami.2020.2992392},
}
Figure