Lossless linear analog compression

We establish the fundamental limits of lossless linear analog compression by considering the recovery of random vectors x is an element of R-m from the noiseless linear measurements y = Ax with measurement matrix A is an element of R-n x m Specifically, for a random vector x is an element of R-m of arbitrary distribution we show that x can be recovered with zero error probability from n > inf dim/(M B) (U) linear measurements, where dim/(MB) (.) denotes the lower modified Minkowski dimension and the infimum is over all sets U subset of R-m with P[x is an element of U] = 1. This achievability statement holds for Lebesgue almost all measurement matrices A. We then show that s-rectifiable random vectors-a stochastic generalization of s-sparse vectors-can be recovered with zero error probability from n > s linear measurements. From classical compressed sensing theory we would expect n >= s to be necessary for successful recovery of x. Surprisingly, certain classes of s rectifiable random vectors can be recovered from fewer than s measurements. Imposing an additional regularity condition on the distribution of s-rectifiable random vectors x, we do get the expected converse result of s measurements being necessary. The resulting class of random vectors appears to be new and will be referred to as s-analytic random vectors.