About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ICML 2016
Conference paper
How to fake multiply by a Gaussian matrix
Abstract
Have you ever wanted to multiply an n x d matrix X, with n d, on the left by an m x n matrix G of i.i.d. Gaussian random variables, hut could not afford to do it because it was too slow? In this work we propose a new randomized m x n matrix T, for which one can compute T X in only 0(nnz(X)) + 6(m1.5 - d3) time, for which the total variation distance between the distributions T ▪ X and G • A' is as small as desired, i.e., less than any positive constant. Here nnz(A) denotes the number of non-zero entries of X. Assuming nnz(X) rn1 5 - d3, this is a significant savings over the naive 0(nnz(X)m) time to compute G • X. Moreover, since the total variation distance is small, we can provably use T ▪ X in place of G ▪ X in any application and have the same guarantees as if we were using G • X, up to a small positive constant in error probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).