Title: Approximate Kernel PCA Using Random Features: Computational vs. Statistical Trade-off,
Abstract: Kernel methods are powerful learning methodologies that provide a simple way
to construct nonlinear algorithms from linear ones. Despite their popularity,
they suffer from poor scalability in big data scenarios. Various approximation
methods, including random feature approximation have been proposed to alleviate
the problem. However, the statistical consistency of most of these approximate
kernel methods is not well understood except for kernel ridge regression
wherein it has been shown that the random feature approximation is not only
computationally efficient but also statistically consistent with a minimax
optimal rate of convergence. In this paper, we investigate the efficacy of
random feature approximation in the context of kernel principal component
analysis (KPCA) by studying the trade-off between computational and statistical
behaviors of approximate KPCA. 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. We also investigate their statistical
behaviors in terms of the convergence of corresponding eigenspaces wherein we
show that only $\sqrt{n}$ features are required to match the performance of
KPCA and if fewer than $\sqrt{n}$ features are used, then approximate KPCA has
a worse statistical behavior than that of KPCA.