Sparse recovery with pre-Gaussian random matrices
Volume 200 / 2010
Studia Mathematica 200 (2010), 91-102
MSC: Primary 15B52; Secondary 60B20, 46B09, 94A12.
DOI: 10.4064/sm200-1-6
Abstract
For an $m \times N$ underdetermined system of linear equations with independent pre-Gaussian random coefficients satisfying simple moment conditions, it is proved that the $s$-sparse solutions of the system can be found by $\ell_1$-minimization under the optimal condition $m \ge c s \ln(e N /s)$. The main ingredient of the proof is a variation of a classical Restricted Isometry Property, where the inner norm becomes the $\ell_1$-norm and the outer norm depends on probability distributions.
