We consider the following k-sparse recovery problem: design an m × n matrix A, such that for any signal x, given Ax we can efficiently recover ○ satisfying ‖x – ○‖1 ≤ C mink-sparse x′ ‖x – x′‖1. It is known that there exist matrices A with this property that have only O(k log(n/k)) rows. In this paper we show that this bound is tight. Our bound holds even for the more general randomized version of the problem, where A is a random variable, and the recovery algorithm is required to work for any fixed x with constant probability (over A).

We provide the first sub-linear sketching algorithm for estimating the planar Earth-Mover Distance with a constant approximation. For sets living in the two-dimensional grid [¿]2, we achieve space ¿¿for approximation O(1/¿), for any desired 0 < ¿ < 1. Our sketch has immediate applications to the streaming and nearest neighbor search problems.