Sparse recovery under weak moment assumptions (Q520739)

The paper is focused on data acquisition framework, addressing the idea of compressed sensing (high-dimensional data being described using low-dimensional approximating structures involving randomness). The identically and independently distributed random vector satisfying weak moment hypothesis are proved to be usable as measurement vectors in compressed sensing, the number of measurements for exact reconstruction being the same as the best possible estimate. The necessity of the moment condition up to a log log factor is also proved. In the end, two conditions are analyzed in the noisy setup (compatibility and restricted eigenvalue condition) and also the properties of neighbourly random polytopes.