Compressed Sensing via Compression Codes

Shirin Jalali, H. Vincent Poor

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

In compressed sensing (CS) a signal x ∈ Rn is measured as y =A x + z, where A ∈ Rm×n (m<n) and z ∈ Rm denote the sensing matrix and measurement noise. The goal is to recover x from measurements y when m<n. CS is possible because we typically want to capture highly structured signals, and recovery algorithms take advantage of a signal’s structure to solve the under-determined system of linear equations. As in CS, data-compression codes take advantage of a signal’s structure to encode it efficiently. Structures used by compression codes are much more elaborate than those used by CS algorithms. Using more complex structures in CS, like those employed by data-compression codes, potentially leads to more efficient recovery methods requiring fewer linear measurements or giving better reconstruction quality. We establish connections between data compression and CS, giving CS recovery methods based on compression codes, which indirectly take advantage of all structures used by compression codes. This elevates the class of structures used by CS algorithms to those used by compression codes, leading to more efficient CS recovery methods.

Original languageEnglish (US)
Title of host publicationInformation-Theoretic Methods in Data Science
PublisherCambridge University Press
Pages72-103
Number of pages32
ISBN (Electronic)9781108616799
ISBN (Print)9781108427135
DOIs
StatePublished - Jan 1 2021
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • General Engineering
  • General Computer Science
  • General Social Sciences
  • General Mathematics

Keywords

  • compressed sensing
  • compression codes
  • distortion-rate
  • rate-distortion
  • sampling

Fingerprint

Dive into the research topics of 'Compressed Sensing via Compression Codes'. Together they form a unique fingerprint.

Cite this