  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 [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)k
log log (n eps/k))$ measurements that uses $O(log* k \log \log (n eps/k))$
rounds. This is a significant improvement over the best possible non-adaptive
bound. - A scheme with $m=O((1/eps) k log (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(log n)$ bits of space and $O(log log n)$ passes, improving over the best
possible space complexity achievable using a single pass.

Data Structures and Algorithms