Lower bounds for sparse recovery

Abstract

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||i ≤ 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).