Lossless linear analog compression

We establish the fundamental limits of lossless linear analog compression by considering the recovery of random vectors x in R^m from the noiseless linear measurements y = Ax with measurement matrix A in R^{n times m}. Specifically, for a random vector x in R^m of arbitrary distribution we show that x can be recovered with zero error probability from n > inf dim_{MB}(U) linear measurements, where dim_{MB}(.) denotes the lower modified Minkowski dimension and the infimum is over all sets U contained in R^m with P[x is in 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.