11 citations · 14 across the 4 of their papers we have counts for
3 papers · 1 filter
Sample-Optimal Average-Case Sparse Fourier Transform in Two Dimensions
Badih Ghazi, Haitham Hassanieh, Piotr Indyk +3
We present the first sample-optimal sublinear time algorithms for the sparse Discrete Fourier Transform over a two-dimensional sqrt{n} x sqrt{n} grid. Our algorithms are analyzed f…
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…
Lower Bounds for Sparse Recovery
Khanh Do Ba, Piotr Indyk, Eric Price +1
We consider the following k-sparse recovery problem: design an m x n matrix A, such that for any signal x, given Ax we can efficiently recover x' satisfying ||x-x'||_1 <= C min_{k-…