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.

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

矩阵和数据的随机算法

Randomized algorithms for matrices and data

Recent work in theoretical computer science and scientific computing has
focused on nearly-linear-time algorithms for solving systems of linear
equations. While introducing several novel theoretical perspectives, this work
has yet to lead to practical algorithms. In an effort to bridge this gap, we
describe in this paper two related results. Our first and main result is a
simple algorithm to approximate the solution to a set of linear equations
defined by a Laplacian (for a graph $G$ with $n$ nodes and $m \le n^2$ edges)
constraint matrix. The algorithm is a non-recursive algorithm; even though it
runs in $O(n^2 \cdot \polylog(n))$ time rather than $O(m \cdot polylog(n))$
time (given an oracle for the so-called statistical leverage scores), it is
extremely simple; and it can be used to compute an approximate solution with a
direct solver. In light of this result, our second result is a straightforward
connection between the concept of graph resistance (which has proven useful in
recent algorithms for linear equation solvers) and the concept of statistical
leverage (which has proven useful in numerically-implementable randomized
algorithms for large matrix problems and which has a natural data-analytic
interpretation).

本文主要介绍了一种针对解决 Laplacian 约束矩阵定义的线性方程组的简单算法，可用于计算近似解并具有直接求解器，同时介绍了图电阻概念与统计杠杆概念之间的联系。