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.

该研究考虑了从子采样随机卷积中恢复稀疏向量的问题，并通过结合小球估计和链式技巧来改进以前的估计，并使用称为鲁棒零空间性质的方法展示了我们的结果。