# On the Power of Adaptivity in Sparse Recovery

Piotr Indyk  Eric Price  David P. Woodruff

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

$\left\lVert x-x^{*}\right\rVert_{p}\leq C\min_{k\text{-sparse
}x^{\prime}}\left\lVert x-x^{\prime}\right\rVert_{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+\epsilon$ and $p=q=2$ we show

  * •

A scheme with $m=O(\frac{1}{\epsilon}k\log\log(n\epsilon/k))$ measurements
that uses $O(\log^{*}k\cdot\log\log(n\epsilon/k))$ rounds. This is a
significant improvement over the best possible non-adaptive bound.

  * •

A scheme with $m=O(\frac{1}{\epsilon}k\log(k/\epsilon)+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,\ldots,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.

##  1 Introduction

In recent years, a new “linear” approach for obtaining a succinct approximate
representation of $n$-dimensional vectors (or signals) has been discovered.
For any signal $x$, the representation is equal to $Ax$, where $A$ is an
$m\times n$ matrix, or possibly a random variable chosen from some
distribution over such matrices. The vector $Ax$ is often referred to as the
measurement vector or linear sketch of $x$. Although $m$ is typically much
smaller than $n$, the sketch $Ax$ often contains plenty of useful information
about the signal $x$.

A particularly useful and well-studied problem is that of stable sparse
recovery. We say that a vector $x^{\prime}$ is $k$-sparse if it has at most
$k$ non-zero coordinates. The sparse recovery problem is typically defined as
follows: for some norm parameters $p$ and $q$ and an approximation factor
$C>0$, given $Ax$, recover an “approximation” vector $x^{*}$ such that

$\left\lVert x-x^{*}\right\rVert_{p}\leq C\min_{k\text{-sparse
}x^{\prime}}\left\lVert x-x^{\prime}\right\rVert_{q}$ (1)

(this inequality is often referred to as $\ell_{p}/\ell_{q}$ guarantee). If
the matrix $A$ is random, then Equation (1) should hold for each $x$ with some
probability (say, 2/3). Sparse recovery has a tremendous number of
applications in areas such as compressive sensing of signals [CRT06, Don06],
genetic data acquisition and analysis [SAZ10, BGK+10] and data stream
algorithms111In streaming applications, a data stream is modeled as a sequence
of linear operations on an (implicit) vector x. Example operations include
increments or decrements of $x$’s coordinates. Since such operations can be
directly performed on the linear sketch $Ax$, one can maintain the sketch
using only $O(m)$ words. [Mut05, Ind07]; the latter includes applications to
network monitoring and data analysis.

It is known [CRT06] that there exist matrices $A$ and associated recovery
algorithms that produce approximations $x^{*}$ satisfying Equation (1) with
$p=q=1$, constant approximation factor $C$, and sketch length

$m=O(k\log(n/k))$ (2)

A similar bound, albeit using random matrices $A$, was later obtained for
$p=q=2$ [GLPS10] (building on [CCF02, CM04, CM06]). Specifically, for
$C=1+\epsilon$, they provide a distribution over matrices $A$ with

$m=O(\frac{1}{\epsilon}k\log(n/k))$ (3)

rows, together with an associated recovery algorithm.

It is also known that the bound in Equation (2) is asymptotically optimal for
some constant $C$ and $p=q=1$, see [DIPW10] and [FPRU10] (building on [GG84,
Glu84, Kas77]). The bound of [DIPW10] also extends to the randomized case and
$p=q=2$. For $C=1+\epsilon$, a lower bound of
$m=\Omega(\frac{1}{\epsilon}k\log(n/k))$ was recently shown [PW11] for the
randomized case and $p=q=2$, improving upon the earlier work of [DIPW10] and
showing the dependence on $\epsilon$ is optimal. The necessity of the “extra”
logarithmic factor multiplying $k$ is quite unfortunate: the sketch length
determines the “compression rate”, and for large $n$ any logarithmic factor
can worsen that rate tenfold.

In this paper we show that this extra factor can be greatly reduced if we
allow the measurement process to be adaptive. In the adaptive case, the
measurements are chosen in rounds, and the choice of the measurements in each
round depends on the outcome of the measurements in the previous rounds. The
adaptive measurement model has received a fair amount of attention in the
recent years [JXC08, CHNR08, HCN09, HBCN09, MSW08, AWZ08], see also [Def10].
In particular [HBCN09] showed that adaptivity helps reducing the approximation
error in the presence of random noise. However, no asymptotic improvement to
the number of measurements needed for sparse recovery (as in Equation (1)) was
previously known.

#### Results

In this paper we show that adaptivity can lead to very significant
improvements in the number of measurements over the bounds in Equations (2)
and (3). We consider randomized sparse recovery with $\ell_{2}/\ell_{2}$
guarantee, and show two results:

  1. 1.

A scheme with $m=O(\frac{1}{\epsilon}k\log\log(n\epsilon/k))$ measurements and
an approximation factor $C=1+\epsilon$. For low values of $k$ this provides an
exponential improvement over the best possible non-adaptive bound. The scheme
uses $O(\log^{*}k\cdot\log\log(n\epsilon/k))$ rounds.

  2. 2.

A scheme with $m=O(\frac{1}{\epsilon}k\log(k/\epsilon)+k\log(n/k))$ and an
approximation factor $C=1+\epsilon$. For low values of $k$ and $\epsilon$ this
offers a significant improvement over the best possible non-adaptive bound,
since the dependence on $n$ and $\epsilon$ is “split” between two terms. The
scheme uses only two rounds.

#### Implications

Our new bounds lead to potentially significant improvements to efficiency of
sparse recovery schemes in a number of application domains. Naturally, not all
applications support adaptive measurements. For example, network monitoring
requires the measurements to be performed simultaneously, since we cannot ask
the network to “re-run” the packets all over again. However, a surprising
number of applications are capable of supporting adaptivity. For example:

  * •

Streaming algorithms for data analysis: since each measurement round can be
implemented by one pass over the data, adaptive schemes simply correspond to
multiple-pass streaming algorithms (see [McG09] for some examples of such
algorithms).

  * •

Compressed sensing of signals: several architectures for compressive sensing,
e.g., the single-pixel camera of [DDT+08], already perform the measurements in
a sequential manner. In such cases the measurements can be made adaptive222We
note that, in any realistic sensing system, minimizing the number of
measurements is only one of several considerations. Other factors include:
minimizing the computation time, minimizing the amount of communication needed
to transfer the measurement matrices to the sensor, satisfying constraints on
the measurement matrix imposed by the hardware etc. A detailed cost analysis
covering all of these factors is architecture-specific, and beyond the scope
of this paper. . Other architectures supporting adaptivity are under
development [Def10].

  * •

Genetic data analysis and acqusition: as above.

Therefore, it seems likely that the results in this paper will be applicable
in a wide variety of scenarios.

As an example application, we show how to solve the problem of finding a
duplicate in a data stream of $n$ arbitrarily chosen items from the set
$\\{1,2,\ldots,n-1\\}$ presented in an arbitrary order. Our algorithm uses
$O(\log n)$ bits of space and $O(\log\log n)$ passes. It is known that for a
single pass, $\Theta(\log^{2}n)$ bits of space is necessary and sufficient
[JST11], and so our algorithm improves upon the best possible space complexity
using a single pass.

#### Techniques

On a high-level, both of our schemes follow the same two-step process. First,
we reduce the problem of finding the best $k$-sparse approximation to the
problem of finding the best $1$-sparse approximation (using relatively
standard techniques). This is followed by solving the latter (simpler)
problem.

The first scheme starts by “isolating” most of of the large coefficients by
randomly sampling $\approx\epsilon/k$ fraction of the coordinates; this mostly
follows the approach of [GLPS10] (cf. [GGI+02]). The crux of the algorithm is
in the identification of the isolated coefficients. Note that in order to
accomplish this using $O(\log\log n)$ measurements (as opposed to $O(\log n)$
achieved by the “standard” binary search algorithm) we need to “extract”
significantly more than one bit of information per measurements. To achieve
this, we proceed as follows. First, observe that if the given vector (say,
$z$) is exactly $1$-sparse, then one can extract the position of the non-zero
entry (say $z_{j}$) from two measurements $a(z)=\sum_{i}z_{i}$, and
$b(z)=\sum_{i}iz_{i}$, since $b(z)/a(z)=j$. A similar algorithm works even if
$z$ contains some “very small” non-zero entries: we just round $b(z)/a(z)$ to
the nearest integer. This algorithm is a special case of a general algorithm
that achieves $O(\log n/\log SNR)$ measurements to identify a single
coordinate $x_{j}$ among $n$ coordinates, where
$SNR=x_{j}^{2}/\|x_{[n]\setminus j}\|^{2}$ (SNR stands for signal-to-noise
ratio). This is optimal as a function of $n$ and the SNR [DIPW10].

A natural approach would then be to partition $[n]$ into two sets
$\\{1,\ldots,n/2\\}$ and $\\{n/2+1,\ldots n\\}$, find the heavier of the two
sets, and recurse. This would take $O(\log n)$ rounds. The key observation is
that not only do we recurse on a smaller-sized set of coordinates, but the SNR
has also increased since $x_{j}^{2}$ has remained the same but the squared
norm of the tail has dropped by a constant factor. Therefore in the next round
we can afford to partition our set into more than two sets, since as long as
we keep the ratio of $\log(\\#\textrm{ of sets })$ and $\log SNR$ constant, we
only need $O(1)$ measurements per round. This ultimately leads to a scheme
that finishes after $O(\log\log n)$ rounds.

In the second scheme, we start by hashing the coordinates into a universe of
size polynomial in $k$ and $1/\epsilon$, in a way that approximately preserves
the top coefficients without introducing spurious ones, and in such a way that
the mass of the tail of the vector does not increase significantly by hashing.
This idea is inspired by techniques in the data stream literature for
estimating moments [KNPW10, TZ04] (cf. [CCF02, CM06, GI10]). Here, though, we
need stronger error bounds. This enables us to identify the positions of those
coefficients (in the hashed space) using only
$O(\frac{1}{\epsilon}k\log(k/\epsilon))$ measurements. Once this is done, for
each large coefficient $i$ in the hash space, we identify the actual large
coefficient in the preimage of $i$. This can be achieved using the number of
measurements that does not depend on $\epsilon$.

##  2 Preliminaries

We start from a few definitions. Let $x$ be an $n$-dimensional vector.

######  Definition 2.1.

Define

$H_{k}(x)=\operatorname*{arg\,max}_{\begin{subarray}{c}S\in[n]\\\
\left|S\right|=k\end{subarray}}\left\lVert x_{S}\right\rVert_{2}$

to be the largest $k$ coefficients in $x$.

######  Definition 2.2.

For any vector $x$, we define the “heavy hitters” to be those elements that
are both (i) in the top $k$ and (ii) large relative to the mass outside the
top $k$. We define

$H_{k,\epsilon}(x)=\\{j\in H_{k}(x)\mid x_{j}^{2}\geq\epsilon\left\lVert
x_{\overline{H_{k}(x)}}\right\rVert_{2}^{2}\\}$

######  Definition 2.3.

Define the error

$\operatorname{Err^{2}}(x,k)=\left\lVert
x_{\overline{H_{k}(x)}}\right\rVert_{2}^{2}$

For the sake of clarity, the analysis of the algorithm in section 4 assumes
that the entries of $x$ are sorted by the absolute value (i.e., we have
$|x_{1}|\geq|x_{2}|\geq\ldots\geq|x_{n}|$). In this case, the set $H_{k}(x)$
is equal to $[k]$; this allows us to simplify the notation and avoid double
subscripts. The algorithms themselves are invariant under the permutation of
the coordinates of $x$.

#### Running times of the recovery algorithms

In the non-adaptive model, the running time of the recovery algorithm is well-
defined: it is the number of operations performed by a procedure that takes
$Ax$ as its input and produces an approximation $x^{*}$ to $x$. The time
needed to generate the measurement vectors $A$, or to encode the vector $x$
using $A$, is not included. In the adaptive case, the distinction between the
matrix generation, encoding and recovery procedures does not exist, since new
measurements are generated based on the values of the prior ones. Moreover,
the running time of the measurement generation procedure heavily depends on
the representation of the matrix. If we suppose that we may output the matrix
in sparse form and receive encodings in time bounded by the number of non-zero
entries in the matrix, our algorithms run in $n\log^{O(1)}n$ time.

##  3 Full adaptivity

This section shows how to perform $k$-sparse recovery with $O(k\log\log(n/k))$
measurements. The core of our algorithm is a method for performing $1$-sparse
recovery with $O(\log\log n)$ measurements. We then extend this to $k$-sparse
recovery via repeated subsampling.

###  3.1 $1$-sparse recovery

This section discusses recovery of $1$-sparse vectors with $O(\log\log n)$
adaptive measurements. First, in Lemma 3.1 we show that if the heavy hitter
$x_{j}$ is $\Omega(n)$ times larger than the $\ell_{2}$ error ($x_{j}$ is
“$\Omega(n)$-heavy”), we can find it with two non-adaptive measurements. This
corresponds to non-adaptive $1$-sparse recovery with approximation factor
$C=\Theta(n)$; achieving this with $O(1)$ measurements is unsurprising,
because the lower bound [DIPW10] is $\Omega(\log_{1+C}n)$.

Lemma 3.1 is not directly very useful, since $x_{j}$ is unlikely to be that
large. However, if $x_{j}$ is $D$ times larger than everything else, we can
partition the coordinates of $x$ into $D$ random blocks of size $N/D$ and
perform dimensionality reduction on each block. The result will in expectation
be a vector of size $D$ where the block containing $j$ is $D$ times larger
than anything else. The first lemma applies, so we can recover the block
containing $j$, which has a $1/\sqrt{D}$ fraction of the $\ell_{2}$ noise.
Lemma 3.2 gives this result.

We then have that with two non-adaptive measurements of a $D$-heavy hitter we
can restrict to a subset where it is an $\Omega(D^{3/2})$-heavy hitter.
Iterating $\log\log n$ times gives the result, as shown in Lemma 3.3.

######  Lemma 3.1.

Suppose there exists a $j$ with $\left|x_{j}\right|\geq
C\frac{n}{\sqrt{\delta}}\left\lVert x_{[n]\setminus\\{j\\}}\right\rVert_{2}$
for some constant $C$. Then two non-adaptive measurements suffice to recover
$j$ with probability $1-\delta$.

###### Proof.

Let $s\colon[n]\to\\{\pm 1\\}$ be chosen from a $2$-wise independent hash
family. Perform the measurements $a(x)=\sum s(i)x_{i}$ and
$b(x)=\sum(n+i)s(i)x_{i}$. For recovery, output the closest integer to
$b/a-n$.

Let $z=x_{[n]\setminus\\{j\\}}$. Then
$\operatorname{\mathbb{E}}[a(z)^{2}]=\left\lVert z\right\rVert_{2}^{2}$ and
$\operatorname{\mathbb{E}}[b(z)^{2}]\leq 4n^{2}\left\lVert
z\right\rVert_{2}^{2}$. Hence with probability at least $1-2\delta$, we have
both

$\displaystyle\left|a(z)\right|\leq\sqrt{1/\delta}\left\lVert
z\right\rVert_{2}$ $\displaystyle\left|b(z)\right|\leq
2n\sqrt{1/\delta}\left\lVert z\right\rVert_{2}$

Thus

$\displaystyle\frac{b(x)}{a(x)}=$
$\displaystyle\frac{s(j)(n+j)x_{j}+b(z)}{s(j)x_{j}+a(z)}$
$\displaystyle\left|\frac{b(x)}{a(x)}-(n+j)\right|=$
$\displaystyle\left|\frac{b(z)-(n+j)a(z)}{s(j)x_{j}+a(z)}\right|$
$\displaystyle\leq$
$\displaystyle\frac{\left|b(z)\right|+(n+j)\left|a(z)\right|}{\left|\left|x_{j}\right|-\left|a(z)\right|\right|}$
$\displaystyle\leq$ $\displaystyle\frac{4n\sqrt{1/\delta}\left\lVert
z\right\rVert_{2}}{\left|\left|x_{j}\right|-\left|a(z)\right|\right|}$

Suppose $\left|x_{j}\right|>(8n+1)\sqrt{1/\delta}\left\lVert
z\right\rVert_{2}$. Then

$\displaystyle\left|\frac{b(x)}{a(x)}-(n+j)\right|<$
$\displaystyle\frac{4n\sqrt{1/\delta}\left\lVert
z\right\rVert_{2}}{8n\sqrt{1/\delta}\left\lVert z\right\rVert_{2}}$
$\displaystyle=$ $\displaystyle 1/2$

so $\hat{\imath}=j$. ∎

######  Lemma 3.2.

Suppose there exists a $j$ with $\left|x_{j}\right|\geq
C\frac{B^{2}}{\delta^{2}}\left\lVert x_{[n]\setminus\\{j\\}}\right\rVert_{2}$
for some constant $C$ and parameters $B$ and $\delta$. Then with two non-
adaptive measurements, with probability $1-\delta$ we can find a set
$S\subset[n]$ such that $j\in S$ and $\left\lVert
x_{S\setminus\\{j\\}}\right\rVert_{2}\leq\left\lVert
x_{[n]\setminus\\{j\\}}\right\rVert_{2}/B$ and $\left|S\right|\leq 1+n/B^{2}$.

###### Proof.

Let $D=B^{2}/\delta$, and let $h\colon[n]\to[D]$ and $s\colon[n]\to\\{\pm
1\\}$ be chosen from pairwise independent hash families. Then define
$S_{p}=\\{i\in[n]\mid h(i)=p\\}$. Define the matrix $A\in\mathbb{R}^{D\times
n}$ by $A_{h(i),i}=s(i)$ and $A_{p,i}=0$ elsewhere. Then

$(Az)_{p}=\sum_{i\in S_{p}}s(i)z_{i}.$

Let $p^{*}=h(j)$ and $y=x_{[n]\setminus\\{j\\}}$. We have that

$\displaystyle\operatorname{\mathbb{E}}[\left|S_{p^{*}}\right|]=$
$\displaystyle 1+(n-1)/D$
$\displaystyle\operatorname{\mathbb{E}}[(Ay)_{p^{*}}^{2}]=\operatorname{\mathbb{E}}[\left\lVert
y_{S_{p^{*}}}\right\rVert_{2}^{2}]=$ $\displaystyle\left\lVert
y\right\rVert_{2}^{2}/D$ $\displaystyle\operatorname{\mathbb{E}}[\left\lVert
Ay\right\rVert_{2}^{2}]=$ $\displaystyle\left\lVert y\right\rVert_{2}^{2}$

Hence by Chebyshev’s inequality, with probability at least $1-4\delta$ all of
the following hold:

$\displaystyle\left|S_{p^{*}}\right|\leq$ $\displaystyle 1+(n-1)/(D\delta)\leq
1+n/B^{2}$ (4) $\displaystyle\left\lVert y_{S_{p^{*}}}\right\rVert_{2}\leq$
$\displaystyle\left\lVert y\right\rVert_{2}/\sqrt{D\delta}$ (5)
$\displaystyle\left|(Ay)_{p^{*}}\right|\leq$ $\displaystyle\left\lVert
y\right\rVert_{2}/\sqrt{D\delta}$ (6) $\displaystyle\left\lVert
Ay\right\rVert_{2}\leq$ $\displaystyle\left\lVert
y\right\rVert_{2}/\sqrt{\delta}.$ (7)

The combination of (6) and (7) imply

$\displaystyle\left|(Ax)_{p^{*}}\right|\geq$
$\displaystyle\left|x_{j}\right|-\left|(Ay)_{p^{*}}\right|\geq(CD/\delta-1/\sqrt{D\delta})\left\lVert
y\right\rVert_{2}\geq(CD/\delta-1/\sqrt{D\delta})\sqrt{\delta}\left\lVert
Ay\right\rVert_{2}\geq\frac{CD}{2\sqrt{\delta}}\left\lVert Ay\right\rVert_{2}$

and hence

$\left|(Ax)_{p^{*}}\right|\geq\frac{CD}{2\sqrt{\delta}}\left\lVert(Ax)_{[D]\setminus
p^{*}}\right\rVert_{2}.$

As long as $C/2$ is larger than the constant in Lemma 3.1, this means two non-
adaptive measurements suffice to recover $p^{*}$ with probability $1-\delta$.
We then output the set $S_{p^{*}}$, which by (5) has

$\displaystyle\left\lVert x_{S_{p^{*}}\setminus\\{j\\}}\right\rVert_{2}=$
$\displaystyle\left\lVert y_{S_{p^{*}}}\right\rVert_{2}\leq\left\lVert
y\right\rVert_{2}/\sqrt{D\delta}=\left\lVert
x_{[n]\setminus\\{j\\}}\right\rVert_{2}/\sqrt{D\delta}=\left\lVert
x_{[n]\setminus\\{j\\}}\right\rVert_{2}/B$

as desired. The overall failure probability is $1-5\delta$; rescaling $\delta$
and $C$ gives the result. ∎

Algorithm 1 Adaptive $1$-sparse recovery

procedure NonAdaptiveShrink($x$, $D$) $\triangleright$ Find smaller set $S$
containing heavy coordinate $x_{j}$

For $i\in[n]$, $s_{1}(i)\leftarrow\\{\pm 1\\},h(i)\leftarrow[D]$

For $i\in[D]$, $s_{2}(i)\leftarrow\\{\pm 1\\}$

$a\leftarrow\sum s_{1}(i)s_{2}(h(i))x_{i}$$\triangleright$ Observation

$b\leftarrow\sum s_{1}(i)s_{2}(h(i))x_{i}(D+h(i))$$\triangleright$ Observation

$p^{*}\leftarrow\textsc{Round}(b/a-D)$.

return $\\{j^{*}\mid h(j^{*})=p^{*}\\}$.

end procedure

procedure AdaptiveOneSparseRec($x$)$\triangleright$ Recover heavy coordinate
$x_{j}$

$S\leftarrow[n]$

$B\leftarrow 2$, $\delta\leftarrow 1/4$

while $\left|S\right|>1$ do

$S\leftarrow\textsc{NonAdaptiveShrink}(x_{S},4B^{2}/\delta)$

$B\leftarrow B^{3/2}$, $\delta\leftarrow\delta/2$.

end while

return $S[0]$

end procedure

######  Lemma 3.3.

Suppose there exists a $j$ with $\left|x_{j}\right|\geq C\left\lVert
x_{[n]\setminus\\{j\\}}\right\rVert_{2}$ for some constant $C$. Then
$O(\log\log n)$ adaptive measurements suffice to recover $j$ with probability
$1/2$.

###### Proof.

Let $C^{\prime}$ be the constant from Lemma 3.2. Define $B_{0}=2$ and
$B_{i}=B_{i-1}^{3/2}$ for $i\geq 1$. Define $\delta_{i}=2^{-i}/4$ for $i\geq
0$. Suppose $C\geq 16C^{\prime}B_{0}^{2}/\delta_{0}^{2}$.

Define $r=O(\log\log n)$ so $B_{r}\geq n$. Starting with $S_{0}=[n]$, our
algorithm iteratively applies Lemma 3.2 with parameters $B=4B_{i}$ and
$\delta=\delta_{i}$ to $x_{S_{i}}$ to identify a set $S_{i+1}\subset S_{i}$
with $j\in S_{i+1}$, ending when $i=r$.

We prove by induction that Lemma 3.2 applies at the $i$th iteration. We chose
$C$ to match the base case. For the inductive step, suppose $\left\lVert
x_{S_{i}\setminus\\{j\\}}\right\rVert_{2}\leq\left|x_{j}\right|/(C^{\prime}16\frac{B_{i}^{2}}{\delta_{i}^{2}})$.
Then by Lemma 3.2,

$\left\lVert
x_{S_{i+1}\setminus\\{j\\}}\right\rVert_{2}\leq\left|x_{j}\right|/(C^{\prime}64\frac{B_{i}^{3}}{\delta_{i}^{2}})=\left|x_{j}\right|/(C^{\prime}16\frac{B_{i+1}^{2}}{\delta_{i+1}^{2}})$

so the lemma applies in the next iteration as well, as desired.

After $r$ iterations, we have $S_{r}\leq 1+n/B_{r}^{2}<2$, so we have uniquely
identified $j\in S_{r}$. The probability that any iteration fails is at most
$\sum\delta_{i}<2\delta_{0}=1/2$. ∎

###  3.2 $k$-sparse recovery

Given a $1$-sparse recovery algorithm using $m$ measurements, one can use
subsampling to build a $k$-sparse recovery algorithm using $O(km)$
measurements and achieving constant success probability. Our method for doing
so is quite similar to one used in [GLPS10]. The main difference is that, in
order to identify one large coefficient among a subset of coordinates, we use
the adaptive algorithm from the previous section as opposed to error-
correcting codes.

For intuition, straightforward subsampling at rate $1/k$ will, with constant
probability, recover (say) 90% of the heavy hitters using $O(km)$
measurements. This reduces the problem to $k/10$-sparse recovery: we can
subsample at rate $10/k$ and recover 90% of the remainder with $O(km/10)$
measurements, and repeat $\log k$ times. The number of measurements decreases
geometrically, for $O(km)$ total measurements. Naively doing this would
multiply the failure probability and the approximation error by $\log k$;
however, we can make the number of measurements decay less quickly than the
sparsity. This allows the failure probability and approximation ratios to also
decay exponentially so their total remains constant.

To determine the number of rounds, note that the initial set of $O(km)$
measurements can be done in parallel for each subsampling, so only $O(m)$
rounds are necessary to get the first 90% of heavy hitters. Repeating $\log k$
times would require $O(m\log k)$ rounds. However, we can actually make the
sparsity in subsequent iterations decay super-exponentially, in fact as a
power tower. This give $O(m\log^{*}k)$ rounds.

######  Theorem 3.4.

There exists an adaptive $(1+\epsilon)$-approximate $k$-sparse recovery scheme
with $O(\frac{1}{\epsilon}k\log\frac{1}{\delta}\log\log(n\epsilon/k))$
measurements and success probability $1-\delta$. It uses
$O(\log^{*}k\log\log(n\epsilon))$ rounds.

To prove this, we start from the following lemma:

######  Lemma 3.5.

We can perform $O(\log\log(n/k))$ adaptive measurements and recover an
$\hat{\imath}$ such that, for any $j\in H_{k,1/k}(x)$ we have
$\Pr[\hat{\imath}=j]=\Omega(1/k)$.

###### Proof.

Let $S=H_{k}(x)$. Let $T\subset[n]$ contain each element independently with
probability $p=1/(4C^{2}k)$, where $C$ is the constant in Lemma 3.3. Let $j\in
H_{k,1/k}(x)$. Then we have

$\operatorname{\mathbb{E}}[\left\lVert x_{T\setminus
S}\right\rVert_{2}^{2}]=p\left\lVert x_{\overline{S}}\right\rVert_{2}^{2}$

so

$\left\lVert x_{T\setminus S}\right\rVert_{2}\leq\sqrt{4p}\left\lVert
x_{\overline{S}}\right\rVert_{2}=\frac{1}{C\sqrt{k}}\left\lVert
x_{\overline{S}}\right\rVert_{2}\leq\left|x_{j}\right|/C$

with probability at least $3/4$. Furthermore we have
$\operatorname{\mathbb{E}}[\left|T\setminus S\right|]<pn$ so $\left|T\setminus
S\right|<n/k$ with probability at least $1-1/(4C^{2})>3/4$. By the union
bound, both these events occur with probability at least $1/2$.

Independently of this, we have

$\Pr[T\cap S=\\{j\\}]=p(1-p)^{k-1}>p/e$

so all these events hold with probability at least $p/(2e)$. Assuming this,

$\left\lVert x_{T\setminus\\{j\\}}\right\rVert_{2}\leq\left|x_{j}\right|/C$

and $\left|T\right|\leq 1+n/k$. But then Lemma 3.3 applies, and
$O(\log\log\left|T\right|)=O(\log\log(n/k))$ measurements can recover $j$ from
a sketch of $x_{T}$ with probability $1/2$. This is independent of the
previous probability, for a total success chance of $p/(4e)=\Omega(1/k)$. ∎

######  Lemma 3.6.

With $O(\frac{1}{\epsilon}k\log\frac{1}{f\delta}\log\log(n\epsilon/k))$
adaptive measurements, we can recover $T$ with $\left|T\right|\leq k$ and

$\operatorname{Err^{2}}(x_{\overline{T}},fk)\leq(1+\epsilon)\operatorname{Err^{2}}(x,k)$

with probability at least $1-\delta$. The number of rounds required is
$O(\log\log(n\epsilon/k))$.

###### Proof.

Repeat Lemma 3.5 $m=O(\frac{1}{\epsilon}k\log\frac{1}{f\delta})$ times in
parallel with parameters $n$ and $k/\epsilon$ to get coordinates
$T^{\prime}=\\{t_{1},t_{2},\dotsc,t_{m}\\}$. For each $j\in
H_{k,\epsilon/k}(x)\subseteq H_{k/\epsilon,\epsilon/k}(x)$ and $i\in[m]$, the
lemma implies $\Pr[j=t_{i}]\geq\epsilon/(Ck)$ for some constant $C$. Then
$\Pr[j\notin T^{\prime}]\leq(1-\epsilon/(Ck))^{m}\leq e^{-\epsilon m/(Ck)}\leq
f\delta$ for appropriate $m$. Thus

$\displaystyle\operatorname{\mathbb{E}}[\left|H_{k,\epsilon/k}(x)\setminus
T^{\prime}\right|]\leq f\delta\left|H_{k,\epsilon/k}(x)\right|\leq$
$\displaystyle f\delta k$
$\displaystyle\Pr\left[\left|H_{k,\epsilon/k}(x)\setminus
T^{\prime}\right|\geq fk\right]\leq$ $\displaystyle\delta.$

Now, observe $x_{T^{\prime}}$ directly and set $T\subseteq T^{\prime}$ to be
the locations of the largest $k$ values. Then, since
$H_{k,\epsilon/k}(x)\subseteq H_{k}(x)$, $\left|H_{k,\epsilon/k}(x)\setminus
T\right|=\left|H_{k,\epsilon/k}(x)\setminus T^{\prime}\right|\leq fk$ with
probability at least $1-\delta$.

Suppose this occurs, and let $y=x_{\overline{T}}$. Then

$\displaystyle\operatorname{Err^{2}}(y,fk)=$
$\displaystyle\min_{\left|S\right|\leq fk}\left\lVert
y_{\overline{S}}\right\rVert_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\left\lVert y_{\overline{H_{k,\epsilon/k}(x)\setminus
T}}\right\rVert_{2}^{2}$ $\displaystyle=$ $\displaystyle\left\lVert
x_{\overline{H_{k,\epsilon/k}(x)}}\right\rVert_{2}^{2}$ $\displaystyle=$
$\displaystyle\left\lVert
x_{\overline{H_{k}(x)}}\right\rVert_{2}^{2}+\left\lVert x_{H_{k}(x)\setminus
H_{k,\epsilon/k}(x)}\right\rVert_{2}^{2}$ $\displaystyle\leq$
$\displaystyle\left\lVert
x_{\overline{H_{k}(x)}}\right\rVert_{2}^{2}+k\left\lVert x_{H_{k}(x)\setminus
H_{k,\epsilon/k}(x)}\right\rVert_{\infty}^{2}$ $\displaystyle\leq$
$\displaystyle(1+\epsilon)\left\lVert
x_{\overline{H_{k}(x)}}\right\rVert_{2}^{2}$ $\displaystyle=$
$\displaystyle(1+\epsilon)\operatorname{Err^{2}}(x,k)$

as desired. ∎

Algorithm 2 Adaptive $k$-sparse recovery

procedure AdaptiveKSparseRec($x$, $k$, $\epsilon$, $\delta$)$\triangleright$
Recover approximation $\hat{x}$ of $x$

$R_{0}\leftarrow[n]$

$\delta_{0}\leftarrow\delta/2$, $\epsilon_{0}\leftarrow\epsilon/e$,
$f_{0}\leftarrow 1/32$, $k_{0}\leftarrow k$.

$J\leftarrow\\{\\}$

for $i\leftarrow 0,\dotsc,O(\log^{*}k)$ do$\triangleright$ While $k_{i}\geq 1$

for $t\leftarrow
0,\dotsc,\Theta(\frac{1}{\epsilon_{i}}k_{i}\log\frac{1}{\delta_{i}})$ do

$S_{t}\leftarrow\textsc{Subsample}(R_{i},\Theta(\epsilon_{i}/k_{i}))$

$J.\text{add}(\textsc{AdaptiveOneSparseRec}(x_{S_{t}}))$

end for

$R_{i+1}\leftarrow[n]\setminus J$

$\delta_{i+1}\leftarrow\delta_{i}/8$

$\epsilon_{i+1}\leftarrow\epsilon_{i}/2$

$f_{i+1}\leftarrow 1/2^{1/(4^{i+1}f_{i})}$

$k_{i+1}\leftarrow k_{i}f_{i}$

end for

$\hat{x}\leftarrow x_{J}$ $\triangleright$ Direct observation

return $\hat{x}$

end procedure

######  Theorem 3.7.

We can perform
$O(\frac{1}{\epsilon}k\log\frac{1}{\delta}\log\log(n\epsilon/k))$ adaptive
measurements and recover a set $T$ of size at most $2k$ with

$\left\lVert x_{\overline{T}}\right\rVert_{2}\leq(1+\epsilon)\left\lVert
x_{\overline{H_{k}(x)}}\right\rVert_{2}.$

with probability $1-\delta$. The number of rounds required is
$O(\log^{*}k\log\log(n\epsilon))$.

###### Proof.

Define $\delta_{i}=\frac{\delta}{2\cdot 2^{i}}$ and
$\epsilon_{i}=\frac{\epsilon}{e\cdot 2^{i}}$. Let $f_{0}=1/32$ and
$f_{i}=2^{-1/(4^{i}f_{i-1})}$ for $i>0$, and define $k_{i}=k\prod_{j<i}f_{j}$.
Let $R_{0}=[n]$.

Let $r=O(\log^{*}k)$ such that $f_{r-1}<1/k$. This is possible since
$\alpha_{i}=1/(4^{i+1}f_{i})$ satisfies the recurrence $\alpha_{0}=8$ and
$\alpha_{i}=2^{\alpha_{i-1}-2i-2}>2^{\alpha_{i-1}/2}$. Thus $\alpha_{r-1}>k$
for $r=O(\log^{*}k)$ and then $f_{r-1}<1/\alpha_{r-1}<1/k$.

For each round $i=0,\dotsc,r-1$, the algorithm runs Lemma 3.6 on $x_{R_{i}}$
with parameters $\epsilon_{i}$, $k_{i}$, $f_{i}$, and $\delta_{i}$ to get
$T_{i}$. It sets $R_{i+1}=R_{i}\setminus T_{i}$ and repeats. At the end, it
outputs $T=\cup T_{i}$.

The total number of measurements is

$\displaystyle
O(\sum\frac{1}{\epsilon_{i}}k_{i}\log\frac{1}{f_{i}\delta_{i}}\log\log(n\epsilon_{i}/k_{i}))\leq$
$\displaystyle
O(\sum\frac{2^{i}(k_{i}/k)\log(1/f_{i})}{\epsilon}k(i+\log\frac{1}{\delta})\log(\log(k/k_{i})+\log(n\epsilon/k)))$
$\displaystyle\leq$ $\displaystyle
O(\frac{1}{\epsilon}k\log\frac{1}{\delta}\log\log(n\epsilon/k)\sum
2^{i}(k_{i}/k)\log(1/f_{i})(i+1)\log\log(k/k_{i}))$

using the very crude bounds $i+\log(1/\delta)\leq(i+1)\log(1/\delta)$ and
$\log(a+b)\leq 2\log a\log b$ for $a,b\geq e$. But then

$\displaystyle\sum 2^{i}(k_{i}/k)\log(1/f_{i})(i+1)\log\log(k/k_{i})\leq$
$\displaystyle\sum 2^{i}(i+1)f_{i}\log(1/f_{i})\log\log(1/f_{i})$
$\displaystyle\leq$ $\displaystyle\sum 2^{i}(i+1)O(\sqrt{f_{i}})$
$\displaystyle=$ $\displaystyle O(1)$

since $f_{i}<O(1/16^{i})$, giving
$O(\frac{1}{\epsilon}k\log\frac{1}{\delta}\log\log(n\epsilon/k)$ total
measurements. The probability that any of the iterations fail is at most
$\sum\delta_{i}<\delta$. The result has size $\left|T\right|\leq\sum k_{i}\leq
2k$. All that remains is the approximation ratio $\left\lVert
x_{\overline{T}}\right\rVert_{2}=\left\lVert x_{R_{r}}\right\rVert_{2}$.

For each $i$, we have

$\displaystyle\operatorname{Err^{2}}(x_{R_{i+1}},k_{i+1})=$
$\displaystyle\operatorname{Err^{2}}(x_{R_{i}\setminus
T_{i}},f_{i}k_{i})\leq(1+\epsilon_{i})\operatorname{Err^{2}}(x_{R_{i}},k_{i}).$

Furthermore, $k_{r}<kf_{r-1}<1$. Hence

$\displaystyle\left\lVert
x_{R_{r}}\right\rVert_{2}^{2}=\operatorname{Err^{2}}(x_{R_{r}},k_{r})\leq$
$\displaystyle\left(\prod_{i=0}^{r-1}(1+\epsilon_{i})\right)\operatorname{Err^{2}}(x_{R_{0}},k_{0})=\left(\prod_{i=0}^{r-1}(1+\epsilon_{i})\right)\operatorname{Err^{2}}(x,k)$

But $\prod_{i=0}^{r-1}(1+\epsilon_{i})<e^{\sum\epsilon_{i}}<e$, so

$\prod_{i=0}^{r-1}(1+\epsilon_{i})<1+\sum e\epsilon_{i}\leq 1+2\epsilon$

and hence

$\left\lVert x_{\overline{T}}\right\rVert_{2}=\left\lVert
x_{R_{r}}\right\rVert_{2}\leq(1+\epsilon)\left\lVert
x_{\overline{H_{k}(x)}}\right\rVert_{2}$

as desired. ∎

Once we find the support $T$, we can observe $x_{T}$ directly with $O(k)$
measurements to get a $(1+\epsilon)$-approximate $k$-sparse recovery scheme,
proving Theorem 3.4

##  4 Two-round adaptivity

The algorithms in this section are invariant under permutation. Therefore, for
simplicity of notation, the analysis assumes our vectors $x$ is sorted:
$\left|x_{1}\right|\geq\dotsc\geq\left|x_{n}\right|=0$.

We are given a $1$-round $k$-sparse recovery algorithm for $n$-dimensional
vectors $x$ using $m(k,\epsilon,n,\delta)$ measurements with the guarantee
that its output $\hat{x}$ satisfies
$\|\hat{x}-x\|_{p}\leq(1+\epsilon)\cdot\|x_{\overline{[k]}}\|_{p}$ for a
$p\in\\{1,2\\}$ with probability at least $1-\delta$. Moreover, suppose its
output $\hat{x}$ has support on a set of size $s(k,\epsilon,n,\delta)$. We
show the following black box two-round transformation.

######  Theorem 4.1.

Assume $s(k,\epsilon,n,\delta)=O(k)$. Then there is a $2$-round sparse
recovery algorithm for $n$-dimensional vectors $x$, which, in the first round
uses $m(k,\epsilon/5,{\mathrm{poly}}(k/\epsilon),1/100)$ measurements and in
the second uses $O(k\cdot m(1,1,n,\Theta(1/k)))$ measurements. It succeeds
with constant probability.

######  Corollary 4.2.

For $p=2$, there is a $2$-round sparse recovery algorithm for $n$-dimensional
vectors $x$ such that the total number of measurements is
$O(\frac{1}{\epsilon}k\log(k/\epsilon)+k\log(n/k))$.

###### Proof of Corollary 4.2..

In the first round it suffices to use CountSketch with
$s(k,\epsilon,n,1/100)=2k$, which holds for any $\epsilon>0$ [PW11]. We also
have that
$m(k,\epsilon/5,{\mathrm{poly}}(k/\epsilon),1/100)=O(\frac{1}{\epsilon}k\log(k/\epsilon))$.
Using [CCF02, CM06, GI10], in the second round we can set
$m(1,1,n,\Theta(1/k))=O(\log n)$. The bound follows by observing that
$\frac{1}{\epsilon}k\log(k/\epsilon)+k\log(n)=O(\frac{1}{\epsilon}k\log(k/\epsilon)+k\log(n/k))$.
∎

###### Proof of Theorem 4.1..

In the first round we perform a dimensionality reduction of the
$n$-dimensional input vector $x$ to a
${\mathrm{poly}}(k/\epsilon)$-dimensional input vector $y$. We then apply the
black box sparse recovery algorithm on the reduced vector $y$, obtaining a
list of $s(k,\epsilon/5,{\mathrm{poly}}(k/\epsilon),1/100)$ coordinates, and
show for each coordinate in the list, if we choose the largest preimage for it
in $x$, then this list of coordinates can be used to provide a $1+\epsilon$
approximation for $x$. In the second round we then identify which heavy
coordinates in $x$ map to those found in the first round, for which it
suffices to invoke the black box algorithm with only a constant approximation.
We place the estimated values of the heavy coordinates obtained in the first
pass in the locations of the heavy coordinates obtained in the second pass.

Let $N={\mathrm{poly}}(k/\epsilon)$ be determined below. Let
$h:[n]\rightarrow[N]$ and $\sigma:[n]\rightarrow\\{-1,1\\}$ be $\Theta(\log
N)$-wise independent random functions. Define the vector $y$ by
$y_{i}=\sum_{j\ \mid\ h(j)=i}\sigma(j)x_{j}$. Let $Y(i)$ be the vector $x$
restricted to coordinates $j\in[n]$ for which $h(j)=i$. Because the algorithm
is invariant under permutation of coordinates of $y$, we may assume for
simplicity of notation that $y$ is sorted:
$\left|y_{1}\right|\geq\dotsc\geq\left|y_{N}\right|=0$.

We note that such a dimensionality reduction is often used in the streaming
literature. For example, the sketch of [TZ04] for $\ell_{2}$-norm estimation
utilizes such a mapping. A “multishot” version (that uses several functions
$h$) has been used before in the context of sparse recovery [CCF02, CM06] (see
[GI10] for an overview). Here, however, we need to analyze a “single-shot”
version.

Let $p\in\\{1,2\\}$, and consider sparse recovery with the $\ell_{p}/\ell_{p}$
guarantee. We can assume that $\|x\|_{p}=1$. We need two facts concerning
concentration of measure.

######  Fact 4.3.

(see, e.g., Lemma 2 of [KNPW10]) Let $X_{1},\ldots,X_{n}$ be such that $X_{i}$
has expectation $\mu_{i}$ and variance $v_{i}^{2}$, and $X_{i}\leq K$ almost
surely. Then if the $X_{i}$ are $\ell$-wise independent for an even integer
$\ell\geq 2$,

$\Pr\left[\left|\sum_{i=1}^{n}X_{i}-\mu\right|\geq\lambda\right]\leq
2^{O(\ell)}\left(\left(v\sqrt{\ell}/\lambda\right)^{\ell}+\left(K\ell/\lambda\right)^{\ell}\right)$

where $\mu=\sum_{i}\mu_{i}$ and $v^{2}=\sum_{i}v_{i}^{2}$.

######  Fact 4.4.

(Khintchine inequality) ([Haa82]) For $t\geq 2$, a vector $z$ and a $t$-wise
independent random sign vector $\sigma$ of the same number of dimensions,
${\bf E}[|\langle z,\sigma\rangle|^{t}]\leq\|z\|_{2}^{t}(\sqrt{t})^{t}.$

We start with a probabilistic lemma. Let $Z(j)$ denote the vector $Y(j)$ with
the coordinate $m(j)$ of largest magnitude removed.

######  Lemma 4.5.

Let $r=O\left(\|x_{\overline{[k]}}\|_{p}\cdot\frac{\log N}{N^{1/6}}\right)$
and $N$ be sufficiently large. Then with probability $\geq 99/100$,

  1. 1.

$\forall j\in[N]$, $\|Z(j)\|_{p}\leq r$.

  2. 2.

$\forall i\in[N^{1/3}]$, $|\sigma(i)\cdot y_{h(i)}-x_{i}|\leq r$,

  3. 3.

$\|y_{\overline{[k]}}\|_{p}\leq(1+O(1/\sqrt{N}))\cdot\|x_{\overline{[k]}}\|_{p}+O(kr)$,

  4. 4.

$\forall j\in[N]$, if $h^{-1}(j)\cap[N^{1/3}]=\emptyset$, then $|y_{j}|\leq
r$,

  5. 5.

$\forall j\in[N]$, $\|Y(j)\|_{0}=O(n/N+\log N)$.

###### Proof.

We start by defining events $\mathcal{E}$, $\mathcal{F}$ and $\mathcal{G}$
that will be helpful in the analysis, and showing that all of them are
satisfied simultaneously with constant probability.

Event $\mathcal{E}$: Let $\mathcal{E}$ be the event that
$h(1),h(2),\ldots,h(N^{1/3})$ are distinct. Then $\Pr_{h}[\mathcal{E}]\geq
1-1/N^{1/3}$.

Event $\mathcal{F}$: Fix $i\in[N]$. Let $Z^{\prime}$ denote the vector
$Y(h(i))$ with the coordinate $i$ removed. Applying Fact 4.4 with
$t=\Theta(\log N)$,

$\displaystyle\Pr_{\sigma}[|\sigma(i)y_{h(i)}-x_{i}|\geq
2\sqrt{t}\cdot\|Z(h(i))\|_{2}]$ $\displaystyle\leq$
$\displaystyle\Pr_{\sigma}[|\sigma(i)y_{h(i)}-x_{i}|\geq
2\sqrt{t}\cdot\left\lVert Z^{\prime}\right\rVert_{2}]$ $\displaystyle\leq$
$\displaystyle\Pr_{\sigma}[|\sigma(i)y_{h(i)}-x_{i}|^{t}\geq
2^{t}(\sqrt{t})^{t}\cdot\|Z^{\prime}\|_{2}^{t}]$ $\displaystyle\leq$
$\displaystyle\Pr_{\sigma}[|\sigma(i)y_{h(i)}-x_{i}|^{t}\geq
2^{t}\operatorname{\mathbb{E}}[\left|\langle\sigma,Z^{\prime}\rangle\right|^{t}]]$
$\displaystyle=$ $\displaystyle\Pr_{\sigma}[|\sigma(i)y_{h(i)}-x_{i}|^{t}\geq
2^{t}\operatorname{\mathbb{E}}[|\sigma(i)y_{h(i)}-x_{i}|^{t}]\leq 1/N^{4/3}.$

Let $\mathcal{F}$ be the event that for all $i\in[N]$,
$|\sigma(i)y_{h(i)}-x_{i}|\leq 2\sqrt{t}\cdot\|Z(h(i))\|_{2},$ so
$\Pr_{\sigma}[\mathcal{F}]\geq 1-1/N$.

Event $\mathcal{G}$: Fix $j\in[N]$ and for each
$i\in\\{N^{1/3}+1,\ldots,n\\}$, let $X_{i}=|x_{i}|^{p}{\bf 1}_{h(i)=j}$ (i.e.,
$X_{i}=|x_{i}|^{p}$ if $h(i)=j$). We apply Lemma 4.3 to the $X_{i}$. In the
notation of that lemma, $\mu_{i}=|x_{i}|^{p}/N$ and
$v_{i}^{2}\leq|x_{i}|^{2p}/N$, and so
$\mu=\|x_{\overline{[N^{1/3}]}}\|_{p}^{p}/N$ and
$v^{2}\leq\|x_{\overline{[N^{1/3}]}}\|_{2p}^{2p}/N$. Also,
$K=|x_{N^{1/3}+1}|^{p}$. Function $h$ is $\Theta(\log N)$-wise independent, so
by Fact 4.3,

$\displaystyle\Pr\left[\left|\sum_{i}X_{i}-\frac{\|x_{\overline{[N^{1/3}]}}\|_{p}^{p}}{N}\right|\geq\lambda\right]\leq$
$\displaystyle
2^{O(\ell)}\left(\left(\|x_{\overline{[N^{1/3}]}}\|_{2p}^{p}\sqrt{\ell}/(\lambda\sqrt{N})\right)^{\ell}+\left(|x_{N^{1/3}+1}|^{p}\ell/\lambda\right)^{\ell}\right)$

for any $\lambda>0$ and an $\ell=\Theta(\log N)$. For $\ell$ large enough,
there is a

$\lambda=\Theta(\|x_{\overline{[N^{1/3}]}}\|_{2p}^{p}\sqrt{(\log
N)/N}+|x_{N^{1/3}+1}|^{p}\cdot\log N)$

for which this probability is $\leq N^{-2}$. Let $\mathcal{G}$ be the event
that for all $j\in[N]$, $\|Z(j)\|_{p}^{p}\leq
C\left(\frac{\|x_{\overline{[N^{1/3}]}}\|_{p}^{p}}{N}+\lambda\right)$ for some
universal constant $C>0$. Then $\Pr[\mathcal{G}\mid\mathcal{E}]\geq 1-1/N$.

By a union bound, $\Pr[\mathcal{E}\wedge\mathcal{F}\wedge\mathcal{G}]\geq
999/1000$ for $N$ sufficiently large.

We know proceed to proving the five conditions in the lemma statement. In the
analysis we assume that the event
$\mathcal{E}\wedge\mathcal{F}\wedge\mathcal{G}$ holds (i.e., we condition on
that event).

First Condition: This condition follows from the occurrence of $\mathcal{G}$,
and using that
$\|x_{\overline{[N^{1/3}]}}\|_{2p}\leq\|x_{\overline{[N^{1/3}]}}\|_{p}$, and
$\|x_{\overline{[N^{1/3}]}}\|_{p}\leq\|x_{\overline{[k]}}\|_{p}$, as well as
$(N^{1/3}-k+1)|x_{N^{1/3}+1}|^{p}\leq\|x_{\overline{[k]}}\|_{p}^{p}$. One just
needs to make these substitutions into the variable $\lambda$ defining
$\mathcal{G}$ and show the value $r$ serves as an upper bound (in fact, there
is a lot of room to spare, e.g., $r/\log N$ is also an upper bound).

Second Condition: This condition follows from the joint occurrence of
$\mathcal{E}$, $\mathcal{F}$, and $\mathcal{G}$.

Third Condition:  For the third condition, let $y^{\prime}$ denote the
restriction of $y$ to coordinates in the set
$[N]\setminus\\{h(1),h(2),...,h(k)\\}$. For $p=1$ and for any choice of $h$
and $\sigma$, $\|y^{\prime}\|_{1}\leq\|x_{\overline{[k]}}\|_{1}$. For $p=2$,
the vector $y$ is the sketch of [TZ04] for $\ell_{2}$-estimation. By their
analysis, with probability $\geq 999/1000$,
$\|y^{\prime}\|_{2}^{2}\leq(1+O(1/\sqrt{N}))\|x^{\prime}\|_{2}^{2}$, where
$x^{\prime}$ is the vector whose support is
$[n]\setminus\cup_{i=1}^{k}h^{-1}(i)\subseteq[n]\setminus[k]$. We assume this
occurs and add $1/1000$ to our error probability. Hence,
$\|y^{\prime}\|_{2}^{2}\leq(1+O(1/\sqrt{N}))\|x_{\overline{[k]}}\|_{2}^{2}$.

We relate $\|y^{\prime}\|_{p}^{p}$ to $\|y_{\overline{[k]}}\|_{p}^{p}$.
Consider any $j=h(i)$ for an $i\in[k]$ for which $j$ is not among the top $k$
coordinates of $y$. Call such a $j$ lost. By the first condition of the lemma,
$|\sigma(i)y_{j}-x_{i}|\leq r$. Since $j$ is not among the top $k$ coordinates
of $y$, there is a coordinate $j^{\prime}$ among the top $k$ coordinates of
$y$ for which $j^{\prime}\notin h([k])$ and
$|y_{j^{\prime}}|\geq|y_{j}|\geq|x_{i}|-r.$ We call such a $j^{\prime}$ a
substitute. We can bijectively map substitutes to lost coordinates. It follows
that
$\|y_{\overline{[k]}}\|_{p}^{p}\leq\|y^{\prime}\|_{p}^{p}+O(kr)\leq(1+O(1/\sqrt{N}))\|x_{\overline{[k]}}\|_{p}^{p}+O(kr).$

Fourth Condition: This follows from the joint occurrence of
$\mathcal{E},\mathcal{F}$, and $\mathcal{G}$, and using that
$|x_{m(j)}|^{p}\leq\|x_{\overline{[k]}}\|_{p}^{p}/(N^{1/3}-k+1)$ since
$m(j)\notin[N^{1/3}]$.

Fifth Condition: For the fifth condition, fix $j\in[N]$. We apply Fact 4.3
where the $X_{i}$ are indicator variables for the event $h(i)=j$. Then ${\bf
E}[X_{i}]=1/N$ and ${\bf Var}[X_{i}]<1/N$. In the notation of Fact 4.3,
$\mu=n/N$, $v^{2}<n/N$, and $K=1$. Setting $\ell=\Theta(\log N)$ and
$\lambda=\Theta(\log N+\sqrt{(n\log N)/N})$, we have by a union bound that for
all $j\in[N]$, $\|Y(j)\|_{0}\leq\frac{n}{N}+\Theta(\log N+\sqrt{(n\log
N)/N})=O(n/N+\log N)$, with probability at least $1-1/N$.

By a union bound, all events jointly occur with probability at least $99/100$,
which completes the proof. ∎

Event $\mathcal{H}$: Let $\mathcal{H}$ be the event that the algorithm returns
a vector $\hat{y}$ with
$\|\hat{y}-y\|_{p}\leq(1+\epsilon/5)\|y_{\overline{[k]}}\|_{p}.$ Then
$\Pr[\mathcal{H}]\geq 99/100$. Let $S$ be the support of $\hat{y}$, so
$|S|=s(k,\epsilon/5,N,1/100)$. We condition on $\mathcal{H}$.

In the second round we run the algorithm on $Y(j)$ for each $j\in S$, each
using $m(1,1,\|Y(j)\|_{0},\Theta(1/k)))$\- measurements. Using the fifth
condition of Lemma 4.5, we have that $\|Y(j)\|_{0}=O(\epsilon
n/k+\log(k)/\epsilon)$ for $N={\mathrm{poly}}(k/\epsilon)$ sufficiently large.

For each invocation on a vector $Y(j)$ corresponding to a $j\in S$, the
algorithm takes the largest (in magnitude) coordinate HH$(j)$ in the output
vector, breaking ties arbitrarily. We output the vector $\hat{x}$ with support
equal to $T=\\{\textrm{HH}(j)\mid j\in S\\}$. We assign the value
$\sigma(x_{j})\hat{y}_{j}$ to HH$(j)$. We have

$\displaystyle\|x-\hat{x}\|_{p}^{p}=$
$\displaystyle\|(x-\hat{x})_{T}\|_{p}^{p}+\|(x-\hat{x})_{[n]\setminus
T}\|_{p}^{p}=\|(x-\hat{x})_{T}\|_{p}^{p}+\|x_{[n]\setminus T}\|_{p}^{p}.$ (8)

The rest of the analysis is devoted to bounding the RHS of equation 8.

######  Lemma 4.6.

For $N={\mathrm{poly}}(k/\epsilon)$ sufficiently large, conditioned on the
events of Lemma 4.5 and $\mathcal{H}$,

$\|x_{[n]\setminus
T}\|_{p}^{p}\leq(1+\epsilon/3)\|x_{\overline{[k]}}\|_{p}^{p}.$

###### Proof.

If $[k]\setminus T=\emptyset$, the lemma follows by definition. Otherwise, if
$i\in([k]\setminus T)$, then $i\in[k]$, and so by the second condition of
Lemma 4.5, $|x_{i}|\leq|y_{h(i)}|+r.$ We also use the third condition of Lemma
4.5 to obtain
$\|y_{\overline{[k]}}\|_{p}\leq(1+O(1/\sqrt{N}))\cdot\|x_{\overline{[k]}}\|_{p}+O(kr).$
By the triangle inequality,

$\displaystyle\left(\sum_{i\in[k]\setminus T}|x_{i}|^{p}\right)^{1/p}$
$\displaystyle\leq k^{1/p}r+\left(\sum_{i\ \in\ [k]\setminus
T}|y_{h(i)}|^{p}\right)^{1/p}\leq k^{1/p}r+\left(\sum_{i\ \in\ [N]\setminus
S}|y_{i}|^{p}\right)^{1/p}$ $\displaystyle\leq$ $\displaystyle
k^{1/p}r+(1+\epsilon/5)\cdot\|y_{\overline{[k]}}\|_{p}.$

The lemma follows using that $r=O(\|x_{\overline{[k]}}\|_{2}\cdot(\log
N)/N^{1/6})$ and $N={\mathrm{poly}}(k/\epsilon)$ is sufficiently large. ∎

We bound $\|(x-\hat{x})_{T}\|_{p}^{p}$ using Lemma 4.5,
$|S|\leq{\mathrm{poly}}(k/\epsilon)$, and that $N={\mathrm{poly}}(k/\epsilon)$
is sufficiently large.

$\displaystyle\|(x-\hat{x})_{T}\|_{p}\leq$ $\displaystyle\left(\sum_{j\in
S}|x_{HH(j)}-\sigma(HH(j))\cdot\hat{y}_{j}|^{p}\right)^{1/p}\leq\left(\sum_{j\in
S}(|y_{j}-\hat{y}_{j}|+|\sigma(HH(j))\cdot x_{HH(j)}-y_{j}|)^{p}\right)^{1/p}$
$\displaystyle\leq$ $\displaystyle\left(\sum_{j\in
S}|y_{j}-\hat{y}_{j}|^{p}\right)^{1/p}+\left(\sum_{j\in S}|\sigma(HH(j))\cdot
x_{HH(j)}-y_{j}|^{p}\right)^{1/p}$ $\displaystyle\leq$
$\displaystyle(1+\epsilon/5)\|y_{\overline{[k]}}\|_{p}+\left(\sum_{j\in
S}|\sigma(HH(j))\cdot x_{HH(j)}-y_{j}|^{p}\right)^{1/p}$ $\displaystyle\leq$
$\displaystyle(1+\epsilon/5)(1+O(1/\sqrt{N}))\|x_{\overline{[k]}}\|_{p}+O(kr)+\left(\sum_{j\in
S}|\sigma(HH((j))\cdot x_{HH(j)}-y_{j}|^{p}\right)^{1/p}$ $\displaystyle\leq$
$\displaystyle(1+\epsilon/4)\|x_{\overline{[k]}}\|_{p}+\left(\sum_{j\in
S}|\sigma(HH(j))\cdot x_{HH(j)}-y_{j}|^{p}\right)^{1/p}$

Event $\mathcal{I}$: We condition on the event $\mathcal{I}$ that all second
round invocations succeed. Note that $\Pr[\mathcal{I}]\geq 99/100$.

We need the following lemma concerning $1$-sparse recovery algorithms.

######  Lemma 4.7.

Let $w$ be a vector of real numbers. Suppose
$|w_{1}|^{p}>\frac{9}{10}\cdot\|w\|^{p}_{p}$. Then for any vector $\hat{w}$
for which $\|w-\hat{w}\|^{p}_{p}\leq 2\cdot\|w_{\overline{[1]}}\|^{p}_{p}$, we
have $|\hat{w}_{1}|^{p}>\frac{3}{5}\cdot\|w\|_{p}^{p}$. Moreover, for all
$j>1$, $|\hat{w}_{j}|^{p}<\frac{3}{5}\cdot\|w\|_{p}^{p}$.

###### Proof.

$\|w-\hat{w}\|^{p}_{p}\geq|w_{1}-\hat{w}_{1}|^{p}$, so if
$|\hat{w}_{1}|^{p}<\frac{3}{5}\cdot\|w\|^{p}_{p}$, then
$\|w-\hat{w}\|^{p}_{p}>\left(\frac{9}{10}-\frac{3}{5}\right)\|w\|^{p}_{p}=\frac{3}{10}\cdot\|w\|^{p}_{p}$.
On the other hand,
$\|w_{\overline{[1]}}\|_{p}^{p}<\frac{1}{10}\cdot\|w\|_{p}^{p}$. This
contradicts that $\|w-\hat{w}\|^{p}_{p}\leq
2\cdot\|w_{\overline{[1]}}\|_{p}^{p}$. For the second part, for $j>1$ we have
$|w_{j}|^{p}<\frac{1}{10}\cdot\|w\|^{p}_{p}$. Now,
$\|w-\hat{w}\|^{p}_{p}\geq|w_{j}-\hat{w}_{j}|^{p}$, so if
$|\hat{w}_{j}|^{p}\geq\frac{3}{5}\cdot\|w\|_{p}^{p}$, then
$\|w-\hat{w}\|^{p}_{p}>\left(\frac{3}{5}-\frac{1}{10}\right)\|w\|_{p}^{p}=\frac{1}{2}\cdot\|w\|_{p}^{p}$.
But since $\|w_{\overline{[1]}}\|_{p}^{p}<\frac{1}{10}\cdot\|w\|_{p}^{p}$,
this contradicts that $\|w-\hat{w}\|^{p}_{p}\leq
2\cdot\|w_{\overline{[1]}}\|_{p}^{p}$. ∎

It remains to bound $\sum_{j\in S}|\sigma(HH(j))\cdot x_{HH(j)}-y_{j}|^{p}$.
We show for every $j\in S$, $|\sigma(HH(j))\cdot x_{HH(j)}-y_{j}|^{p}$ is
small.

Recall that $m(j)$ is the coordinate of $Y(j)$ with the largest magnitude.
There are two cases.

Case 1: $m(j)\notin[N^{1/3}]$. In this case observe that
$HH(j)\notin[N^{1/3}]$ either, and $h^{-1}(j)\cap[N^{1/3}]=\emptyset$. It
follows by the fourth condition of Lemma 4.5 that $|y_{j}|\leq r$. Notice that
$|x_{HH(j)}|^{p}\leq|x_{m(j)}|^{p}\leq\frac{\|x_{\overline{[k]}}\|_{p}^{p}}{N^{1/3}-k}.$
Bounding $|\sigma(HH(j))\cdot x_{HH(j)}-y_{j}|$ by $|x_{HH(j)}|+|y_{j}|$, it
follows for $N={\mathrm{poly}}(k/\epsilon)$ large enough that
$|\sigma(HH(j))\cdot
x_{HH(j)}-y_{j}|^{p}\leq\epsilon/4\cdot\|x_{\overline{[k]}}\|_{p}/|S|)$.

Case 2: $m(j)\in[N^{1/3}]$. If $HH(j)=m(j)$, then $|\sigma(HH(j))\cdot
x_{HH(j)}-y_{j}|\leq r$ by the second condition of Lemma 4.5, and therefore

$|\sigma(HH(j))\cdot x_{HH(j)}-y_{j}|^{p}\leq
r^{p}\leq\epsilon/4\cdot\|x_{\overline{[k]}}\|_{p}/|S|$

for $N={\mathrm{poly}}(k/\epsilon)$ large enough.

Otherwise, $HH(j)\neq m(j)$. From condition 2 of Lemma 4.5 and
$m(j)\in[N^{1/3}]$, it follows that

$\displaystyle|\sigma(HH(j)))x_{HH(j)}-y_{j}|\leq$
$\displaystyle|\sigma(HH(j))x_{HH(j)}-\sigma(m(j))x_{m(j)}|+|\sigma(m(j))x_{m(j)}-y_{j}|\leq|x_{HH(j)}|+|x_{m(j)}|+r$

Notice that $|x_{HH(j)}|+|x_{m(j)}|\leq 2|x_{m(j)}|$ since $m(j)$ is the
coordinate of largest magnitude. Now, conditioned on $\mathcal{I}$, Lemma 4.7
implies that $|x_{m(j)}|^{p}\leq\frac{9}{10}\cdot\|Y(j)\|_{p}^{p}$, or
equivalently, $|x_{m(j)}|\leq 10^{1/p}\cdot\|Z(j)\|_{p}.$ Finally, by the
first condition of Lemma 4.5, we have $\|Z(j)\|_{p}=O(r)$, and so
$|\sigma(HH(j))x_{HH(j)}-y_{j}|^{p}=O(r^{p})$, which as argued above, is small
enough for $N={\mathrm{poly}}(k/\epsilon)$ sufficiently large.

The proof of our theorem follows by a union bound over the events that we
defined. ∎

##  5 Adaptively Finding a Duplicate in a Data Stream

We consider the following FindDuplicate problem. We are given an adversarially
ordered stream $\mathcal{S}$ of $n$ elements in $\\{1,2,\ldots,n-1\\}$ and the
goal is to output an element that occurs at least twice, with probability at
least $1-\delta$. We seek to minimize the space complexity of such an
algorithm. We improve the space complexity of [JST11] for FindDuplicate from
$O(\log^{2}n)$ bits to $O(\log n)$ bits, though we use $O(\log\log n)$ passes
instead of a single pass. Notice that [JST11] also proves a lower bound of
$\Omega(\log^{2}n)$ bits for a single pass.

We use Lemma 3.3 of our multi-pass sparse recovery algorithm:

######  Fact 5.1.

Suppose there exists an $i$ with $|x_{i}|\geq
C\|x_{[n]\setminus\\{i\\}}\|_{2}$ for some constant $C$. Then $O(\log\log n)$
adaptive measurements suffice to recover a set $T$ of constant size so that
$i\in T$ with probability at least $1/2$. Further, all adaptive measurements
are linear combinations with integer coefficients of magnitude bounded by
${\mathrm{poly}}(n)$.

Our algorithm DuplicateFinder for this problem considers the equivalent
formulation of FindDuplicate in which we think of an underlying frequency
vector $x\in\\{-1,0,1,\ldots,n-1\\}^{n}$. We start by initializing $x_{i}=-1$
for all $i$. Each time item $i$ occurs in the stream, we increment its
frequency by $1$. The task is therefore to output an $i$ for which $x_{i}>0$.

######  Theorem 5.2.

There is an $O(\log\log n)$-pass, $O(\log n\log 1/\delta)$ bits of space per
pass algorithm for solving the FindDuplicate problem with probability at least
$1-\delta$.

###### Proof.

We describe an algorithm DuplicateFinder which succeeds with probability at
least $1/8$. Since it knows whether or not it succeeds, the probability can be
amplified to $1-\delta$ by $O(\log 1/\delta)$ independent parallel
repetitions. It is easy to see that the pass and space complexity are as
claimed, so we prove correctness.

DuplicateFinder($\mathcal{S}$) 1. Repeat the following procedure $C=O(1)$
times independently. (a) Select $O(1)$-wise independent uniform
$t_{i}\in[0,1]$ for $i\in[n]$. (b) Let $\epsilon>0$ be a sufficiently small
constant. Let $m=O(\log 1/\epsilon)$.  (c) Let $z^{1},\ldots,z^{4m}$ be a
pairwise-independent partition of the coordinates of $z$, where
$z=x_{i}/t_{i}$ for all $i$. (d) Run algorithm $A$ independently on vectors
$z^{1},\ldots,z^{4m}$.  (e) Let $T_{1},\ldots,T_{4m}$ be the outputs of
algorithm $A$ on $z^{1},\ldots,z^{4m}$, respectively, as per Fact 5.1.  (f)
Compute each $x_{i}$ for $i\in\cup_{j=1}^{4m}T_{j}$ in an extra pass. If there
is an $i$ for which $x_{i}>0$, then output $i$.  2. If no coordinate $i$ has
been output, then output fail.

We use the following fact shown in the proof of Lemma 3 of [JST11].

######  Lemma 5.3.

(see first paragraph of Lemma 3 of [JST11]) For a single index $i\in[n]$ and
$t$ arbitrary, we have

$\Pr[\|z_{\overline{H_{m}(z)}}\|_{2}>\frac{1}{20}\sqrt{m}\|x\|_{1}\mid
t_{i}=t]=O(\epsilon),$

where $H_{m}(z)$ denotes the set of $m$ largest (in magnitude) coordinates of
$z$. Suppose $|z_{i}|>\|x\|_{1}$ for some value of $i$. This happens if
$t_{i}<\frac{|x_{i}|}{\|x\|_{1}}$ and occurs with probability equal to
$\frac{|x_{i}|}{\|x\|_{1}}$. Conditioned on this event, by Lemma 5.3 we have
that with probability $1-O(\epsilon)$,

$\|z_{\overline{H_{m}(z)}}\|_{2}\leq\frac{1}{20}\sqrt{m}\|x\|_{1}.$

Suppose $i$ occurs in $z^{j}$ for some value of $j\in[4m]$. Since the
partition is pairwise-independent, the expected number of $\ell\in
H_{m}(z)\setminus\\{i\\}$ which occur in $z^{j}$ is at most $\frac{m}{4m}$,
and so with probability at least $3/4-O(\epsilon)$, the norm of $z^{j}$ with
coordinate corresponding to coordinate $i$ in $z$ removed is at most

$\|z_{\overline{H_{m}(z)}}\|_{2}\leq\frac{1}{20}\sqrt{m}\|x\|_{1}\leq\frac{1}{20}\sqrt{m}|z_{i}|.$

Since $m$ is a constant, by Fact 5.1, with probability at least $1/2$, $A$
outputs a set $T$ which contains coordinate $i$. Hence, with probability at
least $3/8-O(\epsilon)$, if there is an $i$ for which $|z_{i}|>\|x\|_{1}$, it
is found by DuplicateFinder.

Let $p_{i}=\frac{|x_{i}|}{\|x\|_{1}}$. Then $|z_{i}|>\|x\|_{1}$ with
probability $p_{i}$. Since $\sum_{i}x_{i}>0$, we have $\sum_{i\ \mid\
x_{i}>0}p_{i}>\frac{1}{2}$. Consider one of the $C=O(1)$ independent
repetitions of step 1.

For coordinates $i$ for which $x_{i}>0$, let $W_{i}=1$ if $|z_{i}|>\|x\|_{1}$,
and let $W=\sum_{i}W_{i}$. Then ${\bf E}[W]>1/2$ and by pairwise-independence,
${\bf Var}[W]\leq{\bf E}[W]$.

Let $W^{\prime}$ be the average of the random variable $W$ over $C$
independent repetitions. Then ${\bf E}[W^{\prime}]={\bf E}[W]>\frac{1}{2}$ and
${\bf Var}[W^{\prime}]\leq\frac{{\bf E}[W]}{C}$, and so by Chebyshev’s
inequality for $C=O(1)$ sufficiently large we have that with probability at
least $\frac{1}{2}$, $W^{\prime}>0$, which means that in one of the $C$
repetitions there is a coordinate $i$ for which $x_{i}>0$ and
$|z_{i}|>\|x\|_{1}$.

Hence, the overall probability of success is at least
$1/2\cdot(3/8-O(\epsilon))>1/8$, for $\epsilon$ sufficiently small. This
completes the proof. ∎

## Acknowledgements

This material is based upon work supported by the Space and Naval Warfare
Systems Center Pacific under Contract No. N66001-11-C-4092, David and Lucille
Packard Fellowship, MADALGO (Center for Massive Data Algorithmics, funded by
the Danish National Research Association) and NSF grant CCF-1012042. E. Price
is supported in part by an NSF Graduate Research Fellowship.

## References

  * [AWZ08] A. Aldroubi, H. Wang, and K. Zarringhalam.  Sequential adaptive compressed sampling via huffman codes.  Preprint, 2008.
  * [BGK+10] A. Bruex, A. Gilbert, R. Kainkaryam, John Schiefelbein, and Peter Woolf.  Poolmc: Smart pooling of mRNA samples in microarray experiments.  BMC Bioinformatics, 2010.
  * [CCF02] M. Charikar, K. Chen, and M. Farach-Colton.  Finding frequent items in data streams.  ICALP, 2002.
  * [CHNR08] R. Castro, J. Haupt, R. Nowak, and G. Raz.  Finding needles in noisy haystacks.  Proc. IEEE Conf. Acoustics, Speech, and Signal Proc., page 5133 5136, 2008.
  * [CM04] G. Cormode and S. Muthukrishnan.  Improved data stream summaries: The count-min sketch and its applications.  LATIN, 2004.
  * [CM06] G. Cormode and S. Muthukrishnan.  Combinatorial algorithms for Compressed Sensing.  In Proc. 40th Ann. Conf. Information Sciences and Systems, Princeton, Mar. 2006.
  * [CRT06] E. J. Candès, J. Romberg, and T. Tao.  Stable signal recovery from incomplete and inaccurate measurements.  Comm. Pure Appl. Math., 59(8):1208–1223, 2006.
  * [DDT+08] M. Duarte, M. Davenport, D. Takhar, J. Laska, T. Sun, K. Kelly, and R. Baraniuk.  Single-pixel imaging via compressive sampling.  IEEE Signal Processing Magazine, 2008.
  * [Def10] Defense Sciences Office.  Knowledge enhanced compressive measurement.  Broad Agency Announcement, DARPA-BAA-10-38, 2010.
  * [DIPW10] K. Do Ba, P. Indyk, E. Price, and D. Woodruff.  Lower bounds for sparse recovery.  SODA, 2010.
  * [Don06] D. L. Donoho.  Compressed Sensing.  IEEE Trans. Info. Theory, 52(4):1289–1306, Apr. 2006.
  * [FPRU10] S. Foucart, A. Pajor, H. Rauhut, and T. Ullrich.  The gelfand widths of lp-balls for $0<p\leq 1$.  J. Complexity, 2010.
  * [GG84] A. Y. Garnaev and E. D. Gluskin.  On widths of the euclidean ball.  Sov. Math., Dokl., page 200 204, 1984.
  * [GGI+02] A. C. Gilbert, S. Guha, P. Indyk, Y. Kotidis, S. Muthukrishnan, and M. J. Strauss.  Fast, small-space algorithms for approximate histogram maintenance.  In ACM Symposium on Theoretical Computer Science, 2002.
  * [GI10] A. Gilbert and P. Indyk.  Sparse recovery using sparse matrices.  Proceedings of IEEE, 2010.
  * [GLPS10] Anna C. Gilbert, Yi Li, Ely Porat, and Martin J. Strauss.  Approximate sparse recovery: optimizing time and measurements.  In STOC, pages 475–484, 2010.
  * [Glu84] E. D. Gluskin.  Norms of random matrices and widths of finite-dimensional sets.  Math. USSR-Sb., 48:173 182, 1984.
  * [Haa82] Uffe Haagerup.  The best constants in the Khintchine inequality.  Studia Math., 70(3):231–283, 1982.
  * [HBCN09] J. Haupt, R. Baraniuk, R. Castro, and R. Nowak.  Compressive distilled sensing.  Asilomar, 2009.
  * [HCN09] J. Haupt, R. Castro, and R. Nowak.  Adaptive sensing for sparse signal recovery.  Proc. IEEE 13th Digital Sig. Proc./5th Sig. Proc. Education Workshop, page 702 707, 2009.
  * [Ind07] P. Indyk.  Sketching, streaming and sublinear-space algorithms.  Graduate course notes, available at http://stellar.mit.edu/S/course/6/fa07/6.895/, 2007.
  * [JST11] Hossein Jowhari, Mert Saglam, and Gábor Tardos.  Tight bounds for lp samplers, finding duplicates in streams, and related problems.  In PODS, pages 49–58, 2011.
  * [JXC08] S. Ji, Y. Xue, and L. Carin.  Bayesian compressive sensing.  IEEE Trans. Signal Processing, 56(6):2346 2356, 2008.
  * [Kas77] B. S. Kashin.  Diameters of some finite-dimensional sets and classes of smooth functions.  Math. USSR, Izv.,, 11:317 333, 1977.
  * [KNPW10] Daniel M. Kane, Jelani Nelson, Ely Porat, and David P. Woodruff.  Fast moment estimation in data streams in optimal space.  CoRR, abs/1007.4191, 2010.
  * [McG09] A. McGregor.  Graph mining on streams.  Encyclopedia of Database Systems, page 1271 1275, 2009.
  * [MSW08] D. M. Malioutov, S. Sanghavi, and A. S. Willsky.  Compressed sensing with sequential observations.  ICASSP, 2008.
  * [Mut05] S. Muthukrishnan.  Data streams: Algorithms and applications).  Foundations and Trends in Theoretical Computer Science, 2005.
  * [PW11] E. Price and D. Woodruff.  (1+eps)-approximate sparse recovery.  FOCS, 2011.
  * [SAZ10] N. Shental, A. Amir, and Or Zuk.  Identification of rare alleles and their carriers using compressed se(que)nsing.  Nucleic Acids Research, 38(19):1–22, 2010.
  * [TZ04] Mikkel Thorup and Yin Zhang.  Tabulation based 4-universal hashing with applications to second moment estimation.  In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 615–624, 2004.