For an m × 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 ℓ₁-minimization under the optimal condition m ≥ csln(eN/s). The main ingredient of the proof is a variation of a classical Restricted Isometry Property, where the inner norm becomes the ℓ₁-norm and the outer norm depends on probability distributions.
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-sm200-1-6,
author = {Simon Foucart and Ming-Jun Lai},
title = {Sparse recovery with pre-Gaussian random matrices},
journal = {Studia Mathematica},
volume = {196},
year = {2010},
pages = {91-102},
zbl = {1205.15007},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-sm200-1-6}
}
Simon Foucart; Ming-Jun Lai. Sparse recovery with pre-Gaussian random matrices. Studia Mathematica, Tome 196 (2010) pp. 91-102. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-sm200-1-6/