The Mailman Algorithm: A Note on Matrix Vector Multiplication

Given an m x n matrix A we are interested in applying it to a real vector x epsilon Rn in less then the straightforward Omn time. For an exact, deterministic computation at the very least all entrees in A must be accessed, requiring Omn 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 Omn steps is sufficient to preprocess it such that any subsequent application to vectors requires only Omn logmaxm,ng operations. Theoretically our algorithm can improve on recent results for dimensionality reduction and practically it is useful faster even for small matrices.