Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


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 \[ \norm{p}{x-x^*} \le C \min_{k\text{-sparse } x'} \norm{q}{x-x'} \] 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)$ {\em non-adaptive} measurements~\cite{CRT06:Stable-Signal} and that this bound is tight~\cite{DIPW,FPRU}. In this paper we show that if one is allowed to perform measurements that are {\em 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}{\eps}k \log \log (n\eps/k))$ measurements that uses $O(\sqrt{\log k} \cdot \log \log (n\eps/k))$ rounds. This is a significant improvement over the {\em best possible} non-adaptive bound. * A scheme with $m=O(\frac{1}{\eps}k \log (k/\eps) + k \log (n/k))$ measurements that uses {\em two} rounds. This improves over the {\em best known} non-adaptive bound. To the best of our knowledge, these are the first results of this type.

Questions and Answers

You need to be logged in to be able to post here.