Sobolev Duals for Random Frames and Sigma-Delta Quantization of Compressed Sensing Measurements
Authors:
Preprint
Abstract
Quantization of compressed sensing measurements is typically justified by the robust recovery results of Cand\`es, Romberg and Tao, and of Donoho. These results guarantee that if a uniform quantizer of step size $\delta$ is used to quantize $m$ measurements $y = \Phi x$ of a $k$-sparse signal $x \in \R^N$, where $\Phi$ satisfies the restricted isometry property, then the approximate recovery $x^#$ via $\ell_1$-minimization is within $O(\delta)$ of $x$. The simplest and commonly assumed approach is to quantize each measurement independently. In this paper, we show that if instead an $r$th 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 reduction of the approximation error by a factor of $(m/k)^{(r-1/2)\alpha}$ for any $0 < \alpha < 1$, if $m \gtrsim_r k (\log N)^{1/(1-\alpha)}$. The result holds with high probability on the initial draw of the measurement matrix $\Phi$ from the Gaussian distribution, and uniformly for all $k$-sparse signals $x$ that satisfy a mild size condition on their supports.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Democracy in action: Quantization, saturation, and compressive sensingApplied and Computational Harmonic Analysis, 2011
- Sobolev Duals in Frame Theory and Sigma-Delta QuantizationJournal of Fourier Analysis and Applications, 2009
- Smallest singular value of a random rectangular matrixCommunications on Pure and Applied Mathematics, 2009
- Compressed sensing and best 𝑘-term approximationJournal of the American Mathematical Society, 2008
- Alternative dual frames for digital-to-analog conversion in sigma–delta quantizationAdvances in Computational Mathematics, 2008
- A Simple Proof of the Restricted Isometry Property for Random MatricesConstructive Approximation, 2008
- Smooth Frame-Path Termination for Higher Order Sigma-Delta QuantizationJournal of Fourier Analysis and Applications, 2007
- Stable signal recovery from incomplete and inaccurate measurementsCommunications on Pure and Applied Mathematics, 2006
- Quantized overcomplete expansions in IR/sup N/: analysis, synthesis, and algorithmsIEEE Transactions on Information Theory, 1998
- On the distribution of the singular values of Toeplitz matricesLinear Algebra and its Applications, 1986