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 逼近以及核矩阵的逼近等等，特别适用于机器学习和科学计算。