Let $A$ be an $m \times n$ random matrix, where each entry is an i.i.d.sub-exponential random variable with mean 0 and variance $\frac{ 1}{ m^2}$. We demonstrate that, with high probability, the sub-exponential matrix $A$ can be used for the exact reconstruction of $s$-sparse vectors via $\ell_1$-minimization, provided that $m \ge C_1 s \log\left(\frac{ C_2 n}{ s}\right)$. This improves upon the existing results by Adamczak et al.
Categories: math.PR