Lossless Linear Analog Compression

Abstract

We establish the fundamental limits of lossless linear analog compression by considering the recovery of random vectors $\mathsf{x}\in {\mathbb{R}}^m$ from the noiseless linear measurements $\mathsf{y}=\mathbf{A}\mathsf{x}$ with measurement matrix $\mathbf{A}\in {\mathbb{R}}^{n\times m}$. Specifically, for a random vector $\mathsf{x}\in {\mathbb{R}}^m$ of arbitrary distribution we show that $\mathsf{x}$ can be recovered with zero error probability from $n>\inf {\underline{\dim }}_{\mathrm{MB}}(U)$ linear measurements, where ${\underline{\dim }}_{\mathrm{MB}}(\cdot )$ denotes the lower modified Minkowski dimension and the infimum is over all sets $U\subseteq {\mathbb{R}}^m$ with $\mathbb{P}[\mathsf{x}\in U]=1$. This achievability statement holds for Lebesgue almost all measurement matrices $\mathbf{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\ge s$ to be necessary for successful recovery of $\mathsf{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 $\mathsf{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.