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