Approximating matrix multiplication for pattern recognition tasks

Many pattern recognition tasks, including estimation, classification, and t he finding of similar objects, make use of linear models. The fundamental o peration in such tasks is the computation of the dot product between a quer y vector and a large database of instance vectors. Often we are interested primarily in those instance vectors which have high dot products with the q uery. We present a random sampling based algorithm that enables us to ident ify, for any given query vector, those instance vectors which have large do t products, while avoiding explicit computation of all dot products. We pro vide experimental results that demonstrate considerable speedups for text r etrieval tasks. Our approximate matrix multiplication algorithm is applicab le to products of k greater than or equal to 2 matrices and is of independe nt interest. Our theoretical and experimental analysis demonstrates that in many scenarios, our method dominates standard matrix multiplication, (C) 1 999 Academic Press.