  Kernel methods provide an elegant framework for developing nonlinear learning
algorithms from simple linear methods. Though these methods have superior
empirical performance in several real data applications, their usefulness is
inhibited by the significant computational burden incurred in large sample
situations. Various approximation schemes have been proposed in the literature
to alleviate these computational issues, and the approximate kernel machines
are shown to retain the empirical performance. However, the theoretical
properties of these approximate kernel machines are less well understood. In
this work, we theoretically study the trade-off between computational
complexity and statistical accuracy in Nystr\"om approximate kernel principal
component analysis (KPCA), wherein we show that the Nystr\"om approximate KPCA
matches the statistical performance of (non-approximate) KPCA while remaining
computationally beneficial. Additionally, we show that Nystr\"om approximate
KPCA outperforms the statistical behavior of another popular approximation
scheme, the random feature approximation, when applied to KPCA.
