2014

Quantization and Compressive Sensing

Boufounos, Petros T., Jacques, Laurent, Krahmer, Felix et al.

Understand

Quantization is an essential step in digitizing signals, and, therefore, an indispensable component of any modern acquisition system.

This book chapter explores the interaction of quantization and compressive sensing and examines practical quantization strategies for compressive acquisition systems.
Specifically, we first provide a brief overview of quantization and examine fundamental performance bounds applicable to any quantization approach.
Next, we consider several forms of scalar quantizers, namely uniform, non-uniform, and 1-bit.

Built on

Quantization distortion in pulse-count modulation with nonuniform spacing of levels
P. F. Panter and W. Dite · 1951
Earlier work this paper cites.
Quantizing for minimum distortion
J. Max · 1960
Earlier work this paper cites.
A telemetering system by code modulation – Δ − Σ \Delta-\Sigma modulation
H. Inose, Y. Yasuda, and J. Murakami · 1962
Earlier work this paper cites.
Probability inequalities for sums of bounded random variables
W. Hoeffding · 1963
Earlier work this paper cites.
A unity bit coding method by negative feedback
H. Inose and Y. Yasuda · 1963
Earlier work this paper cites.
A bound on tail probabilities for quadratic forms in independent random variables
D. L. Hanson and F. T. Wright · 1971
Earlier work this paper cites.
Least squares quantization in PCM
S. Lloyd · 1982
Earlier work this paper cites.
Extensions of lipschitz mappings into a hilbert space
W. B. Johnson and J. Lindenstrauss · 1984
Earlier work this paper cites.
Entropy numbers of diagonal operators between symmetric Banach spaces
C. Schütt · 1984
Earlier work this paper cites.
Oversampled sigma-delta modulation
R.M. Gray · 1987
Earlier work this paper cites.
Parametric generalized Gaussian density estimation
M. K. Varanasi and B. Aazhang · 1989
Earlier work this paper cites.
Reduction of the MSE in R-times oversampled A/D conversion O ⁡ ( 1 / R ) O(1/R) to O ⁡ ( 1 / R 2 ) O(1/R^{2})
N.T. Thao and M. Vetterli · 1994
Earlier work this paper cites.
Function spaces, entropy numbers, differential operators
D. E. Edmunds and H. Triebel · 1996
Earlier work this paper cites.
Delta-Sigma data converters: theory, design, and simulation
S. R. Norsworthy, R. Schreier, G. C. Temes, et al · 1996
Earlier work this paper cites.
Lower bound on the mean-squared error in oversampled quantization of periodic signals using vector quantization analysis
N. T. Thao and M. Vetterli · 1996
Earlier work this paper cites.
Atomic Decomposition by Basis Pursuit
S. S. Chen, D. L. Donoho, and M. A. Saunders · 1998
Earlier work this paper cites.
Quantized overcomplete expansions in ℝ N \mathbb{R}^{N} : Analysis, synthesis, and algorithms
V. K Goyal, M. Vetterli, and N. T. Thao · 1998
Earlier work this paper cites.
Quantization
R. M. Gray and D. L. Neuhoff · 1998
Earlier work this paper cites.
Harmonic analysis of two problems in signal compression
S. Güntürk · 2000
Earlier work this paper cites.
A lower estimate for entropy numbers
T. Kühn · 2001
Earlier work this paper cites.
The pros and cons of democracy
A. Calderbank and I. Daubechies · 2002
Earlier work this paper cites.
Approximating a bandlimited function using very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order
I. Daubechies and R. DeVore · 2003
Earlier work this paper cites.
One-bit sigma-delta quantization with exponential accuracy
C. S. Güntürk · 2003
Earlier work this paper cites.
The concentration of measure phenomenon
M. Ledoux · 2005
Earlier work this paper cites.
Second-order Sigma–Delta ( Σ \Sigma Δ \Delta ) quantization of finite frame expansions
J. J. Benedetto, A. M. Powell, and Ö. Yılmaz · 2006
Earlier work this paper cites.
Sigma-Delta ( Σ \Sigma Δ \Delta ) quantization and finite frames
J. J. Benedetto, A. M. Powell, and Ö. Yılmaz · 2006
Earlier work this paper cites.
Quantization and Erasures in Frame Representations
P. T. Boufounos · 2006
Earlier work this paper cites.
Quantization noise shaping on arbitrary frame expansions
P. T. Boufounos and A. V. Oppenheim · 2006
Earlier work this paper cites.
Encoding the ℓ p \ell_{p} ball from limited measurements
E. Candès and J. Romberg · 2006
Earlier work this paper cites.
Stable signal recovery from incomplete and inaccurate measurements
E. Candès, J. Romberg, and T. Tao · 2006
Earlier work this paper cites.
Nonadaptive lossy encoding of sparse signals
R. J. Pai · 2006
Earlier work this paper cites.

Similar

