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 language | English |
---|---|
Pages (from-to) | 881-904 |
Number of pages | 24 |
Journal | Journal of the European Mathematical Society |
Volume | 19 |
Issue number | 3 |
DOIs | |
Publication status | Published - 2017 |
Externally published | Yes |