Compression-Based Compressed Sensing

Farideh E. Rezagah, Shirin Jalali, Elza Erkip, H. Vincent Poor

Research output: Contribution to journalArticle

Abstract

Modern compression codes exploit signals' complex structures to encode them very efficiently. On the other hand, compressed sensing algorithms recover 'structured' signals from their under-determined set of linear measurements. Currently, there is a noticeable gap between the types of structures used in the area of compressed sensing and those employed by state-of-the-art compression codes. Recent results in the literature on deterministic signals aim at bridging this gap through devising compressed sensing decoders that employ compression codes. This paper focuses on structured stochastic processes and studies application of lossy compression codes to compressed sensing of such signals. The performance of the formerly proposed compressible signal pursuit (CSP) optimization is studied in this stochastic setting. It is proved that in the low-distortion regime, as the blocklength grows to infinity, the CSP optimization reliably and robustly recovers n instances of a stationary process from its random linear measurements as long as n is slightly more than n times the rate-distortion dimension (RDD) of the source. It is also shown that under some regularity conditions, the RDD of a stationary process is equal to its information dimension. This connection establishes the optimality of CSP at least for memoryless stationary sources, which have known fundamental limits. Finally, it is shown that CSP combined by a family of universal variable-length fixed-distortion compression codes yields a family of universal compressed sensing recovery algorithms.

Original languageEnglish (US)
Article number7979584
Pages (from-to)6735-6752
Number of pages18
JournalIEEE Transactions on Information Theory
Volume63
Issue number10
DOIs
StatePublished - Oct 2017

Keywords

  • Compressed sensing
  • information dimension
  • lossy compression
  • rate-distortion dimension
  • universal compression

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'Compression-Based Compressed Sensing'. Together they form a unique fingerprint.

  • Cite this

    Rezagah, F. E., Jalali, S., Erkip, E., & Poor, H. V. (2017). Compression-Based Compressed Sensing. IEEE Transactions on Information Theory, 63(10), 6735-6752. [7979584]. https://doi.org/10.1109/TIT.2017.2726549