Journal
INFORMATION PROCESSING LETTERS
Volume 109, Issue 3, Pages 179-182Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.ipl.2008.09.028
Keywords
Algorithms; Matrix-vector multiplication; Mailman algorithm; Random projections
Categories
Funding
- AFOSR
- NGA
Ask authors/readers for more resources
Given an m x n matrix A we are interested in applying it to a real vector x is an element of 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 0(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. (C) 2008 Elsevier B.V. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available