Upper and Lower Bounds on the Performance of Kernel PCA
This work provides a better theoretical understanding of KPCA's efficiency, which is important for researchers and practitioners using this dimension reduction technique, by clarifying its information capture capabilities.
This paper establishes theoretical upper and lower bounds on the performance of Kernel PCA (KPCA), quantifying the amount of information captured by KPCA using empirical eigenvalues and a new variance notion. The results demonstrate that fast convergence rates are achievable for a common class of kernels.
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.