The Mailman algorithm: A note on matrix--vector multiplication Export

@article{citeulike:5973265, abstract = {Given an mxn matrix A we are interested in applying it to a real vector x@?R^n in less than the straightforward O(mn) time. For an exact deterministic computation at the very least all entries in A must be accessed, requiring O(mn) operations and matching the running time of naively applying A to x. However, we claim that if the matrix contains only a constant number of distinct values, then reading the matrix once in O(mn) steps is sufficient to preprocess it such that any subsequent application to vectors requires only O(mn/log(max{m,n})) operations. Algorithms for matrix-vector multiplication over finite fields, which save a log factor, have been known for many years. Our contribution is unique in its simplicity and in the fact that it applies also to real valued vectors. Using our algorithm improves on recent results for dimensionality reduction. It gives the first known random projection process exhibiting asymptotically optimal running time. The mailman algorithm is also shown to be useful (faster than naive) even for small matrices.}, address = {Amsterdam, The Netherlands, The Netherlands}, author = {Liberty, Edo and Zucker, Steven W.}, citeulike-article-id = {5973265}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1478699}, citeulike-linkout-1 = {http://dx.doi.org/10.1016/j.ipl.2008.09.028}, doi = {10.1016/j.ipl.2008.09.028}, issn = {0020-0190}, journal = {Inf. Process. Lett.}, keywords = {matrix}, number = {3}, pages = {179--182}, posted-at = {2009-10-20 08:31:18}, priority = {2}, publisher = {Elsevier North-Holland, Inc.}, title = {The Mailman algorithm: A note on matrix--vector multiplication}, url = {http://dx.doi.org/10.1016/j.ipl.2008.09.028}, volume = {109}, year = {2009} }

TY - JOUR ID - citeulike:5973265 L3 - citeulike-article-id:5973265 N2 - Given an mxn matrix A we are interested in applying it to a real vector x@?R^n in less than the straightforward O(mn) time. For an exact deterministic computation at the very least all entries in A must be accessed, requiring O(mn) operations and matching the running time of naively applying A to x. However, we claim that if the matrix contains only a constant number of distinct values, then reading the matrix once in O(mn) steps is sufficient to preprocess it such that any subsequent application to vectors requires only O(mn/log(max{m,n})) operations. Algorithms for matrix-vector multiplication over finite fields, which save a log factor, have been known for many years. Our contribution is unique in its simplicity and in the fact that it applies also to real valued vectors. Using our algorithm improves on recent results for dimensionality reduction. It gives the first known random projection process exhibiting asymptotically optimal running time. The mailman algorithm is also shown to be useful (faster than naive) even for small matrices. IS - 3 JF - Inf. Process. Lett. SN - 0020-0190 AD - Amsterdam, The Netherlands, The Netherlands EP - 182 TI - The Mailman algorithm: A note on matrix--vector multiplication PB - Elsevier North-Holland, Inc. VL - 109 SP - 179 KW - matrix AU - Liberty, Edo AU - Zucker, Steven PY - 2009/// UR - http://dx.doi.org/10.1016/j.ipl.2008.09.028 ER -