Frame paths and error bounds for Sigma–Delta quantization
B. G. Bodmann and V. I. Paulsen · 2007
Cited alongside, same era.
Smooth frame-path termination for higher order Sigma-Delta quantization
B. G. Bodmann, V. I. Paulsen, and S. A. Abdulbaki · 2007
Cited alongside, same era.
Quantization of sparse representations
P. T. Boufounos and R. G. Baraniuk · 2007
Cited alongside, same era.
Sparse MRI: The application of compressed sensing for rapid MRI imaging
M. Lustig, D. Donoho, and J.M. Pauly · 2007
Cited alongside, same era.
Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions
A. Andoni and P. Indyk · 2008
Cited alongside, same era.
A simple proof of the restricted isometry property for random matrices
R. Baraniuk, M. Davenport, R. DeVore, and M. Wakin · 2008
Cited alongside, same era.
Combining geometry and combinatorics: a unified approach to sparse signal recovery
R. Berinde, A. C. Gilbert, P. Indyk, H. Karloff, and M. J. Strauss · 2008
Cited alongside, same era.
Sparse sampling of signal innovations
T. Blu, P-L Dragotti, M. Vetterli, P. Marziliano, and L. Coulot · 2008
Cited alongside, same era.
1-bit compressive sensing
P. T. Boufounos and R. G. Baraniuk · 2008
Cited alongside, same era.
The restricted isometry property and its implications for compressed sensing
E. J. Candès · 2008
Cited alongside, same era.
Restricted isometry properties and nonconvex compressive sensing
R. Chartrand and V. Staneva · 2008
Cited alongside, same era.
Compressive coded aperture superresolution image reconstruction
R. F. Marcia and R. M. Willett · 2008
Cited alongside, same era.

Then

Sub-Nyquist sampling
M. Mishali and Y. C. Eldar · 2011
Later among the works it cites.
Universal rate-efficient scalar quantization
P. T. Boufounos · 2012
Later among the works it cites.
The pros and cons of compressive sensing for wideband signal acquisition: Noise folding versus dynamic range
M. A. Davenport, J. N. Laska, J. Treichler, and R. G. Baraniuk · 2012
Later among the works it cites.
Message-passing de-quantization with applications to compressed sensing
U.S. Kamilov, V.K. Goyal, and S. Rangan · 2012
Later among the works it cites.
Root-exponential accuracy for coarse quantization of finite frame expansions
F. Krahmer, R. Saab, and R. Ward · 2012
Later among the works it cites.
Lower bounds for the error decay incurred by coarse quantization schemes
F. Krahmer and R. Ward · 2012
Later among the works it cites.
Regime change: Bit-depth versus measurement-rate in compressive sensing
J. N. Laska and R. G. Baraniuk · 2012
Later among the works it cites.
Quantized embeddings of scale-invariant image features for mobile augmented reality
M. Li, S. Rane, and P. T. Boufounos · 2012
Later among the works it cites.
Robust 1-bit compressive sensing via Gradient Support Pursuit
Original
S. Bahmani, P. T. Boufounos, and B. Raj · 2013
Later among the works it cites.
Efficient coding of signal distances using universal quantized embeddings
P. T. Boufounos and S. Rane · 2013
Later among the works it cites.
Non-convex decoding for sigma delta quantized compressed sensing
E. Chou · 2013
Later among the works it cites.
Sobolev duals for random frames and Σ \Sigma Δ \Delta quantization of compressed sensing measurements
C. S. Güntürk, M. Lammers, A. M. Powell, R. Saab, and Ö. Yılmaz · 2013
Later among the works it cites.
Near-optimal encoding for sigma-delta quantization of finite frame expansions
M. Iwen and R. Saab · 2013
Later among the works it cites.
A quantized Johnson Lindenstrauss lemma: The finding of buffon’s needle
Original
L. Jacques · 2013
Later among the works it cites.
Quantized iterative hard thresholding: Bridging 1-bit and high-resolution quantized compressed sensing
Original
L. Jacques, K. Degraux, and C. De Vleeschouwer · 2013
Later among the works it cites.
Stabilizing nonuniformly quantized compressed sensing with scalar companders
L. Jacques, D. K. Hammond, and M. J. Fadili · 2013
Later among the works it cites.
Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors
L. Jacques, J. N. Laska, P. T. Boufounos, and R. G. Baraniuk · 2013
Later among the works it cites.
One-bit compressed sensing by linear programming
Y. Plan and R. Vershynin · 2013
Later among the works it cites.
Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach
Y. Plan and R. Vershynin · 2013
Later among the works it cites.
Quantization and finite frames
A. M. Powell, R. Saab, and Ö. Yılmaz · 2013
Later among the works it cites.
Error bounds for consistent reconstruction: Random polytopes and coverage processes
Original
A. M. Powell and J. T. Whitehouse · 2013
Later among the works it cites.
Quantized embeddings: An efficient and universal nearest neighbor method for cloud-based image retrieval
S. Rane, P. T. Boufounos, and A. Vetro · 2013
Later among the works it cites.
Hanson-wright inequality and sub-gaussian concentration
M. Rudelson and R. Vershynin · 2013
Later among the works it cites.
One-bit compressed sensing with non-gaussian measurements
A. Ai, A. Lapanowski, Y. Plan, and R. Vershynin · 2014
Closest in time.
Exponential decay of reconstruction error from binary measurements of sparse signals
Original
R. Baraniuk, S. Foucart, D. Needell, Y. Plan, and M. Wootters · 2014
Closest in time.
Sparse representation of a polytope and recovery of sparse signals and low-rank matrices
T. T. Cai and A. Zhang · 2014
Closest in time.
An RIP approach to Sigma-Delta quantization for compressed sensing
J. Feng and F. Krahmer · 2014
Closest in time.
Error decay of (almost) consistent signal estimations from quantized random gaussian projections
Original
L. Jacques · 2014
Closest in time.
Suprema of chaos processes and the restricted isometry property
F. Krahmer, S. Mendelson, and H. Rauhut · 2014
Closest in time.
Sigma-delta quantization of sub-gaussian frame expansions and its application to compressed sensing
F. Krahmer, R. Saab, and Ö. Yilmaz · 2014
Closest in time.
Dimension reduction by random hyperplane tessellations
Y. Plan and R. Vershynin · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…