Randomized methods for computing low-rank approximations of matrices
Randomized methods for computing low-rank approximations of matrices
复制标题
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
P. Martinsson;N. Halko
中科院分区：
文献类型：
--
作者：
P. Martinsson;N. Halko
随机抽样技术最近被证明能够有效地解决线性代数中的许多标准问题，并使计算规模比以前可能的要大得多。新算法是自下而上设计的，以便在通信成本是主要限制的现代计算环境中运行良好。在极端情况下，算法甚至可以在完全不存储矩阵的流媒体环境中工作，每个元素只能看到一次。本文描述了一套快速构造矩阵低阶逼近的随机化技术。这些算法是在模块化框架中提出的，该框架首先通过随机抽样计算矩阵范围的近似值。其次，将矩阵投影到近似范围，并进行因式分解(SVD、QR、LU等)。通过经典确定论方法的变化来计算所得到的低阶矩阵的。给出了理论上的性能界限。特别注意矩阵不适合单个工作站上的RAM的超大规模计算。对于原始矩阵必须存储在核外但近似因子适合在RAM中的情况，开发了算法。提供了对数据集执行主成分分析的数值例子，该数据集非常大，以至于只有不到百分之一的数据集可以放入标准膝上型计算机的RAM中。此外，本文还提出了一种计算降阶奇异值分解的并行随机化方案。通过并行和分配随机采样阶段和近似因式分解中的因子处理，该方法需要每个节点独立于输入矩阵的两个维度的存储量。数值实验是在亚马逊弹性计算云中的Hadoop计算机集群上进行的，总内核高达。最后，我们在超大稀疏矩阵上直接比较了随机化算法和经典Lanczos方法的性能和精度，证实了随机化方法在这种环境下的优越性。
Randomized sampling techniques have recently proved capable of efficiently solving many standard problems in linear algebra, and enabling computations at scales far larger than what was previously possible. The new algorithms are designed from the bottom up to perform well in modern computing environments where the expense of communication is the primary constraint. In extreme cases, the algorithms can even be made to work in a streaming environment where the matrix is not stored at all, and each element can be seen only once. The dissertation describes a set of randomized techniques for rapidly constructing a low-rank approximation to a matrix. The algorithms are presented in a modular framework that first computes an approximation to the range of the matrix via randomized sampling. Secondly, the matrix is projected to the approximate range, and a factorization (SVD, QR, LU, etc.) of the resulting low-rank matrix is computed via variations of classical deterministic methods. Theoretical performance bounds are provided. Particular attention is given to very large scale computations where the matrix does not fit in RAM on a single workstation. Algorithms are developed for the case where the original matrix must be stored out-of-core but where the factors of the approximation fit in RAM. Numerical examples are provided that perform Principal Component Analysis of a data set that is so large that less than one hundredth of it can fit in the RAM of a standard laptop computer. Furthermore, the dissertation presents a parallelized randomized scheme for computing a reduced rank Singular Value Decomposition. By parallelizing and distributing both the randomized sampling stage and the processing of the factors in the approximate factorization, the method requires an amount of memory per node which is independent of both dimensions of the input matrix. Numerical experiments are performed on Hadoop clusters of computers in Amazon's Elastic Compute Cloud with up to 64 total cores. Finally, we directly compare the performance and accuracy of the randomized algorithm with the classical Lanczos method on extremely large, sparse matrices and substantiate the claim that randomized methods are superior in this environment.