  Kernel methods are powerful learning methodologies that allow to perform
non-linear data analysis. 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. The analysis hinges on Bernstein-type
inequalities for the operator and Hilbert-Schmidt norms of a self-adjoint
Hilbert-Schmidt operator-valued U-statistics, which are of independent
interest.
