Importance Sampling for a Monte Carlo Matrix Multiplication Algorithm, with Application to Information Retrieval
Sylvester David Eriksson-Bique, Mary Solbrig, Michael Stefanelli, Sarah Warkentin, Ralph Abbey, Ilse C. F. Ipsen · SIAM Journal on Scientific Computing · 2011
We perform importance sampling for a randomized matrix multiplication algorithm by Drineas, Kannan, and Mahoney and derive probabilities that minimize the expected value (with regard to the distributions of the matrix elements) of the variance. We compare these optimized probabilities with uniform probabilities and derive conditions under which the actual variance of the optimized probabilities is lower. Numerical experiments with query matching in information retrieval applications illustrate that the optimized probabilities produce more accurate matchings than the uniform probabilities and that they can also be computed efficiently.