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 回归问题中的实际应用和理论基础。