Universal Compressed Sensing for Almost Lossless Recovery

In this paper, the problem of developing universal algorithms for noiseless compressed sensing of stochastic processes is studied. First, Rényi's notion of information dimension (ID) is generalized to continuous-valued discrete-time stationary processes. This provides a measure of complexity for such processes and is connected to the rate of measurement (sampling rate) required for their accurate recovery. Then, based on Occam's razor, a minimum entropy pursuit (MEP) optimization approach for universal compressed sensing is proposed. It is proven that, for any stationary process satisfying certain mixing conditions, if the sampling rate is larger than the ID of the source process, MEP optimization can reliably recover the source vector almost losslessly, without having any prior information about its distribution. Then, a Lagrangian-type relaxation of MEP optimization problem, referred to as Lagrangian-MEP, is studied. It is shown that Lagrangian-MEP is identical to an implementable algorithm proposed by Baron and coauthors, and for the right choice of parameters, has the same asymptotic performance as MEP optimization. Finally, it is proven that Lagrangian-MEP is robust to small measurement noise.