## Abstract

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 language | English (US) |
---|---|

Pages (from-to) | 1-36 |

Number of pages | 36 |

Journal | Foundations of Computational Mathematics |

Volume | 13 |

Issue number | 1 |

DOIs | |

State | Published - 2013 |

## Keywords

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

## ASJC Scopus subject areas

- Analysis
- Computational Mathematics
- Computational Theory and Mathematics
- Applied Mathematics