2014/01/09 by Guillaume Lecué, Shahar Mendelson, Lecué, Guillaume +1
Mathematics · #FOS: Mathematics #Probability (math.PR) #Statistics Theory (math.ST) #math.PR #math.ST #stat.TH
paper · pdf · doi:10.48550/arxiv.1401.2188
arxiv created 2015/03/03 · arxiv updated 2016/02/22
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. Applications to the Compatibility Condition and the Restricted Eigenvalue Condition in the noisy setup and to properties of neighbourly random polytopes are also discussed.