Fast Monte-Carlo algorithms for approximate matrix multiplication

摘要: Given an m ? n matrix A and p B, we present 2 simple intuitive algorithms to compute approximation P the product with provable bounds for norm of "error matrix" - B. Both run in 0(mp+mn+np) time. In both algorithms, randomly pick s = 0(1) columns form S corresponding rows B R. After scaling R, multiply them together obtain our P. The choice probability distribution use picking are crucial features which enable us fairly elementary proofs error bounds. Our first algorithm can be implemented without storing matrices Random Access Memory, provided make two passes through (stored external memory). second has a smaller bound on 2-norm matrix, but requires storage RAM. We also fast that "describes" as sum rank one if AT.