Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication

作者：Petros Drineas, Ravi Kannan, Michael W. Mahoney · 发表于：SIAM Journal on Computing · 年份：2006 · DOI：10.1137/s0097539704442684 · 被引用次数：514 · 研究领域：Matrix Theory and Algorithms、Markov Chains and Monte Carlo Methods、Tensor decomposition and applications

Motivated by applications in which the data may be formulated as a matrix, we consider algorithms for several common linear algebra problems. These algorithms make more efficient use of computational resources, such as the computation time, random access memory (RAM), and the number of passes over the data, than do previously known algorithms for these problems. In this paper, we devise two algorithms for the matrix multiplication problem. Suppose A and B (which are $m\times n$ and $n\times p$, respectively) are the two input matrices. In our main algorithm, we perform c independent trials, where in each trial we randomly sample an element of $\{ 1,2,\ldots, n\}$ with an appropriate probability distribution ${\cal P}$ on $\{ 1,2,\ldots, n\}$. We form an $m\times c$ matrix C consisting of the sampled columns of A, each scaled appropriately, and we form a $c\times n$ matrix R using the corresponding rows of B, again scaled appropriately. The choice of ${\cal P}$ and the column and row scaling are crucial features of the algorithm. When these are chosen judiciously, we show that $CR$ is a good approximation to $AB$. More precisely, we show that $$ \left\|AB-CR\right\|_F = O(\left\|A\right\|_F \left\|B\right\|_F /\sqrt c) , $$ where $\|\cdot\|_F$ denotes the Frobenius norm, i.e., $\|A\|^2_F=\sum_{i,j}A_{ij}^2$. This algorithm can be implemented without storing the matrices A and B in RAM, provided it can make two passes over the matrices stored in external memory and use $O(c(m+n...