  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, we can recover a k-sparse approximation to x
under the EMD distance. One construction yields m = O(k log(n/k)) and a 1 +
epsilon approximation factor, which matches the best achievable bound for other
error measures, such as the L_1 norm. Our algorithms are obtained by exploiting
novel connections to other problems and areas, such as streaming algorithms for
k-median clustering and model-based compressive sensing. We also provide novel
algorithms and results for the latter problems.
