Abstract : 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 ℓ1-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 ℓ1-norm and the outer norm depends on probability distributions.
Type de document :
Article dans une revue
Studia Mathematica, INSTYTUT MATEMATYCZNY * POLSKA AKADEMIA NAUK, 2010, 200, pp.91--102. 〈10.4064/sm200-1-6〉
https://hal.inria.fr/hal-00767062
Contributeur : Rémi Gribonval
<>
Soumis le : mercredi 19 décembre 2012 - 14:18:26
Dernière modification le : vendredi 16 novembre 2018 - 01:55:10
Simon Foucart, Ming-Jun Lai. Sparse recovery with pre-Gaussian random matrices. Studia Mathematica, INSTYTUT MATEMATYCZNY * POLSKA AKADEMIA NAUK, 2010, 200, pp.91--102. 〈10.4064/sm200-1-6〉. 〈hal-00767062〉
