How to Fake Multiply by a Gaussian Matrix
arXiv:1606.05732
Abstract
Have you ever wanted to multiply an matrix , with , on the left by an 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 matrix , for which one can compute in only time, for which the total variation distance between the distributions and is as small as desired, i.e., less than any positive constant. Here denotes the number of non-zero entries of . Assuming , this is a significant savings over the naïve time to compute . Moreover, since the total variation distance is small, we can provably use in place of in any application and have the same guarantees as if we were using , up to a small positive constant in error probability. We apply this transform to nonnegative matrix factorization (NMF) and support vector machines (SVM).
References in corpus (6)
- Fast and Robust Recursive Algorithms for Separable Nonnegative Matrix Factorization
- Fast Conical Hull Algorithms for Near-separable Non-negative Matrix Factorization
- Factoring nonnegative matrices with linear programs
- Using Underapproximations for Sparse Nonnegative Matrix Factorization
- Compressed Nonnegative Matrix Factorization is Fast and Accurate
- Scalable methods for nonnegative matrix factorizations of near-separable tall-and-skinny matrices