Abstract
The field of quantized compressed sensing investigates how to jointly design a measurement matrix, quantizer, and reconstruction algorithm in order to accurately reconstruct low-complexity signals from a minimal number of measurements that are quantized to a finite number of bits. In this short survey, we give an overview of the state-of-the-art rigorous reconstruction results that have been obtained for three popular quantization models: one-bit quantization, uniform scalar quantization, and noise-sha** methods.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
A. Ai, A. Lapanowski, Y. Plan, R. Vershynin, One-bit compressed sensing with non-Gaussian measurements. Linear Algebr. Appl. 441, 222–239 (2014)
U. Ayaz, S. Dirksen, H. Rauhut, Uniform recovery of fusion frame structured sparse signals. Appl. Comput. Harmon. Anal. 41(2), 341–361 (2016)
R. Baraniuk, S. Foucart, D. Needell, Y. Plan, M. Wootters, One-bit compressive sensing of dictionary-sparse signals. Inf. Inference: A J. IMA 7(1), 83–104 (2017)
R.G. Baraniuk, S. Foucart, D. Needell, Y. Plan, M. Wootters, Exponential decay of reconstruction error from binary measurements of sparse signals. IEEE Trans. Inf. Theory 63(6), 3368–3385 (2017)
P.T. Boufounos, R.G. Baraniuk, 1-bit compressive sensing, in 2008 42nd Annual Conference on Information Sciences and Systems (IEEE 2008), pp. 16–21
P. T. Boufounos, L. Jacques, F. Krahmer, R. Saab, Quantization and compressive sensing, in Compressed Sensing and its Applications (Springer, 2015), pp. 193–237
J. Bourgain, An improved estimate in the restricted isometry problem, in Geometric Aspects of Functional Analysis, ed. B. Klartag, E. Milman, volume 2116 of Lecture Notes in Mathematics (Springer International Publishing, 2014), pp. 65–70
E.J. Candès, J., T. Tao, J.K. Romberg, Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inform. Theory 52(2), 489–509 (2006)
E.J. Candès, J.K. Romberg, T. Tao, Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math. 59(8), 1207–1223 (2006)
E. Chou, Beta-duals of frames and applications to problems in quantization. PhD thesis, New York University (2013)
E. Chou, C.S. Güntürk, Distributed noise-sha** quantization: I. Beta duals of finite frames and near-optimal quantization of random measurements. Constr. Approx. 44(1), 1–22 (2016)
E. Chou, C. S. Güntürk, Distributed noise-sha** quantization: II. Classical frames, in Excursions in Harmonic Analysis, Volume 5 (Springer, 2017), pp. 179–198
E. Chou, C. S. Güntürk, F. Krahmer, R. Saab, Ö. Yılmaz, Noise-sha** quantization methods for frame-based and compressive sampling systems, in Sampling Theory, a Renaissance (Springer, 2015), pp. 157–184
I. Daubechies, R. DeVore, Approximating a bandlimited function using very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order. Ann. Math. 158(2), 679–710 (2003)
M.A. Davenport, J. Romberg, An overview of low-rank matrix recovery from incomplete observations. IEEE J. Sel. Top. Signal Process. 10(4), 608–622 (2016)
P. Deift, F. Krahmer, C.S. Güntürk, An optimal family of exponentially accurate one-bit sigma-delta quantization schemes. Commun. Pure Appl. Math. 64(7), 883–919 (2011)
S. Dirksen, Dimensionality reduction with subgaussian matrices: a unified theory. Found. Comput. Math. 16(5), 1367–1396 (2016)
S. Dirksen, H.C. Jung, H. Rauhut, One-bit compressed sensing with Gaussian circulant matrices. ar**v:1710.03287 (2017)
S. Dirksen, G. Lecué, H. Rauhut, On the gap between restricted isometry properties and sparse recovery conditions. IEEE Trans. Inform. Theory 64(8), 5478–5487 (2018)
S. Dirksen, S. Mendelson, Non-gaussian hyperplane tessellations and robust one-bit compressed sensing. ar**v:1805.09409
S. Dirksen, S. Mendelson, Robust one-bit compressed sensing with partial circulant matrices. ar**v:1812.06719
S. Dirksen, S. Mendelson. Unpublished manuscript
D.L. Donoho, Compressed sensing. IEEE Trans. Inform. Theory 52(4), 1289–1306 (2006)
A. Eftekhari, M.B. Wakin, New analysis of manifold embeddings and signal recovery from compressive measurements. Appl. Comput. Harmon. Anal. 39(1), 67–109 (2015)
J.-M. Feng, F. Krahmer, An RIP-based approach to \(\varSigma \varDelta \) quantization for compressed sensing. IEEE Signal Process. Lett. 21(11), 1351–1355 (2014)
J.-M. Feng, F. Krahmer, R. Saab, Quantized compressed sensing for partial random circulant matrices. ar**v:1702.04711 (2017)
S. Foucart, Flavors of Compressive Sensing (Springer International Publishing, Cham, 2017), pp. 61–104
S. Foucart, R. Lynch, Recovering low-rank matrices from binary measurements. Preprint (2018)
S. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing (Applied and Numerical Harmonic Analysis. Birkhäuser/Springer, New York, 2013)
V.K. Goyal, M. Vetterli, N.T. Thao, Quantized overcomplete expansions in \(\mathbb{R}^N\) analysis, synthesis, and algorithms. IEEE Trans. Inform. Theory 44(1), 16–31 (1998)
R.M. Gray, D.L. Neuhoff, Quantization. IEEE Trans. Inf. Theory 44(6), 2325–2383 (1998)
R.M. Gray, T.G. Stockham, Dithered quantizers. IEEE Trans. Inf. Theory 39(3), 805–812 (1993)
C.S. Güntürk, One-bit sigma-delta quantization with exponential accuracy. Commun. Pure Appl. Math. 56(11), 1608–1630 (2003)
C.S. Güntürk, M. Lammers, A.M. Powell, R. Saab, Ö. Yılmaz, Sobolev duals for random frames and \(\varSigma \varDelta \) quantization of compressed sensing measurements. Found. Comput. Math. 13(1), 1–36 (2013)
I. Haviv, O. Regev, The restricted isometry property of subsampled Fourier matrices, in SODA ’16 (Philadelphia, PA, USA, 2016), pp. 288–297
T. Huynh, R. Saab, Fast binary embeddings, and quantized compressed sensing with structured matrices. ar**v:1801.08639 (2018)
L. Jacques, A quantized Johnson-Lindenstrauss lemma: the finding of Buffon’s needle. IEEE Trans. Inf. Theory 61(9), 5012–5027 (2015)
L. Jacques, Error decay of (almost) consistent signal estimations from quantized gaussian random projections. IEEE Trans. Inf. Theory 62(8), 4696–4709 (2016)
L. Jacques, Small width, low distortions: quantized random embeddings of low-complexity sets. IEEE Trans. Inf. Theory 63(9), 5477–5495 (2017)
L. Jacques, V. Cambareri, Time for dithering: fast and quantized random embeddings via the restricted isometry property. Inf. Inference: A J. IMA 6(4), 441–476 (2017)
L. Jacques, K. Degraux, C. De Vleeschouwer, Quantized iterative hard thresholding: Bridging 1-bit and high-resolution quantized compressed sensing. ar**v:1305.1786 (2013)
L. Jacques, J.N. Laska, P.T. Boufounos, R.G. Baraniuk, Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors. IEEE Trans. Inform. Theory 59(4), 2082–2102 (2013)
K. Knudson, R. Saab, R. Ward, One-bit compressive sensing with norm estimation. IEEE Trans. Inform. Theory 62(5), 2748–2758 (2016)
F. Krahmer, S. Mendelson, H. Rauhut, Suprema of chaos processes and the restricted isometry property. Comm. Pure Appl. Math. 67(11), 1877–1904 (2014)
F. Krahmer, R. Saab, Ö. Yilmaz, Sigma-delta quantization of sub-gaussian frame expansions and its application to compressed sensing. Inf. Inference 3(1), 40–58 (2014)
J.N. Laska, P.T. Boufounos, M.A. Davenport, R.G. Baraniuk, Democracy in action: quantization, saturation, and compressive sensing. Appl. Comput. Harmonic Anal. 31(3), 429–443 (2011)
M. Lustig, D.L. Donoho, J.M. Santos, J.M. Pauly, Compressed sensing MRI. IEEE Signal Process. Mag. 25(2), 72–82 (2008)
S. Mendelson, Learning without concentration. J. ACM 62(3), Art. 21, 25 (2015)
S. Mendelson, H. Rauhut, R. Ward, Improved bounds for sparse recovery from subsampled random convolutions. Ann. Appl. Probab. 28(6), 3491–3527 (2018)
A. Montanari, N. Sun, Spectral algorithms for tensor completion. Comm. Pure Appl. Math. 71(11), 2381–2425 (2018)
A. Moshtaghpour, L. Jacques, V. Cambareri, K. Degraux, C. De Vleeschouwer, Consistent basis pursuit for signal and matrix estimates in quantized compressed sensing. IEEE Signal Process. Lett. 23(1), 25–29 (2016)
S. Oymak, B. Recht, Near-optimal bounds for binary embeddings of arbitrary sets. ar**v:1512.04433 (2015)
Y. Plan, R. Vershynin, One-bit compressed sensing by linear programming. Comm. Pure Appl. Math. 66(8), 1275–1297 (2013)
Y. Plan, R. Vershynin, Robust 1-bit compressed sensing and sparse logistic regression: a convex programming approach. IEEE Trans. Inform. Theory 59(1), 482–494 (2013)
Y. Plan, R. Vershynin, Dimension reduction by random hyperplane tessellations. Discrete Comput. Geom. 51(2), 438–461 (2014)
H. Rauhut, R. Schneider, Z. Stojanac, Low rank tensor recovery via iterative hard thresholding. Linear Algebra Appl. 523, 220–262 (2017)
L. Roberts, Picture coding using pseudo-random noise. IRE Trans. Inf. Theory 8(2), 145–154 (1962)
J. Romberg, Compressive sensing by random convolution. SIAM J. Imaging Sci. 2(4), 1098–1128 (2009)
M. Rudelson, R. Vershynin, On sparse reconstruction from Fourier and Gaussian measurements. Comm. Pure Appl. Math. 61(8), 1025–1045 (2008)
R. Saab, R. Wang, Ö. Yılmaz, Quantization of compressive samples with stable and robust recovery. Appl. Comput. Harmonic Anal. 44(1), 123–143 (2018)
G. Schechtman, Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. 200(1), 125–135 (2006)
R. Vershynin, High-Dimensional Probability (Cambridge University Press, 2018)
C. Xu, L. Jacques, Quantized compressive sensing with RIP matrices: the benefit of dithering. ar**v:1801.05870 (2018)
Acknowledgements
It is a pleasure to thank the anonymous reviewer, Rayan Saab, and especially Laurent Jacques for many comments that improved this book chapter. This work was supported by the DFG through the project Quantized Compressive Spectrum Sensing (QuaCoSS), which is part of the Priority Program SPP 1798 Compressive Sensing in Information Processing (COSIP).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this chapter
Cite this chapter
Dirksen, S. (2019). Quantized Compressed Sensing: A Survey. In: Boche, H., Caire, G., Calderbank, R., Kutyniok, G., Mathar, R., Petersen, P. (eds) Compressed Sensing and Its Applications. Applied and Numerical Harmonic Analysis. Birkhäuser, Cham. https://doi.org/10.1007/978-3-319-73074-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-73074-5_2
Published:
Publisher Name: Birkhäuser, Cham
Print ISBN: 978-3-319-73073-8
Online ISBN: 978-3-319-73074-5
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)