82 citations · 187 across the 27 of their papers we have counts for
Showing 2016 · cs.DSShow all
2 papers · 2 filters
cs.DS2016★ 2 cited
How to Fake Multiply by a Gaussian Matrix
Michael Kapralov, Vamsi K. Potluru, David P. Woodruff
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 aff…
cs.DS2016★ 3 cited
Sparse Fourier Transform in Any Constant Dimension with Nearly-Optimal Sample Complexity in Sublinear Time
Michael Kapralov
We consider the problem of computing a -sparse approximation to the Fourier transform of a length signal. Our main result is a randomized algorithm for computing such an app…