On the Power of Adaptivity in Sparse Recovery

Abstract

The goal of (stable) sparse recovery is to recover a $k$-sparse approximation $x\ast$ of a vector $x$ from linear measurements of $x$. Specifically, the goal is to recover $x\ast$ 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 [CRT06] and that this bound is tight [DIPW10,FPRU10,PW11]. 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+eps$ and $p=q=2$ we show - A scheme with $m=O((1/eps)kloglog(neps/k))$ measurements that uses $O(log\ast k\log \log (neps/k))$ rounds. This is a significant improvement over the best possible non-adaptive bound. - A scheme with $m=O((1/eps)klog(k/eps)+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. As an independent application, we show how to solve the problem of finding a duplicate in a data stream of $n$ items drawn from $1,2,...,n-1$ using $O(logn)$ bits of space and $O(loglogn)$ passes, improving over the best possible space complexity achievable using a single pass.

18 pages; appearing at FOCS 2011