  We propose a new technique for constructing low-rank approximations of
matrices that arise in kernel methods for machine learning. Our approach pairs
a novel automatically constructed analytic expansion of the underlying kernel
function with a data-dependent compression step to further optimize the
approximation. This procedure works in linear time and is applicable to any
isotropic kernel. Moreover, our method accepts the desired error tolerance as
input, in contrast to prevalent methods which accept the rank as input.
Experimental results show our approach compares favorably to the commonly used
Nystrom method with respect to both accuracy for a given rank and computational
time for a given accuracy across a variety of kernels, dimensions, and
datasets. Notably, in many of these problem settings our approach produces
near-optimal low-rank approximations. We provide an efficient open-source
implementation of our new technique to complement our theoretical developments
and experimental results.
