# Streaming Kernel Principal Component Analysis

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2015.

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

- [Towards a Scalable Reference-Free Evaluation of Generative Models](https://mlsanity.com/paper/2407.02961/) (2024)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [Incremental Ensemble Gaussian Processes](https://mlsanity.com/paper/2110.06777/) (2021)
- [Towards an Explainable Comparison and Alignment of Feature Embeddings](https://mlsanity.com/paper/2506.06231/) (2025)
- [Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpoint](https://mlsanity.com/paper/2310.18593/) (2023)
- [KODA: Contrastive Representation Comparison and Alignment for Vision-Language Foundation Models](https://mlsanity.com/paper/2606.04180/) (2026)
- [Online Kernel Sliced Inverse Regression](https://mlsanity.com/paper/2301.09516/) (2023)
- [Data eccentricity, asymptotics of Gaussian RBF reproducing kernel Hilbert space, and kernel PCA](https://mlsanity.com/paper/2607.21823/) (2026)

## Abstract (arXiv)

Kernel principal component analysis (KPCA) provides a concise set of basis vectors which capture non-linear structures within large data sets, and is a central tool in data analysis and learning. To allow for non-linear relations, typically a full n × n kernel matrix is constructed over n data points, but this requires too much space and time for large values of n. Techniques such as the Nystr"om method and random feature maps can help towards this goal, but they do not explicitly maintain the basis vectors in a stream and take more space than desired. We propose a new approach for streaming KPCA which maintains a small set of basis elements in a stream, requiring space only logarithmic in n, and also improves the dependence on the error parameter. Our technique combines together random feature maps with recent advances in matrix sketching, it has guaranteed spectral norm error bounds with respect to the original kernel matrix, and it compares favorably in practice to state-of-the-art approaches.