Improved bounds for sparse recovery from subsampled random convolutions

We study the recovery of sparse vectors from subsampled random convolutions via ℓ1-minimization. We consider the setup in which both the subsampling locations as well as the generating vector are chosen at random. For a sub-Gaussian generator with independent entries, we improve previously known estimates: If the sparsity s is small enough, that is, s ≤ √ n/ log(n), we show that m ≥ 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 ≥ s log²(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.