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).