Sobolev Duals for Random Frames and ΣΔ Quantization of Compressed Sensing Measurements

C. S. Güntürk, M. Lammers, A. M. Powell, R. Saab, Ö Yilmaz

Research output: Contribution to journalArticlepeer-review


Quantization of compressed sensing measurements is typically justified by the robust recovery results of Candès, Romberg and Tao, and of Donoho. These results guarantee that if a uniform quantizer of step size δ is used to quantize m measurements y=Φx of a k-sparse signal x ∈ ℝN, where Φ satisfies the restricted isometry property, then the approximate recovery x# via ℓ1-minimization is within O(δ) of x. The simplest and commonly assumed approach is to quantize each measurement independently. In this paper, we show that if instead an rth-order ΣΔ (Sigma-Delta) quantization scheme with the same output alphabet is used to quantize y, then there is an alternative recovery method via Sobolev dual frames which guarantees a reduced approximation error that is of the order δ(k/m)(r-1/2)α for any 0 < α < 1, if m≳r,αk(log N)1/(1-α). The result holds with high probability on the initial draw of the measurement matrix Φ from the Gaussian distribution, and uniformly for all k-sparse signals x whose magnitudes are suitably bounded away from zero on their support.

Original languageEnglish (US)
Pages (from-to)1-36
Number of pages36
JournalFoundations of Computational Mathematics
Issue number1
StatePublished - Feb 2013


  • Alternative duals
  • Compressed sensing
  • Finite frames
  • Quantization
  • Random frames

ASJC Scopus subject areas

  • Analysis
  • Computational Mathematics
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Sobolev Duals for Random Frames and ΣΔ Quantization of Compressed Sensing Measurements'. Together they form a unique fingerprint.

Cite this