Improved Algorithms for Adaptive Compressed Sensing

Abstract

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,\dots ,A_{m}x$, where $A_i$ can be chosen based on the outcomes $A_{1}x,\dots ,A_{i-1}x$ of previous measurements. The goal is to output a vector $\hat{x}$ for which $$\Vert x-\hat{x}{\Vert }_p\le C\cdot \underset{k\text{-sparse }{x}^{\prime }}{\min }\Vert x-x^{\prime }{\Vert }_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/ε) \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/ε) \cdot \loglog(1/ε))$ measurements and $\Oh(\log^*(k) \loglog (n))$ rounds, as well as a scheme with $\Oh((k/ε) \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.

To appear in ICALP 2018