  In the problem of adaptive compressed sensing, one wants to estimate an
approximately $k$-sparse vector $x\in\mathbb{R}^n$ from $m$ linear measurements
$A_1 x, A_2 x,\ldots, A_m x$, where $A_i$ can be chosen based on the outcomes
$A_1 x,\ldots, A_{i-1} x$ of previous measurements. The goal is to output a
vector $\hat{x}$ for which $$\|x-\hat{x}\|_p \le C \cdot \min_{k\text{-sparse }
x'} \|x-x'\|_q\,$$ with probability at least $2/3$, where $C > 0$ is an
approximation factor. Indyk, Price and Woodruff (FOCS'11) gave an algorithm for
$p=q=2$ for $C = 1+\epsilon$ with $\Oh((k/\epsilon) \loglog (n/k))$
measurements and $\Oh(\log^*(k) \loglog (n))$ rounds of adaptivity. We first
improve their bounds, obtaining a scheme with $\Oh(k \cdot \loglog (n/k)
+(k/\epsilon) \cdot \loglog(1/\epsilon))$ measurements and $\Oh(\log^*(k)
\loglog (n))$ rounds, as well as a scheme with $\Oh((k/\epsilon) \cdot \loglog
(n\log (n/k)))$ measurements and an optimal $\Oh(\loglog (n))$ rounds. We then
provide novel adaptive compressed sensing schemes with improved bounds for
$(p,p)$ for every $0 < p < 2$. We show that the improvement from $O(k
\log(n/k))$ measurements to $O(k \log \log (n/k))$ measurements in the adaptive
setting can persist with a better $\epsilon$-dependence for other values of $p$
and $q$. For example, when $(p,q) = (1,1)$, we obtain
$O(\frac{k}{\sqrt{\epsilon}} \cdot \log \log n \log^3 (\frac{1}{\epsilon}))$
measurements.
