# Streaming Kernel PCA with tildeO(√n) Random Features

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Aug 2018.

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

- [Contrastive Learning Can Find An Optimal Basis For Approximately View-Invariant Functions](https://mlsanity.com/paper/2210.01883/) (2022)
- [Towards a Scalable Reference-Free Evaluation of Generative Models](https://mlsanity.com/paper/2407.02961/) (2024)
- [Generalization Bounds for Sparse Random Feature Expansions](https://mlsanity.com/paper/2103.03191/) (2021)
- [Learning to Forecast Dynamical Systems from Streaming Data](https://mlsanity.com/paper/2109.09703/) (2021)
- [Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCA](https://mlsanity.com/paper/2105.08875/) (2021)
- [Towards an Explainable Comparison and Alignment of Feature Embeddings](https://mlsanity.com/paper/2506.06231/) (2025)
- [Random Fourier Signature Features](https://mlsanity.com/paper/2311.12214/) (2023)
- [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)
- [Kernel PCA for Out-of-Distribution Detection: Non-Linear Kernel Selection and Approximation](https://mlsanity.com/paper/2505.15284/) (2025)
- [Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offs](https://mlsanity.com/paper/2609.20454/) (2026)

## Abstract (arXiv)

We study the statistical and computational aspects of kernel principal component analysis using random Fourier features and show that under mild assumptions, O(√n log n) features suffices to achieve O(1/ε2) sample complexity. Furthermore, we give a memory efficient streaming algorithm based on classical Oja's algorithm that achieves this rate.