How to Fake Multiply by a Gaussian Matrix

Have you ever wanted to multiply an n × d matrix X, with n gg d, on the left by an m × n matrix tilde G of i.i.d. Gaussian random variables, but could not afford to do it because it was too slow? In this work we propose a new randomized m × n matrix T, for which one can compute T · X in only O(nnz(X)) + tilde O(m2 · d3) time, for which the total variation distance between the distributions T · X and tilde G · X is as small as desired, i.e., less than any positive constant. Here nnz(X) denotes the number of non-zero entries of X. Assuming nnz(X) gg m2 · d3, this is a significant savings over the na"ive O(nnz(X) m) time to compute tilde G · X. Moreover, since the total variation distance is small, we can provably use T · X in place of tilde G · X in any application and have the same guarantees as if we were using tilde 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).