1.9k citations · 2.8k across the 40 of their papers we have counts for
4 papers · 1 filter
On the Power of Adaptivity in Sparse Recovery
Piotr Indyk, Eric Price, David P. Woodruff
The goal of (stable) sparse recovery is to recover a -sparse approximation of a vector from linear measurements of . Specifically, the goal is to recover such t…
(1+eps)-approximate Sparse Recovery
Eric Price, David P. Woodruff
The problem central to sparse recovery and compressive sensing is that of stable sparse recovery: we want a distribution of matrices A in R^{m\times n} such that, for any x \in R^n…
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-…
K-Median Clustering, Model-Based Compressive Sensing, and Sparse Recovery for Earth Mover Distance
Piotr Indyk, Eric Price
We initiate the study of sparse recovery problems under the Earth-Mover Distance (EMD). Specifically, we design a distribution over m x n matrices A such that for any x, given Ax,…