Sparse recovery under weak moment assumptions

  • Guillaume Lecué

    Ecole Polytechnique, Palaiseau, France
  • Shahar Mendelson

    Technion, Haifa, Israel

Abstract

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