1.9k citations · 2.8k across the 40 of their papers we have counts for
4 papers · 2 filters
New constructions of RIP matrices with fast multiplication and fewer rows
Jelani Nelson, Eric Price, Mary Wootters
In compressed sensing, the "restricted isometry property" (RIP) is a sufficient condition for the efficient reconstruction of a nearly k-sparse vector x in C^d from m linear measur…
Improved Concentration Bounds for Count-Sketch
Gregory T. Minton, Eric Price
We present a refined analysis of the classic Count-Sketch streaming heavy hitters algorithm [CCF02]. Count-Sketch uses O(k log n) linear measurements of a vector x in R^n to give a…
Lower Bounds for Adaptive Sparse Recovery
Eric Price, David P. Woodruff
We give lower bounds for the problem of stable sparse recovery from /adaptive/ linear measurements. In this problem, one would like to estimate a vector from linea…
Nearly Optimal Sparse Fourier Transform
Haitham Hassanieh, Piotr Indyk, Dina Katabi +1
We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show: * An O(k log n)-time randomized algorithm for…