  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 \geq 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.
