Sparse recovery with pre-Gaussian random matrices

作者：Foucart Simon^*; Lai Ming Jun

来源：Studia Mathematica, 2010, 200(1): 91-102.

DOI：10.4064/sm200-1-6

• random matrices
• pre-Gaussian random variables
• sparse recovery
• compressed sensing
• l(1)-minimization

For an m x 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 l(1)-minimization under the optimal condition m >= cs ln(eN/s). The main ingredient of the proof is a variation of a classical Restricted Isometry Property, where the inner norm becomes the l(1)-norm and the outer norm depends on probability distributions.

• 出版日期2010