JournalsjemsVol. 19, No. 3pp. 881–904

Sparse recovery under weak moment assumptions

  • Guillaume Lecué

    Ecole Polytechnique, Palaiseau, France
  • Shahar Mendelson

    Technion, Haifa, Israel
Sparse recovery under weak moment assumptions cover

A subscription is required to access this article.


We prove that iid random vectors that satisfy a rather weak moment assumption can be used as measurement vectors in Compressed Sensing, and the number of measurements required for exact reconstruction is the same as the best possible estimate – exhibited by a random Gaussian matrix. We also prove that this moment condition is necessary, up to a log log factor. In addition, we explore the Compatibility Condition and the Restricted Eigenvalue Condition in the noisy setup, as well as properties of neighbourly random polytopes.

Cite this article

Guillaume Lecué, Shahar Mendelson, Sparse recovery under weak moment assumptions. J. Eur. Math. Soc. 19 (2017), no. 3, pp. 881–904

DOI 10.4171/JEMS/682