  Nystr\"om approximation is a fast randomized method that rapidly solves
kernel ridge regression (KRR) problems through sub-sampling the n-by-n
empirical kernel matrix appearing in the objective function. However, the
performance of such a sub-sampling method heavily relies on correctly
estimating the statistical leverage scores for forming the sampling
distribution, which can be as costly as solving the original KRR. In this work,
we propose a linear time (modulo poly-log terms) algorithm to accurately
approximate the statistical leverage scores in the stationary-kernel-based KRR
with theoretical guarantees. Particularly, by analyzing the first-order
condition of the KRR objective, we derive an analytic formula, which depends on
both the input distribution and the spectral density of stationary kernels, for
capturing the non-uniformity of the statistical leverage scores. Numerical
experiments demonstrate that with the same prediction accuracy our method is
orders of magnitude more efficient than existing methods in selecting the
representative sub-samples in the Nystr\"om approximation.
