This survey describes probabilistic algorithms for linear algebra
computations, such as factorizing matrices and solving linear systems. It
focuses on techniques that have a proven track record for real-world problem
instances. The paper treats both the theoretical foundations of the subject and
the practical computational issues.
Topics covered include norm estimation; matrix approximation by sampling;
structured and unstructured random embeddings; linear regression problems;
low-rank approximation; subspace iteration and Krylov methods; error estimation
and adaptivity; interpolatory and CUR factorizations; Nystr\"om approximation
of positive-semidefinite matrices; single view ("streaming") algorithms; full
rank-revealing factorizations; solvers for linear systems; and approximation of
kernel matrices that arise in machine learning and in scientific computing.

本文介绍了一些概率算法，来完成线性代数计算，如矩阵分解和线性系统求解，覆盖了在实际问题中得到证明的技术和理论知识，包括规范估计，采样的矩阵逼近，线性回归问题，低秩逼近，亚空间迭代和 Krylov 方法，误差估计和自适应性，插值和 CUR 分解，Nystrom 逼近以及核矩阵的逼近等等，特别适用于机器学习和科学计算。

随机数值线性代数：基础与算法

Randomized Numerical Linear Algebra: Foundations & Algorithms

We propose a novel class of kernels to alleviate the high computational cost
of large-scale nonparametric learning with kernel methods. The proposed kernel
is defined based on a hierarchical partitioning of the underlying data domain,
where the Nystr\"om method (a globally low-rank approximation) is married with
a locally lossless approximation in a hierarchical fashion. The kernel
maintains (strict) positive-definiteness. The corresponding kernel matrix
admits a recursively off-diagonal low-rank structure, which allows for fast
linear algebra computations. Suppressing the factor of data dimension, the
memory and arithmetic complexities for training a regression or a classifier
are reduced from $O(n^2)$ and $O(n^3)$ to $O(nr)$ and $O(nr^2)$, respectively,
where $n$ is the number of training examples and $r$ is the rank on each level
of the hierarchy. Although other randomized approximate kernels entail a
similar complexity, empirical results show that the proposed kernel achieves a
matching performance with a smaller $r$. We demonstrate comprehensive
experiments to show the effective use of the proposed kernel on data sizes up
to the order of millions.

本文提出了一个基于层次划分的新型核函数，可以减轻用于核方法的大规模非参数学习的计算复杂度并且在实验中提高了表现。