# Kernel PCA with the Nystr"om method

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 102 references that are in the map.
- First posted on arXiv 12 Sep 2021.

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

- [Just Interpolate: Kernel "Ridgeless" Regression Can Generalize](https://mlsanity.com/paper/1808.00387/) (2018)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Kernel Instrumental Variable Regression](https://mlsanity.com/paper/1906.00232/) (2019)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Kernel methods through the roof: handling billions of points efficiently](https://mlsanity.com/paper/2006.10350/) (2020)
- [FALKON: An Optimal Large Scale Kernel Method](https://mlsanity.com/paper/1705.10958/) (2017)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Diving into the shallows: a computational perspective on large-scale shallow learning](https://mlsanity.com/paper/1703.10622/) (2017)
- [Statistical and computational trade-offs in estimation of sparse principal components](https://mlsanity.com/paper/1408.5369/) (2014)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)
- [Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off](https://mlsanity.com/paper/1706.06296/) (2017)
- [ParK: Sound and Efficient Kernel Ridge Regression by Feature Space Partitions](https://mlsanity.com/paper/2106.12231/) (2021)
- [Metric and non-metric proximity transformations at linear costs](https://mlsanity.com/paper/1411.1646/) (2014)
- [Linearized Kernel Dictionary Learning](https://mlsanity.com/paper/1509.05634/) (2015)
- [Upper and Lower Bounds on the Performance of Kernel PCA](https://mlsanity.com/paper/2012.10369/) (2020)

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

- [Autoencoding Random Forests](https://mlsanity.com/paper/2505.21441/) (2025)
- [Kernel PCA for Out-of-Distribution Detection: Non-Linear Kernel Selection and Approximation](https://mlsanity.com/paper/2505.15284/) (2025)

## Abstract (arXiv)

The Nystr"om method is one of the most popular techniques for improving the scalability of kernel methods. However, it has not yet been derived for kernel PCA in line with classical PCA. In this paper we derive kernel PCA with the Nystr"om method, thereby providing one of the few available options to make kernel PCA scalable. We further study its statistical accuracy through a finite-sample confidence bound on the empirical reconstruction error compared to the full method. The behaviours of the method and bound are illustrated through computer experiments on multiple real-world datasets. As an application of the method we present kernel principal component regression with the Nystr"om method, as an alternative to Nystr"om kernel ridge regression for efficient regularized regression with kernels.