Universal compressed sensing

Shirin Jalali, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 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 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.

Original languageEnglish (US)
Title of host publicationProceedings - ISIT 2016; 2016 IEEE International Symposium on Information Theory
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Electronic)9781509018062
StatePublished - Aug 10 2016
Event2016 IEEE International Symposium on Information Theory, ISIT 2016 - Barcelona, Spain
Duration: Jul 10 2016Jul 15 2016

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2016 IEEE International Symposium on Information Theory, ISIT 2016

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


  • Compressed Sensing
  • Information Dimension
  • Mixing processes
  • Universal coding


Dive into the research topics of 'Universal compressed sensing'. Together they form a unique fingerprint.

Cite this