Streaming Kernel PCA with O(√(n)) Random Features

2018/08/02 by Ullah, Enayat, Mianjy, Poorya, Marinov, Teodor V. +1 · 2 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1808.00934

Abstract

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/ε²) sample complexity. Furthermore, we give a memory efficient streaming algorithm based on classical Oja's algorithm that achieves this rate.

Cited by

• Towards an Explainable Comparison and Alignment of Feature Embeddings
• Kernel PCA for Out-of-Distribution Detection: Non-Linear Kernel Selections and Approximations

Related

• Streaming Kernel Principal Component Analysis
• Streaming Kernel PCA Algorithm With Small Space
• Rivalry of Two Families of Algorithms for Memory-Restricted Streaming\n PCA
• History PCA: A New Algorithm for Streaming PCA
• Approximate Kernel PCA Using Random Features: Computational vs.\n Statistical Trade-off