Abstract

This work elaborates connections between notions of compressibility of infinite sequences, recently addressed by Amini et al. [1], and the performance of the compressed sensing (CS) type of recovery algorithms from linear measurements in the under-sample scenario. In particular, in the asymptotic regime when the signal dimension goes to infinity, we established a new set of compressibility definitions over infinite sequences that guarantees arbitrary good performance in an ?1-noise to signal ratio (?1-NSR) sense with an arbitrary close to zero number of measurements per signal dimension. © 2012 APSIPA.