# Gain with no Pain: Efficient Kernel-PCA by Nystr"om Sampling

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2019.

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

- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)
- [Nonparametric estimation of continuous DPPs with kernel methods](https://mlsanity.com/paper/2106.14210/) (2021)
- [Optimal Transport for Kernel Gaussian Mixture Models](https://mlsanity.com/paper/2310.18586/) (2023)

## Abstract (arXiv)

In this paper, we propose and study a Nystr"om based approach to efficient large scale kernel principal component analysis (PCA). The latter is a natural nonlinear extension of classical PCA based on considering a nonlinear feature map or the corresponding kernel. Like other kernel approaches, kernel PCA enjoys good mathematical and statistical properties but, numerically, it scales poorly with the sample size. Our analysis shows that Nystr"om sampling greatly improves computational efficiency without incurring any loss of statistical accuracy. While similar effects have been observed in supervised learning, this is the first such result for PCA. Our theoretical findings, which are also illustrated by numerical results, are based on a combination of analytic and concentration of measure techniques. Our study is more broadly motivated by the question of understanding the interplay between statistical and computational requirements for learning.