Skip to main content

Approximate Kernal PCA: Computation vs. Statistical Trade-Off

Date:
Location:
MDS 220
Speaker(s) / Presenter(s):
Dr. Bharath Sriperumbudur

Abstract: Kernel principal component analysis (KPCA) is a popular non-linear dimensionality reduction technique, which generalizes classical linear PCA by finding functions in a reproducing kernel Hilbert space (RKHS) such that the function evaluation at a random variable X has maximum variance. Despite its popularity, kernel PCA suffers from poor scalability in big data scenarios as it involves solving a n x n eigensystem leading to a computational complexity of O(n^3) with n being the number of samples. To address this issue, in this work, we consider a random feature approximation to kernel PCA which requires solving an m x m eigenvalue problem and therefore has a computational complexity of O(m^3+nm^2), implying that the approximate method is computationally efficient if m<n with m being the number of random features. The goal of this work is to investigate the trade-off between computational and statistical behaviors of approximate KPCA, i.e., whether the computational gain is achieved at the cost of statistical efficiency. We show that the approximate KPCA is both computationally and statistically efficient compared to KPCA in terms of the error associated with reconstructing a kernel function based on its projection onto the corresponding eigenspaces. Depending on the eigenvalue decay behavior of the covariance operator, we show that only n^{2/3} features (polynomial decay) or \sqrt{n} features (exponential decay) are needed to match the statistical performance of KPCA, which means without losing statistically, approximate KPCA has a computational complexity of O(n^2) or O(n^{3/2}) depending on the eigenvalue decay behavior.

Event Series: