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 l(1)-noise to signal ratio (l(1)-NSR) sense with an arbitrary close to zero number of measurements per signal dimension.