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. Rec
本文提出了一种新的随机算法，该算法采用特别偏向采样的方法，使误差最小化，可以在光谱范数下利用输入稀疏性生成 M 的秩 - r 逼近，并具有 better dependence on error ε，是一种高度可并行化的优化方法。此外，本论文探讨了计算两个给定矩阵的积的小秩逼近的新方法和小通信开销的改进算法。