Improved bounds for sparse recovery from subsampled random convolutions

Abstract

We study the recovery of sparse vectors from subsampled random convolutions via ${\ell }_1$-minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a subgaussian generator with independent entries, we improve previously known estimates: if the sparsity $s$ is small enough, i.e., $s\lesssim \sqrt{n/\log (n)}$, we show that $m\gtrsim s\log (en/s)$ measurements are sufficient to recover $s$-sparse vectors in dimension $n$ with high probability, matching the well-known condition for recovery from standard Gaussian measurements. If $s$ is larger, then essentially $m\ge s{\log }^2(s)\log (\log (s))\log (n)$ measurements are sufficient, again improving over previous estimates. Our results are shown via the so-called robust null space property which is weaker than the standard restricted isometry property. Our method of proof involves a novel combination of small ball estimates with chaining techniques {which should be of independent interest.

34 pages