Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication

摘要: Motivated by applications in which the data may be formulated as a matrix, we consider algorithms for several common linear algebra problems. These make more efficient use of computational resources, such computation time, random access memory (RAM), and number passes over data, than do previously known these In this paper, devise two matrix multiplication problem. Suppose $A$ $B$ (which are $m\times n$ $n\times p$, respectively) input matrices. our main algorithm, perform $c$ independent trials, where each trial randomly sample an element $\{ 1,2,\ldots, n\}$ with appropriate probability distribution ${\cal P}$ on n\}$. We form c$ $C$ consisting sampled columns $A$, scaled appropriately, $c\times $R$ using corresponding rows $B$, again appropriately. The choice column row scaling crucial features algorithm. When chosen judiciously, show that $CR$ is good approximation to $AB$. More precisely, $$ \left\|AB-CR\right\|_F = O(\left\|A\right\|_F \left\|B\right\|_F /\sqrt c) , $\|\cdot\|_F$ denotes Frobenius norm, i.e., $\|A\|^2_F=\sum_{i,j}A_{ij}^2$. This algorithm can implemented without storing matrices RAM, provided it stored external $O(c(m+n+p))$ additional RAM construct $R$. then present second similar spirit addition, model (the pass-efficient model) efficiency other approximate studied argue well suited many involving massive sets. model, scarce resources space time required presented any order entries (and not just or order), case where, e.g., has been written multiple agents. sparse representation, only nonzero written.