Abstract

Have you ever wanted to multiply an n × d matrix X, with n d, on the left by an m × n matrix 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 time, for which the total variation distance between the distributions T · X and · 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 this is a significant savings over the na¨ıve O(nnz(X)m) time to compute · X. Moreover, since the total variation distance is small, we can provably use T · X in place of · X in any application and have the same guarantees as if we were using · X, up to a small positive constant in erro probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).