Universal compressed sensing

Abstract

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 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 minimum entropy pursuit (Lagrangian-MEP) algorithm, originally proposed by Baron et al. as a heuristic universal recovery algorithm, is studied. It is shown that, if the normalized number of randomized measurements is larger than the ID of the source process, for the right set of parameters, asymptotically, the Lagrangian-MEP algorithm recovers any stationary process satisfying some mixing constraints almost losslessly, without having any prior information about the source distribution.