Sparse recovery with pre-Gaussian random matrices

Tom 200 / 2010

Simon Foucart, Ming-Jun Lai Studia Mathematica 200 (2010), 91-102 MSC: Primary 15B52; Secondary 60B20, 46B09, 94A12. DOI: 10.4064/sm200-1-6


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.


  • Simon FoucartLaboratoire J.-L. Lions
    Université Pierre et Marie Curie
    75013 Paris, France
  • Ming-Jun LaiDepartment of Mathematics
    University of Georgia
    Athens, GA 30602, U.S.A.

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek