On the power of adaptivity in sparse recovery

The goal of (stable) sparse recovery is to recover a k-sparse approximation x* of a vector x from linear measurements of x. Specifically, the goal is to recover x* such that ∥x-x*∥ p ≤ C min k-sparse x′ ∥x-x′∥ q for some constant C and norm parameters p and q. It is known that, for p=q=1 or p=q=2, this task can be accomplished using m=O(k log (n/k)) non-adaptive measurements [3] and that this bound is tight [9], [12], [28]. In this paper we show that if one is allowed to perform measurements that are adaptive, then the number of measurements can be considerably reduced. Specifically, for C=1+ε and p=q=2 we show • A scheme with m=O(1/ε k log log (nε/k)) measurements that uses O(log* k·log log(nε/k)) rounds. This is a significant improvement over the best possible non-adaptive bound. • A scheme with m=O(1/εk log (k/ε) + k log (n/k)) measurements that uses two rounds. This improves over the best possible non-adaptive bound. To the best of our knowledge, these are the first results of this type. © 2011 IEEE.