Universal Compressed Sensing

In this paper, the problem of developing universal algorithms for compressed sensing of stochastic processes is studied. First, Renyi's notion of information dimension (ID) is generalized to analog stationary processes. This provides a measure of complexity for such processes and is connected to the number of measurements required for their accurate recovery. Then the so-called Lagrangian-MEP algorithm, originally proposed by Baron et al. as a heuristic universal recovery algorithms, is studied. It is shown that the Lagrangian-MEP algorithm, for the right set of parameters, recovers any stationary process satisfying some mixing constraints from sufficient number of randomized linear measurements. For memoryless sources with a discrete-continuous mixture distribution, it is proved that there is no loss in universal coding, and the Lagrangian-MEP algorithm asymptotically achieves the fundamental limits of compressed sensing.