# How to Fake Multiply by a Gaussian Matrix

arXiv: https://arxiv.org/abs/1606.05732 · HTML: https://mlsanity.com/paper/1606.05732/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2016.

## Built on by (most cited first, 1 of 1)

- [Estimating leverage scores via rank revealing methods and randomization](https://mlsanity.com/paper/2105.11004/) (2021)

## Abstract (arXiv)

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