On the Convergence of Eigenspaces in Kernel Principal Component Analysis

Laurent Zwald, Gilles BlanchardNeurIPS 2005 · OpenReview

Introduction

Principal Component Analysis (PCA) and its non-linear counterpart, Kernel PCA (KPCA), are fundamental tools for dimensionality reduction. Traditionally, the performance of these methods is evaluated based on reconstruction error—how well the low-dimensional projection approximates the original data.

However, KPCA is rarely an end in itself; it typically serves as a preprocessing step for downstream tasks like classification or regression. In these scenarios, the stability of the eigenspace is paramount. If slight variations in training data cause the principal axes to rotate significantly, subsequent models built on those axes become unreliable. This paper addresses a critical gap in the literature by shifting the focus from variance capture to eigenspace stability, providing rigorous, non-asymptotic statistical guarantees for KPCA.

Theoretical Framework

The authors utilize operator perturbation theory within the framework of Reproducing Kernel Hilbert Spaces (RKHS). By treating the data covariance as a Hilbert-Schmidt operator in an infinite-dimensional space, they analyze the orthogonal projector onto the entire $D$-dimensional principal subspace, rather than looking at individual, potentially unstable eigenvectors.

Standard perturbation results, such as the Davis-Kahan theorem, often imply that estimation errors accumulate as the number of dimensions $D$ increases. To overcome this, the authors derive refined bounds that treat the entire $D$-eigenspace as a single unit. The mathematical isolation of this subspace relies heavily on the spectral gap—the distance between the eigenvalues kept and those discarded.

Contour $\gamma$ in the complex plane enclosing the first $D$ eigenvalues, illustrating the spectral gap $\delta_D$ used to isolate the principal subspace.

Key Results and Insights

The central contribution of the paper is a non-asymptotic bound on the difference between the true projection operator $P_{S_D}$ and the empirical one $\hat{P}_{S_D}$:

$$ \|P_{S_D} - \hat{P}_{S_D}\| \leq \frac{B_D}{\sqrt{n}} $$

Here, $n$ is the sample size, and $B_D$ is a constant dependent on the kernel's maximum value and the inverse of the spectral gap, defined as $\delta_D = \frac{1}{2}(\lambda_D - \lambda_{D+1})$. This result yields several profound insights:

  • The Spectral Gap is King: The stability of the KPCA subspace is primarily dictated by the gap between the last retained eigenvalue ($\lambda_D$) and the first discarded one ($\lambda_{D+1}$). A large gap ensures a stable subspace, while a tiny gap renders it shaky.
  • Dimension Independence: Counterintuitively, the complexity of estimating the subspace does not inherently scale with $D$. Estimating a high-dimensional subspace can be just as stable as a 1-dimensional one, provided the spectral gap at the boundary $D$ remains sufficiently large.
  • Geometric Stability: The error bound can be geometrically interpreted as the tangent of the angle between the true and estimated subspaces, offering a tangible measure of stability in high-dimensional feature spaces.
  • Kernel Trick Consistency: The results confirm that the Nyström approximation (used to compute KPCA on finite data) converges to the true underlying operator at a standard statistical rate of $O(n^{-1/2})$.

Limitations and Practical Implications

As a purely theoretical contribution, the paper focuses on mathematical proofs rather than empirical benchmarks on specific datasets. The analysis primarily assumes "simple" eigenvalues (no exact multiplicities), though it can be extended provided $D$ does not split a group of identical eigenvalues. Furthermore, while the non-asymptotic bounds are robust and "safe," the authors acknowledge they may not be as tight as asymptotic limits suggested by the Central Limit Theorem.

Practically, this work provides strong theoretical justification for a common heuristic: choosing the number of components $D$ at the point where the largest drop (gap) in eigenvalues occurs. By maximizing the spectral gap, practitioners are directly maximizing the theoretical stability of their KPCA subspace.

Summary updated

Abstract

This paper presents a non-asymptotic statistical analysis of Kernel-PCA with a focus different from the one proposed in previous work on this topic. Here instead of considering the reconstruction error of KPCA we are interested in approximation error bounds for the eigenspaces themselves. We prove an upper bound depending on the spacing between eigenvalues but not on the dimensionality of the eigenspace. As a consequence this allows to infer stability results for these estimated spaces.
BibTeX
@inproceedings{zwald2005convergence,
  author = {Laurent Zwald and Gilles Blanchard},
  title = {{On the Convergence of Eigenspaces in Kernel Principal Component Analysis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2005},
  url = {https://openreview.net/forum?id=HkWE5UWdZS},
}
Figure