In this era of large-scale data, distributed systems built on top of clusters
of commodity hardware provide cheap and reliable storage and scalable
processing of massive data. Here, we review recent work on developing and
implementing randomized matrix algorithms in large-scale parallel and
distributed environments. Randomized algorithms for matrix problems have
received a great deal of attention in recent years, thus far typically either
in theory or in machine learning applications or with implementations on a
single machine. Our main focus is on the underlying theory and practical
implementation of random projection and random sampling algorithms for very
large very overdetermined (i.e., overconstrained) $\ell_1$ and $\ell_2$
regression problems. Randomization can be used in one of two related ways:
either to construct sub-sampled problems that can be solved, exactly or
approximately, with traditional numerical methods; or to construct
preconditioned versions of the original full problem that are easier to solve
with traditional iterative algorithms. Theoretical results demonstrate that in
near input-sparsity time and with only a few passes through the data one can
obtain very strong relative-error approximate solutions, with high probability.
Empirical results highlight the importance of various trade-offs (e.g., between
the time to construct an embedding and the conditioning quality of the
embedding, between the relative importance of computation versus communication,
etc.) and demonstrate that $\ell_1$ and $\ell_2$ regression problems can be
solved to low, medium, or high precision in existing distributed systems on up
to terabyte-sized data.

在大规模数据时代，分布式系统为处理海量数据提供了可靠的、实惠的存储和可扩展的处理，本文主要介绍发展和实施随机矩阵算法在大规模并行和分布式环境中的最新工作，着重讨论随机投影和随机采样算法在极度超定的 l1 和 l2 回归问题中的实际应用和理论基础。

在并行和分布式环境中实现随机矩阵算法

Implementing Randomized Matrix Algorithms in Parallel and Distributed  Environments

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.

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