mlsanityData to 7 Oct 2026

Streaming Kernel PCA with tildeO(√n) Random Features

arXiv 1808.00934 ↗First posted 2 Aug 2018cs.LG cs.AI stat.MLcited by 11

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 1; 2023: 2; 2024: 1; 2025: 2; 2026: 2.

11 papers.

  1. 2022Contrastive Learning Can Find An Optimal Basis For Approximately View-Invariant Functionscited by 32
  2. 2024Towards a Scalable Reference-Free Evaluation of Generative Modelscited by 25
  3. 2021Generalization Bounds for Sparse Random Feature Expansionscited by 22
  4. 2021Learning to Forecast Dynamical Systems from Streaming Datacited by 17
  5. 2021Statistical Optimality and Computational Efficiency of Nystr"om Kernel PCAcited by 10
  6. 2023Random Fourier Signature Featurescited by 9
  7. 2025Towards an Explainable Comparison and Alignment of Feature Embeddingscited by 9
  8. 2023Fair Streaming Principal Component Analysis: Statistical and Algorithmic Viewpointcited by 5
  9. 2026KODA: Contrastive Representation Comparison and Alignment for Vision-Language Foundation Modelscited by 2
  10. 2025Kernel PCA for Out-of-Distribution Detection: Non-Linear Kernel Selection and Approximationcited by 1
  11. 2026Online Supervised Dimension Reduction with Random Features: Diagnostics and Computational Trade-offscited by 0