Most kernel-based methods, such as kernel or Gaussian process regression,
kernel PCA, ICA, or $k$-means clustering, do not scale to large datasets,
because constructing and storing the kernel matrix $\mathbf{K}_n$ requires at
least $\mathcal{O}(n^2)$ time and space for $n$ samples. Recent works show that
sampling points with replacement according to their ridge leverage scores (RLS)
generates small dictionaries of relevant points with strong spectral
approximation guarantees for $\mathbf{K}_n$. The drawback of RLS-based methods
is that computing exact RLS requires constructing and storing the whole kernel
matrix. In this paper, we introduce SQUEAK, a new algorithm for kernel
approximation based on RLS sampling that sequentially processes the dataset,
storing a dictionary which creates accurate kernel matrix approximations with a
number of points that only depends on the effective dimension $d_{eff}(\gamma)$
of the dataset. Moreover since all the RLS estimations are efficiently
performed using only the small dictionary, SQUEAK is the first RLS sampling
algorithm that never constructs the whole matrix $\mathbf{K}_n$, runs in linear
time $\widetilde{\mathcal{O}}(nd_{eff}(\gamma)^3)$ w.r.t. $n$, and requires
only a single pass over the dataset. We also propose a parallel and distributed
version of SQUEAK that linearly scales across multiple machines, achieving
similar accuracy in as little as
$\widetilde{\mathcal{O}}(\log(n)d_{eff}(\gamma)^3)$ time.

介绍了一种名为 SQUEAK 的基于 RLS 抽样的核逼近算法，可以在线性时间内生成精确的核矩阵近似，并且只需处理数据集一次；同时还提出了一个并行和分布式版本，可在对数时间内线性扩展到多台机器上。