# Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA

arXiv: https://arxiv.org/abs/2105.08875 · HTML: https://mlsanity.com/paper/2105.08875/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 53 references that are in the map.
- First posted on arXiv 19 May 2021.

## Builds on (most cited first, 9 of 9)

- [Generalization Properties of Learning with Random Features](https://mlsanity.com/paper/1602.04474/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Randomized sketches for kernels: Fast and optimal non-parametric regression](https://mlsanity.com/paper/1501.06195/) (2015)
- [Randomized Nonlinear Component Analysis](https://mlsanity.com/paper/1402.0119/) (2014)
- [Streaming Kernel PCA with tildeO(√n) Random Features](https://mlsanity.com/paper/1808.00934/) (2018)
- [Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off](https://mlsanity.com/paper/1706.06296/) (2017)
- [On the Sample Complexity of Subspace Learning](https://mlsanity.com/paper/1408.5032/) (2014)
- [Gain with no Pain: Efficient Kernel-PCA by Nystr"om Sampling](https://mlsanity.com/paper/1907.05226/) (2019)

## Built on by (most cited first, 10 of 10)

- [Spectral Regularized Kernel Two-Sample Tests](https://mlsanity.com/paper/2212.09201/) (2022)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [On the Approximation of Kernel functions](https://mlsanity.com/paper/2403.06731/) (2024)
- [Kernel PCA with the Nystr"om method](https://mlsanity.com/paper/2109.05578/) (2021)
- [Deep Sketched Output Kernel Regression for Structured Prediction](https://mlsanity.com/paper/2406.09253/) (2024)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2506.16283/) (2025)
- [Kernel PCA for Out-of-Distribution Detection: Non-Linear Kernel Selection and Approximation](https://mlsanity.com/paper/2505.15284/) (2025)
- [Random feature approximation for general spectral methods](https://mlsanity.com/paper/2308.15434/) (2023)
- [Kernel Trace Distance: Quantum Statistical Metric between Measures through RKHS Density Operators](https://mlsanity.com/paper/2507.06055/) (2025)

## Abstract (arXiv)

Kernel methods provide an elegant framework for developing nonlinear learning algorithms from simple linear methods. Though these methods have superior empirical performance in several real data applications, their usefulness is inhibited by the significant computational burden incurred in large sample situations. Various approximation schemes have been proposed in the literature to alleviate these computational issues, and the approximate kernel machines are shown to retain the empirical performance. However, the theoretical properties of these approximate kernel machines are less well understood. In this work, we theoretically study the trade-off between computational complexity and statistical accuracy in Nystr"om approximate kernel principal component analysis (KPCA), wherein we show that the Nystr"om approximate KPCA matches the statistical performance of (non-approximate) KPCA while remaining computationally beneficial. Additionally, we show that Nystr"om approximate KPCA outperforms the statistical behavior of another popular approximation scheme, the random feature approximation, when applied to KPCA.