Sparse recovery under weak moment assumptions

Guillaume Lecue, Shahar Mendelson

Research output: Contribution to journalArticlepeer-review

38 Citations (Scopus)

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 then show 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.

Original languageEnglish
Pages (from-to)881-904
Number of pages24
JournalJournal of the European Mathematical Society
Volume19
Issue number3
DOIs
Publication statusPublished - 2017
Externally publishedYes

Fingerprint

Dive into the research topics of 'Sparse recovery under weak moment assumptions'. Together they form a unique fingerprint.

Cite this