  Common kernel ridge regression is expensive in memory allocation and
computation time. This paper addresses low rank approximations and surrogates
for kernel ridge regression, which bridge these difficulties. The fundamental
contribution of the paper is a lower bound on the rank of the low dimensional
approximation, which is required such that the prediction power remains
reliable. The bound relates the effective dimension with the largest
statistical leverage score. We characterize the effective dimension and its
growth behavior with respect to the regularization parameter by involving the
regularity of the kernel. This growth is demonstrated to be asymptotically
logarithmic for suitably chosen kernels, justifying low-rank approximations as
the Nystr\"om method.
