Randomized algorithms for very large matrix problems have received a great
deal of attention in recent years. Much of this work was motivated by problems
in large-scale data analysis, and this work was performed by individuals from
many different research communities. This monograph will provide a detailed
overview of recent work on the theory of randomized matrix algorithms as well
as the application of those ideas to the solution of practical problems in
large-scale data analysis. An emphasis will be placed on a few simple core
ideas that underlie not only recent theoretical advances but also the
usefulness of these tools in large-scale data applications. Crucial in this
context is the connection with the concept of statistical leverage. This
concept has long been used in statistical regression diagnostics to identify
outliers; and it has recently proved crucial in the development of improved
worst-case matrix algorithms that are also amenable to high-quality numerical
implementation and that are useful to domain scientists. Randomized methods
solve problems such as the linear least-squares problem and the low-rank matrix
approximation problem by constructing and operating on a randomized sketch of
the input matrix. Depending on the specifics of the situation, when compared
with the best previously-existing deterministic algorithms, the resulting
randomized algorithms have worst-case running time that is asymptotically
faster; their numerical implementations are faster in terms of clock-time; or
they can be implemented in parallel computing environments where existing
numerical algorithms fail to run at all. Numerous examples illustrating these
observations will be described in detail.

本文详细介绍了随机矩阵算法理论的最新进展以及这些思想在大规模数据分析实际问题求解中的应用，重点放在一些简单的核心思想上，这些思想不仅支撑了最近的理论发展，也使得这些工具在大规模数据应用中非常有用；本文特别关注了统计上的杠杆作用这一概念，它不仅可以用于识别异常值，而且还可以帮助开发更好的矩阵算法，这些方法可以解决诸如线性最小二乘问题和低秩矩阵逼近问题。与之前最佳确定性算法相比，最终得到的随机算法的最坏运行时间渐近更快；它们的数值实现在时间上更快；或者它们可以在现有数值算法无法运行的并行计算环境中运行。