Universal Compressed Sensing for Almost Lossless Recovery

Shirin Jalali, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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.

Original languageEnglish (US)
Article number7862255
Pages (from-to)2933-2953
Number of pages21
JournalIEEE Transactions on Information Theory
Issue number5
StatePublished - May 2017

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


  • Universal coding
  • compressed sensing
  • information dimension
  • mixing processes


Dive into the research topics of 'Universal Compressed Sensing for Almost Lossless Recovery'. Together they form a unique fingerprint.

Cite this