You know what happens when Random Matrices Are Too Damn Large and so yuuuggge, they cannot be held in memory nor processed ? well, the answer is to fake them till you make it. I like how the authors used the phase transition diagrams to show the similarity of two algorithms.
How to Fake Multiply by a Gaussian Matrix by Michael Kapralov, Vamsi K. Potluru, David P. Woodruff
Have you ever wanted to multiply an
n×dmatrix X, with n≫d, on the left by an m×nmatrix 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×nmatrix T, for which one can compute T⋅Xin only O(nnz(X))+O~(m1.5⋅d3)time, for which the total variation distance between the distributions T⋅Xand G~⋅Xis 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)≫m1.5⋅d3, this is a significant savings over the na\"ive O(nnz(X)m)time to compute G~⋅X. Moreover, since the total variation distance is small, we can provably use T⋅Xin place of G~⋅Xin 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).
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.