Upper and Lower Bounds on the Performance of Kernel PCA
arXiv:2012.10369
Abstract
Principal Component Analysis (PCA) is a popular method for dimension reduction and has attracted an unfailing interest for decades. More recently, kernel PCA (KPCA) has emerged as an extension of PCA but, despite its use in practice, a sound theoretical understanding of KPCA is missing. We contribute several lower and upper bounds on the efficiency of KPCA, involving the empirical eigenvalues of the kernel Gram matrix and new quantities involving a notion of variance. These bounds show how much information is captured by KPCA on average and contribute a better theoretical understanding of its efficiency. We demonstrate that fast convergence rates are achievable for a widely used class of kernels and we highlight the importance of some desirable properties of datasets to ensure KPCA efficiency.
arXiv comment16 pages
References in corpus (6)
- A Note on the PAC Bayesian Theorem
- Meta-Learning by Adjusting Priors Based on Extended PAC-Bayes Theory
- A Simple and Fast Algorithm for L1-norm Kernel PCA
- PAC-Bayes under potentially heavy tails
- PAC-Bayes unleashed: generalisation bounds with unbounded losses
- A PAC-Bayesian Perspective on Structured Prediction with Implicit Loss Embeddings