1Laboratoire J.-L. Lions Université Pierre et Marie Curie 75013 Paris, France 2Department of Mathematics University of Georgia Athens, GA 30602, U.S.A.
Studia Mathematica, Tome 200 (2010) no. 1, pp. 91-102
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.
Keywords:
times underdetermined system linear equations independent pre gaussian random coefficients satisfying simple moment conditions proved s sparse solutions system found ell minimization under optimal condition main ingredient proof variation classical restricted isometry property where inner norm becomes ell norm outer norm depends probability distributions
Affiliations des auteurs :
Simon Foucart
1
;
Ming-Jun Lai
2
1
Laboratoire J.-L. Lions Université Pierre et Marie Curie 75013 Paris, France
2
Department of Mathematics University of Georgia Athens, GA 30602, U.S.A.
@article{10_4064_sm200_1_6,
author = {Simon Foucart and Ming-Jun Lai},
title = {Sparse recovery with {pre-Gaussian} random matrices},
journal = {Studia Mathematica},
pages = {91--102},
year = {2010},
volume = {200},
number = {1},
doi = {10.4064/sm200-1-6},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.4064/sm200-1-6/}
}
TY - JOUR
AU - Simon Foucart
AU - Ming-Jun Lai
TI - Sparse recovery with pre-Gaussian random matrices
JO - Studia Mathematica
PY - 2010
SP - 91
EP - 102
VL - 200
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.4064/sm200-1-6/
DO - 10.4064/sm200-1-6
LA - en
ID - 10_4064_sm200_1_6
ER -
%0 Journal Article
%A Simon Foucart
%A Ming-Jun Lai
%T Sparse recovery with pre-Gaussian random matrices
%J Studia Mathematica
%D 2010
%P 91-102
%V 200
%N 1
%U http://geodesic.mathdoc.fr/articles/10.4064/sm200-1-6/
%R 10.4064/sm200-1-6
%G en
%F 10_4064_sm200_1_6
Simon Foucart; Ming-Jun Lai. Sparse recovery with pre-Gaussian random matrices. Studia Mathematica, Tome 200 (2010) no. 1, pp. 91-102. doi: 10.4064/sm200-1-6
