Democracy in action: Quantization, saturation, and compressive sensing

Jason N. Laska, Petros T. Boufounos, Mark A. Davenport, Richard G. Baraniuk

Research output: Contribution to journalArticlepeer-review

180 Scopus citations


Recent theoretical developments in the area of compressive sensing (CS) have the potential to significantly extend the capabilities of digital data acquisition systems such as analog-to-digital converters and digital imagers in certain applications. To date, most of the CS literature has been devoted to studying the recovery of sparse signals from a small number of linear measurements. In this paper, we study more practical CS systems where the measurements are quantized to a finite number of bits; in such systems some of the measurements typically saturate, causing significant nonlinearity and potentially unbounded errors. We develop two general approaches to sparse signal recovery in the face of saturation error. The first approach merely rejects saturated measurements; the second approach factors them into a conventional CS recovery algorithm via convex consistency constraints. To prove that both approaches are capable of stable signal recovery, we exploit the heretofore relatively unexplored property that many CS measurement systems are democratic, in that each measurement carries roughly the same amount of information about the signal being acquired. A series of computational experiments indicate that the signal acquisition error is minimized when a significant fraction of the CS measurements is allowed to saturate (10-30% in our experiments). This challenges the conventional wisdom of both conventional sampling and CS.

Original languageEnglish (US)
Pages (from-to)429-443
Number of pages15
JournalApplied and Computational Harmonic Analysis
Issue number3
StatePublished - Nov 2011


  • Compressive sensing
  • Consistent reconstruction
  • Quantization
  • Saturation

ASJC Scopus subject areas

  • Applied Mathematics


Dive into the research topics of 'Democracy in action: Quantization, saturation, and compressive sensing'. Together they form a unique fingerprint.

Cite this