Near-Optimal Sparse Recovery in the L1 Norm

We consider the *approximate sparse recovery problem*, where the goal is to (approximately) recover a high-dimensional vector x from Rn from its lower-dimensional *sketch* Ax from Rm.Specifically, we focus on the sparse recovery problem in the L1 norm: for a parameter k, given the sketch Ax, compute an approximation x' of x such that the L1 approximation error | |x-x'| | is close to minimum of | |x-x*| | over all vectors x* with at most k terms. The sparse recovery problem has been subject to extensive research over the last few years.Many solutions to this problem have been discovered, achieving different trade-offs between various attributes, such as the sketch length, encoding and recovery times.In this paper we provide a sparse recovery scheme which achieves close to optimal performance on virtually all attributes. In particular, this is the first recovery scheme that guarantees k log(n/k) sketch length, and near-linear n log (n/k) recovery time *simultaneously*. It also features low encoding and update times, and is noise-resilient.