×

Quantization and compressive sensing. (English) Zbl 1333.94016

Boche, Holger (ed.) et al., Compressed sensing and its applications. MATHEON workshop, Berlin, Germany, December 2013. Cham: Birkhäuser/Springer (ISBN 978-3-319-16041-2/hbk; 978-3-319-16042-9/ebook). Applied and Numerical Harmonic Analysis, 193-237 (2015).
Summary: Quantization is an essential step in digitizing signals, and, therefore, an indispensable component of any modern acquisition system. This 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. We provide performance bounds and fundamental analysis, as well as practical quantizer designs and reconstruction algorithms that account for quantization. Furthermore, we provide an overview of Sigma-Delta \((\Sigma\Delta)\) quantization in the compressed sensing context, and also discuss implementation issues, recovery algorithms, and performance bounds. As we demonstrate, proper accounting for quantization and careful quantizer design has significant impact in the performance of a compressive acquisition system.
For the entire collection see [Zbl 1320.94007].

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Software:

PDCO; UNLocBoX

References:

[1] Ai, A.; Lapanowski, A.; Plan, Y.; Vershynin, R., One-bit compressed sensing with non-gaussian measurements, Linear Algebra Appl., 441, 222-239 (2014) · Zbl 1332.94041 · doi:10.1016/j.laa.2013.04.002
[2] Andoni, A.; Indyk, P., Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions, Commun. ACM, 51, 1, 117-122 (2008) · doi:10.1145/1327452.1327494
[3] Bahmani, S., Boufounos, P.T., Raj, B.: Robust 1-bit compressive sensing via Gradient Support Pursuit. arXiv preprint arXiv:1304.6627 (2013)
[4] Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constr. Approx., 28, 3, 253-263 (2008) · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x
[5] Baraniuk, R., Foucart, S., Needell, D., Plan, Y., Wootters, M.: Exponential decay of reconstruction error from binary measurements of sparse signals. arXiv preprint arXiv:1407.8246 (2014) · Zbl 1446.94017
[6] Benedetto, J. J.; Powell, A. M.; Yılmaz, Ö., Second-order Sigma-Delta (Σ Δ) quantization of finite frame expansions, Appl. Comput. Harmon. Anal., 20, 1, 126-148 (2006) · Zbl 1088.42018 · doi:10.1016/j.acha.2005.04.003
[7] Benedetto, J. J.; Powell, A. M.; Yılmaz, Ö., Sigma-Delta (Σ Δ) quantization and finite frames, IEEE Trans. Inform. Theory, 52, 5, 1990-2005 (2006) · Zbl 1285.94014 · doi:10.1109/TIT.2006.872849
[8] Berinde, R., Gilbert, A.C., Indyk, P., Karloff, H., Strauss, M.J.: Combining geometry and combinatorics: a unified approach to sparse signal recovery. In: Proceedings 46th Annual Allerton Conference Communication Control Computing, pp. 798-805. IEEE, New York (2008)
[9] Blu, T.; Dragotti, P.-L.; Vetterli, M.; Marziliano, P.; Coulot, L., Sparse sampling of signal innovations, IEEE Signal Process. Mag., 25, 2, 31-40 (2008) · doi:10.1109/MSP.2007.914998
[10] Blum, J.; Lammers, M.; Powell, A. M.; Yılmaz, Ö., Sobolev duals in frame theory and Sigma-Delta quantization, J. Fourier Anal. Appl., 16, 3, 365-381 (2010) · Zbl 1200.42019 · doi:10.1007/s00041-009-9105-x
[11] Blumensath, T.; Davies, M., Iterative hard thresholding for compressive sensing, Appl. Comput. Harmon. Anal., 27, 3, 265-274 (2009) · Zbl 1174.94008 · doi:10.1016/j.acha.2009.04.002
[12] Bodmann, B. G.; Paulsen, V. I., Frame paths and error bounds for Sigma-Delta quantization, Appl. Comput. Harmon. Anal., 22, 2, 176-197 (2007) · Zbl 1133.94013 · doi:10.1016/j.acha.2006.05.010
[13] Bodmann, B. G.; Paulsen, V. I.; Abdulbaki, S. A., Smooth frame-path termination for higher order Sigma-Delta quantization, J. Fourier Anal. Appl., 13, 3, 285-307 (2007) · Zbl 1130.46011 · doi:10.1007/s00041-006-6032-y
[14] Boufounos, P. T., Quantization and Erasures in Frame Representations (2006), Thesis, MIT EECS, Cambridge, MA: D.Sc, Thesis, MIT EECS, Cambridge, MA
[15] Boufounos, P.T.: Greedy sparse signal reconstruction from sign measurements. In:Proceeding of Asilomar Conference on Signals Systems and Computing. Asilomar, California (2009)
[16] Boufounos, P.T.: Hierarchical distributed scalar quantization. In: Proceedings of International Conference Sampling Theory and Applications (SampTA), pp. 2-6. Singapore (2011)
[17] Boufounos, P. T., Universal rate-efficient scalar quantization, IEEE Trans. Inform. Theory, 58, 3, 1861-1872 (2012) · Zbl 1365.94065 · doi:10.1109/TIT.2011.2173899
[18] Boufounos, P.T., Baraniuk, R.G.: Quantization of sparse representations. In: Rice University ECE Department Technical Report 0701. Summary appears in Proceeding Data Compression Conference (DCC), pp. 27-29. Snowbird, UT (2007)
[19] Boufounos P.T., Baraniuk, R.G.: 1-bit compressive sensing. In: Proceedings of Conference Informatin Science and Systems (CISS), pp. 19-21. IEEE Princeton, NJ (2008)
[20] Boufounos, P.T., Oppenheim, A.V.: Quantization noise shaping on arbitrary frame expansions. IEEE EURASIP J. Adv. Signal Process. Article ID:053807 (2006) · Zbl 1122.94306
[21] Boufounos, P.T., Rane, S.: Efficient coding of signal distances using universal quantized embeddings. In: Proceedings Data Compression Conference (DCC), pp. 20-22. IEEE, Snowbird, UT (2013)
[22] Cai, T. T.; Zhang, A., Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inform. Theory, 60, 1, 122-132 (2014) · Zbl 1364.94114 · doi:10.1109/TIT.2013.2288639
[23] Calderbank, A.; Daubechies, I., The pros and cons of democracy, IEEE Trans. Inform. Theory, 48, 6, 1721-1725 (2002) · Zbl 1061.94014 · doi:10.1109/TIT.2002.1003852
[24] Candès, E., Romberg, J.: Encoding the ℓ_p ball from limited measurements. In: Proceeding Data Compression Conference (DCC), pp. 28-30. IEEE, Snowbird, UT (2006)
[25] Candès, E.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Commun. Pure Appl. Math., 59, 8, 1207-1223 (2006) · Zbl 1098.94009 · doi:10.1002/cpa.20124
[26] Candès, E. J., The restricted isometry property and its implications for compressed sensing. C. R. Acad. Sci., Ser, I, 346, 589-592 (2008) · Zbl 1153.94002
[27] Chartrand, R.; Staneva, V., Restricted isometry properties and nonconvex compressive sensing, Inverse Prob., 24, 3, 1-14 (2008) · Zbl 1143.94004 · doi:10.1088/0266-5611/24/3/035020
[28] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic Decomposition by Basis Pursuit, SIAM J. Sci. Comput., 20, 1, 33-61 (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[29] Chou, E.: Non-convex decoding for sigma delta quantized compressed sensing. In: Proceeding International Conference Sampling Theory and Applications (SampTA 2013), pp. 101-104. Bremen, Germany (2013)
[30] Combettes, P.L., Pesquet, J.-C.: Proximal splitting methods in signal processing. Fixed-Point Algorithms for Inverse Problems in Science and Engineering, pp. 185-212. Springer, New York (2011) · Zbl 1242.90160
[31] Dai, W., Pham, H.V., Milenkovic, O.: Distortion-Rate Functions for Quantized Compressive Sensing. Technical Report arXiv:0901.0749 (2009)
[32] Daubechies, I., DeVore, R.: Approximating a bandlimited function using very coarsely quantized data: A family of stable sigma-delta modulators of arbitrary order. Ann. Math. 679-710 (2003) · Zbl 1058.94004
[33] Davenport, M.A., Laska, J.N., Boufounos, P.T., Baraniuk, R.G.: A simple proof that random matrices are democratic. Technical report, Rice University ECE Department Technical Report TREE-0906, Houston, TX (2009)
[34] Davenport, M. A.; Laska, J. N.; Treichler, J.; Baraniuk, R. G., The pros and cons of compressive sensing for wideband signal acquisition: Noise folding versus dynamic range, IEEE Trans. Signal Process., 60, 9, 4628-4642 (2012) · Zbl 1393.94678 · doi:10.1109/TSP.2012.2201149
[35] Deift, P.; Güntürk, C. S.; Krahmer, F., An optimal family of exponentially accurate one-bit sigma-delta quantization schemes, Commun. Pure Appl. Math., 64, 7, 883-919 (2011) · Zbl 1248.94035 · doi:10.1002/cpa.20367
[36] Edmunds, D. E.; Triebel, H., Function Spaces, Entropy Numbers (1996), Differential Operators: Cambridge University Press, Cambridge, Differential Operators · Zbl 0865.46020 · doi:10.1017/CBO9780511662201
[37] Feng, J.; Krahmer, F., An RIP approach to Sigma-Delta quantization for compressed sensing, IEEE Signal Process. Lett., 21, 11, 1351-1355 (2014) · doi:10.1109/LSP.2014.2336700
[38] Goyal, V. K.; Vetterli, M.; Thao, N. T., Quantized overcomplete expansions in \(\mathbb{R}^N \) : Analysis, synthesis, and algorithms, IEEE Trans. Inform. Theory, 44, 1, 16-31 (1998) · Zbl 0905.94007 · doi:10.1109/18.650985
[39] Gray, R. M.; Neuhoff, D. L., Quantization, IEEE Trans. Inform. Theory, 44, 6, 2325-2383 (1998) · Zbl 1016.94016 · doi:10.1109/18.720541
[40] Gray, R. M., Oversampled sigma-delta modulation, IEEE Trans. Comm., 35, 5, 481-489 (1987) · Zbl 0641.94005 · doi:10.1109/TCOM.1987.1096814
[41] Güntürk, C. S., One-bit sigma-delta quantization with exponential accuracy, Commun. Pure Appl. Math., 56, 11, 1608-1630 (2003) · Zbl 1029.94006 · doi:10.1002/cpa.3044
[42] Güntürk, C. S.; Lammers, M.; Powell, A. M.; Saab, R.; Yılmaz, Ö., Sobolev duals for random frames and Σ Δ quantization of compressed sensing measurements, Found. Comput. Math., 13, 1, 1-36 (2013) · Zbl 1273.41020 · doi:10.1007/s10208-012-9140-x
[43] Güntürk, S.: Harmonic analysis of two problems in signal compression. PhD thesis, Program in Applied and Computation Mathematics, Princeton University, Princeton, NJ (2000)
[44] Hanson, D. L.; Wright, F. T., A bound on tail probabilities for quadratic forms in independent random variables, Ann. Math. Stat., 42, 3, 1079-1083 (1971) · Zbl 0216.22203 · doi:10.1214/aoms/1177693335
[45] Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Am. Stat. Assoc., 58, 301, 13-30 (1963) · Zbl 0127.10602 · doi:10.1080/01621459.1963.10500830
[46] Inose, H.; Yasuda, Y., A unity bit coding method by negative feedback, Proc. IEEE, 51, 11, 1524-1535 (1963) · doi:10.1109/PROC.1963.2622
[47] Inose, H.; Yasuda, Y.; Murakami, J., A telemetering system by code modulation - Δ −Σ modulation, IRE Trans. Space El. Tel., SET-8, 3, 204-209 (1962) · doi:10.1109/IRET-SET.1962.5008839
[48] Iwen, M.; Saab, R., Near-optimal encoding for sigma-delta quantization of finite frame expansions, J. Fourier Anal. Appl., 19, 6, 1255-1273 (2013) · Zbl 1304.42073 · doi:10.1007/s00041-013-9295-0
[49] Jacques, L.: A quantized Johnson Lindenstrauss lemma: The finding of buffon’s needle. arXiv preprint arXiv:1309.1507 (2013) · Zbl 1359.81065
[50] Jacques, L.: Error decay of (almost) consistent signal estimations from quantized random gaussian projections. arXiv preprint arXiv:1406.0022 (2014)
[51] Jacques, L., Degraux, K., De Vleeschouwer, C.: Quantized iterative hard thresholding: Bridging 1-bit and high-resolution quantized compressed sensing. In: Proceedings of International Conference Sampling Theory and Applications (SampTA 2013), arXiv:1305.1786, pp. 105-108. Bremen, Germany (2013)
[52] Jacques, L.; Hammond, D. K.; Fadili, M. J., Dequantizing compressed sensing: When oversampling and non-gaussian constraints combine, IEEE Trans. Inform. Theory, 57, 1, 559-571 (2011) · Zbl 1366.94106 · doi:10.1109/TIT.2010.2093310
[53] Jacques, L.; Hammond, D. K.; Fadili, M. J., Stabilizing nonuniformly quantized compressed sensing with scalar companders, IEEE Trans. Inform. Theory, 5, 12, 7969-7984 (2013) · Zbl 1364.94129 · doi:10.1109/TIT.2013.2281815
[54] Jacques, L.; Laska, J. N.; Boufounos, P. T.; Baraniuk, R. G., Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors, IEEE Trans. Inform. Theory, 59, 4, 2082-2102 (2013) · Zbl 1364.94130 · doi:10.1109/TIT.2012.2234823
[55] Johnson, W. B.; Lindenstrauss, J., Extensions of lipschitz mappings into a hilbert space, Contemp. Math., 26, 189-206, 1 (1984) · Zbl 0539.46017
[56] Kamilov, U., Goyal, V.K., Rangan, S.: Optimal quantization for compressive sensing under message passing reconstruction. In: Proceeding of IEEE International Symposium on Information Theory (ISIT), pp. 459-463 (2011)
[57] Kamilov, U. S.; Goyal, V. K.; Rangan, S., Message-passing de-quantization with applications to compressed sensing, IEEE Trans. Signal Process., 60, 12, 6270-6281 (2012) · Zbl 1393.94290 · doi:10.1109/TSP.2012.2217334
[58] Kostina, V., Duarte, M.F., Jafarpour, S., Calderbank, R.: The value of redundant measurement in compressed sensing. In: Proceeding of International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 3656-3659 (2011)
[59] Krahmer, F.; Mendelson, S.; Rauhut, H., Suprema of chaos processes and the restricted isometry property, Commun. Pure Appl. Math., 67, 11, 1877-1904 (2014) · Zbl 1310.94024 · doi:10.1002/cpa.21504
[60] Krahmer, F.; Saab, R.; Ward, R., Root-exponential accuracy for coarse quantization of finite frame expansions, IEEE Trans. Inform. Theory, 58, 2, 1069-1079 (2012) · Zbl 1365.94080 · doi:10.1109/TIT.2011.2168942
[61] Krahmer, F.; Saab, R.; Yilmaz, Ö., Sigma-delta quantization of sub-gaussian frame expansions and its application to compressed sensing, Inform. Inference, 3, 1, 40-58 (2014) · Zbl 1308.94034 · doi:10.1093/imaiai/iat007
[62] Krahmer, F.; Ward, R., New and improved johnson-lindenstrauss embeddings via the restricted isometry property, SIAM J. Math. Anal., 43, 3, 1269-1281 (2011) · Zbl 1247.15019 · doi:10.1137/100810447
[63] Krahmer, F.; Ward, R., Lower bounds for the error decay incurred by coarse quantization schemes, Appl. Comput. Harmonic Anal., 32, 1, 131-138 (2012) · Zbl 1236.94031 · doi:10.1016/j.acha.2011.06.003
[64] Kühn, T., A lower estimate for entropy numbers, J. Approx. Theory, 110, 1, 120-124 (2001) · Zbl 0995.47014 · doi:10.1006/jath.2000.3554
[65] Lammers, M.; Powell, A. M.; Yılmaz, Ö., Alternative dual frames for digital-to-analog conversion in sigma-delta quantization, Adv. Comput. Math., 32, 1, 73-102 (2010) · Zbl 1181.94050 · doi:10.1007/s10444-008-9088-1
[66] Laska, J.; Boufounos, P.; Davenport, M.; Baraniuk, R., Democracy in action: Quantization, saturation, and compressive sensing, Appl. Comput. Harmon. Anal., 31, 3, 429-443 (2011) · Zbl 1231.94045 · doi:10.1016/j.acha.2011.02.002
[67] Laska, J.; Wen, Z.; Yin, W.; Baraniuk, R., Trust, but verify: Fast and accurate signal recovery from 1-bit compressive measurements, IEEE Trans. Signal Process., 59, 11, 5289-5301 (2010) · Zbl 1393.94314 · doi:10.1109/TSP.2011.2162324
[68] Laska, J. N.; Baraniuk, R. G., Regime change: Bit-depth versus measurement-rate in compressive sensing, IEEE Trans. Signal Process., 60, 7, 3496-3505 (2012) · Zbl 1393.94690 · doi:10.1109/TSP.2012.2194710
[69] Ledoux, M., The Concentration of Measure Phenomenon (2005), Providence, RI: American Mathematical Society, Providence, RI · doi:10.1090/surv/089
[70] Li, M., Rane, S., Boufounos, P.T.: Quantized embeddings of scale-invariant image features for mobile augmented reality. In: Proceeding of IEEE Internatioal Workshop on Multimedia Signal Processing (MMSP), pp. 17-19. Banff, Canada (2012)
[71] Lloyd, S., Least squares quantization in PCM, IEEE Trans. Inform. Theory, 28, 2, 129-137 (1982) · Zbl 0504.94015 · doi:10.1109/TIT.1982.1056489
[72] Lustig, M.; Donoho, D.; Pauly, J. M., Sparse MRI: The application of compressed sensing for rapid MRI imaging, Magn. Reson. Med., 58, 6, 1182-1195 (2007) · doi:10.1002/mrm.21391
[73] Marcia, R.F., Willett, R.M.: Compressive coded aperture superresolution image reconstruction. In: Proceeding of International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 833-836. IEEE, New York (2008)
[74] Max, J., Quantizing for minimum distortion, IEEE Trans. Inform. Theory, 6, 1, 7-12 (1960) · doi:10.1109/TIT.1960.1057548
[75] Mishali, M.; Eldar, Y. C., Sub-Nyquist sampling, IEEE Signal Proc. Mag., 28, 6, 98-124 (2011) · doi:10.1109/MSP.2011.942308
[76] Nguyen, H. Q.; Goyal, V. K.; Varshney, L. R., Frame permutation quantization (2010), Anal: Appl. Comput. Harmon, Anal · doi:10.1109/CISS.2010.5464814
[77] Norsworthy, S. R.; Schreier, R.; Temes, G. C., Delta-Sigma Data Converters: Theory, Design, and Simulation (1996), New York: IEEE press, New York · doi:10.1109/9780470544358
[78] Pai, R. J., Nonadaptive lossy encoding of sparse signals (2006), MIT EECS, Cambridge, MA: M.eng. thesis, MIT EECS, Cambridge, MA
[79] Panter, P. F.; Dite, W., Quantization distortion in pulse-count modulation with nonuniform spacing of levels, Proc. IRE, 39, 1, 44-48 (1951) · doi:10.1109/JRPROC.1951.230419
[80] Plan, Y.; Vershynin, R., One-bit compressed sensing by linear programming, Commun. Pure Appl. Math., 66, 8, 1275-1297 (2013) · Zbl 1335.94018 · doi:10.1002/cpa.21442
[81] Plan, Y.; Vershynin, R., Robust 1-bit compressed sensing and sparse logistic regression: A convex programming approach, IEEE Trans. Inform. Theory, 59, 1, 482-494 (2013) · Zbl 1364.94153 · doi:10.1109/TIT.2012.2207945
[82] Plan, Y.; Vershynin, R., Dimension reduction by random hyperplane tessellations, Discret Comput. Geom., 51, 2, 438-461 (2014) · Zbl 1296.52014 · doi:10.1007/s00454-013-9561-6
[83] Powell, A.M., Saab, R., Yılmaz, Ö.: Quantization and finite frames. In: Finite Frames, pp. 267-302. Springer, New York (2013) · Zbl 1264.42013
[84] Powell, A.M., Whitehouse, J.T.: Error bounds for consistent reconstruction: Random polytopes and coverage processes. Found. Comput. Math. (2013). doi:doi:10.1007/s10208-015-9251-2. arXiv preprint arXiv:1405.7094 · Zbl 1341.62127
[85] Rane, S., Boufounos, P.T., Vetro, A.: Quantized embeddings: An efficient and universal nearest neighbor method for cloud-based image retrieval. In: Proceedings of SPIE Applications of Digital Image Processing XXXVI, (2013) 885609
[86] Rudelson, M.; Vershynin, R., On sparse reconstruction from Fourier and Gaussian measurements, Commun. Pure Appl. Math., 61, 1025-1045 (2008) · Zbl 1149.94010 · doi:10.1002/cpa.20227
[87] Rudelson, M.; Vershynin, R., Hanson-wright inequality and sub-gaussian concentration, Electron. Comm. Probab., 18, 1-9 (2013) · Zbl 1329.60056 · doi:10.1214/ECP.v18-2865
[88] Schütt, C., Entropy numbers of diagonal operators between symmetric Banach spaces, J. Approx. Theory, 40, 2, 121-128 (1984) · Zbl 0497.41017 · doi:10.1016/0021-9045(84)90021-2
[89] Sun, J.Z., Goyal, V.K.: Optimal quantization of random measurements in compressed sensing. In: Proceedings IEEE International Symposium on Information Theory (ISIT), pp. 6-10 (2009)
[90] Thao, N. T.; Vetterli, M., Lower bound on the mean-squared error in oversampled quantization of periodic signals using vector quantization analysis, IEEE Trans. Inform. Theory, 42, 2, 469-479 (1996) · Zbl 0855.94009 · doi:10.1109/18.485717
[91] Thao, N. T.; Vetterli, M., Reduction of the MSE in R-times oversampled A/D conversion O(1∕R) to O(1∕R^2), IEEE Trans. Signal Process., 42, 1, 200-203 (1994) · doi:10.1109/78.258137
[92] Varanasi, M. K.; Aazhang, B., Parametric generalized Gaussian density estimation, J. Acoust. Soc. Am., 86, 1404-1415 (1989) · doi:10.1121/1.398700
[93] Zymnis, A.; Boyd, S.; Candes, E., Compressed sensing with quantized measurements, IEEE Signal Proc. Lett., 17, 2, 149-152 (2010) · doi:10.1109/LSP.2009.2035667
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.