×

Quantization of compressive samples with stable and robust recovery. (English) Zbl 1375.94079

Summary: In this paper we study the quantization stage that is implicit in any compressed sensing signal acquisition paradigm. We propose using Sigma-Delta \((\Sigma\Delta)\) quantization and a subsequent reconstruction scheme based on convex optimization. We prove that the reconstruction error due to quantization decays polynomially in the number of measurements. Our results apply to arbitrary signals, including compressible ones, and account for measurement noise. Additionally, they hold for sub-Gaussian (including Gaussian and Bernoulli) random compressed sensing measurements, as well as for both high bit-depth and coarse quantizers, and they extend to 1-bit quantization. In the noise-free case, when the signal is strictly sparse we prove that by optimizing the order of the quantization scheme one can obtain root-exponential decay in the reconstruction error due to quantization.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
60B20 Random matrices (probabilistic aspects)

Software:

CoSaMP
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bajwa, Waheed U.; Haupt, Jarvis D.; Raz, Gil M.; Wright, Stephen J.; Nowak, Robert D., Toeplitz-structured compressed sensing matrices, (IEEE/SP 14th Workshop on Statistical Signal Processing, 2007. IEEE/SP 14th Workshop on Statistical Signal Processing, 2007, SSP’07 (2007), IEEE), 294-298
[2] Baraniuk, Richard; Foucart, Simon; Needell, Deanna; Plan, Yaniv; Wootters, Mary, Exponential decay of reconstruction error from binary measurements of sparse signals (2014), arXiv preprint
[3] Baraniuk, Richard G.; Cevher, Volkan; Duarte, Marco F.; Hegde, Chinmay, Model-based compressive sensing, IEEE Trans. Inform. Theory, 56, 4, 1982-2001 (2010) · Zbl 1366.94215
[4] 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
[5] 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
[6] Blumensath, T.; Davies, M. E., Iterative hard thresholding for compressed sensing, Appl. Comput. Harmon. Anal., 27, 3, 265-274 (2009) · Zbl 1174.94008
[7] 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
[8] Boufounos, P. T., Universal rate-efficient scalar quantization, IEEE Trans. Inform. Theory, 58, 3, 1861-1872 (2012) · Zbl 1365.94065
[9] Boufounos, Petros T.; Jacques, Laurent; Krahmer, Felix; Saab, Rayan, Quantization and compressive sensing (2014), arXiv preprint · Zbl 1333.94016
[10] Boufounos, P. T.; Baraniuk, R. G., 1-bit compressive sensing, (42nd Annual Conference on Information Sciences and Systems, 2008. 42nd Annual Conference on Information Sciences and Systems, 2008, CISS 2008 (2008), IEEE), 16-21
[11] Candès, E. J.; Romberg, J.; Tao, T., Stable signal recovery from incomplete and inaccurate measurements, Comm. Pure Appl. Math., 59, 1207-1223 (2006) · Zbl 1098.94009
[12] Candes, Emmanuel; Romberg, Justin, Encoding the \(\ell_p\) ball from limited measurements, (Proceedings of Data Compression Conference. Proceedings of Data Compression Conference, DCC (2006)), 33-42
[13] Casazza, Peter G.; Kutyniok, Gitta, Finite Frames (2012), Springer · Zbl 1261.42048
[14] Chou, E.; Güntürk, C. S., Distributed noise-shaping quantization: I. beta duals of finite frames and near-optimal quantization of random measurements (2015), arXiv preprint · Zbl 1361.94033
[15] Chou, E.; Güntürk, C. S.; Krahmer, F.; Saab, R.; Yılmaz, Ö., Noise-shaping quantization methods for frame-based and compressive sampling systems (2015), arXiv preprint · Zbl 1358.94023
[16] Dai, W.; Milenkovic, O., Subspace pursuit for compressive sensing signal reconstruction, IEEE Trans. Inform. Theory, 55, 5, 2230-2249 (2009) · Zbl 1367.94082
[17] 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., 158, 2, 679-710 (2003) · Zbl 1058.94004
[18] Daubechies, Ingrid; DeVore, Ronald A.; Gunturk, C. S.; Vaishampayan, Vinay A., A/d conversion with imperfect quantizers, IEEE Trans. Inform. Theory, 52, 3, 874-885 (2006) · Zbl 1231.94036
[19] Deift, P.; Güntürk, C. S.; Krahmer, F., An optimal family of exponentially accurate one-bit sigma-delta quantization schemes, Comm. Pure Appl. Math., 64, 7, 883-919 (2011) · Zbl 1248.94035
[20] Donoho, D. L., Compressed sensing, IEEE Trans. Inform. Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016
[21] Donoho, D. L.; Maleki, A.; Montanari, A., Message-passing algorithms for compressed sensing, Proc. Natl. Acad. Sci. USA, 106, 45, 18914-18919 (2009)
[22] Feng, J.; Krahmer, F., An RIP-based approach to ΣΔ quantization for compressed sensing, IEEE Signal Process. Lett., 21, 11, 1351-1355 (2014)
[23] Foucart, S., Stability and robustness of \(\ell_1\)-minimizations with Weibull matrices and redundant dictionaries, Linear Algebra Appl., 441, 4-21 (2014) · Zbl 1332.94042
[24] Friedlander, M. P.; Mansour, H.; Saab, R.; Yilmaz, O., Recovering compressively sampled signals using partial support information, IEEE Trans. Inform. Theory, 58, 2, 1122-1134 (Feb. 2012) · Zbl 1365.94071
[25] Goyal, V. K.; Vetterli, M.; Thao, N. T., Quantized overcomplete expansions in \(R^N\): analysis, synthesis, and algorithms, IEEE Trans. Inform. Theory, 44, 1, 16-31 (Jan. 1998) · Zbl 0905.94007
[26] Güntürk, C. S., One-bit sigma-delta quantization with exponential accuracy, Comm. Pure Appl. Math., 56, 11, 1608-1630 (2003) · Zbl 1029.94006
[27] Güntürk, C. S.; Lammers, M.; Powell, A. M.; Saab, R.; Yılmaz, Ö., Sobolev duals for random frames and sigma-delta quantization of compressed sensing measurements, Found. Comput. Math., 13, 1, 1-36 (2013) · Zbl 1273.41020
[28] Inose, H.; Yasuda, Y., A unity bit coding method by negative feedback, Proc. IEEE, 51, 11, 1524-1535 (1963)
[29] Iwen, M.; Saab, R., Near-optimal encoding for sigma-delta quantization of finite frame expansions, J. Fourier Anal. Appl., 1-19 (2013) · Zbl 1304.42073
[30] 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 (January 2011) · Zbl 1366.94106
[31] Jacques, L.; Hammond, D. K.; Fadili, M. J., Stabilizing nonuniformly quantized compressed sensing with scalar companders, IEEE Trans. Inform. Theory, 59, 12, 7969-7984 (January 2013) · Zbl 1364.94129
[32] 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
[33] Kamilov, Ulugbek S.; Goyal, Vivek K.; Rangan, Sundeep, Message-passing de-quantization with applications to compressed sensing, IEEE Trans. Signal Process., 60, 12, 6270-6281 (2012) · Zbl 1393.94290
[34] Knudson, Karin; Saab, Rayan; Ward, Rachel, One-bit compressive sensing with norm estimation (2014), arXiv preprint · Zbl 1359.94117
[35] Kovacevic, Jelena; Chebira, Amina, Life beyond bases: the advent of frames (part I), IEEE Signal Process. Mag., 24, 4, 86-104 (2007)
[36] Krahmer, F.; Saab, R.; Ward, R., Root-exponential accuracy for coarse quantization of finite frame expansions, IEEE Trans. Inform. Theory, 58, 2, 1069-1079 (February 2012) · Zbl 1365.94080
[37] Krahmer, F.; Saab, R.; Yılmaz, Ö., Sigma-Delta quantization of sub-Gaussian frame expansions and its application to compressed sensing, Inf. Inference, 3, 1, 40-58 (2013) · Zbl 1308.94034
[38] Krahmer, Felix; Mendelson, Shahar; Rauhut, Holger, Suprema of chaos processes and the restricted isometry property, Comm. Pure Appl. Math., 67, 11, 1877-1904 (2014) · Zbl 1310.94024
[39] Lammers, M.; Powell, A. M.; Yılmaz, Ö., Alternative dual frames for digital-to-analog conversion in sigma-delta quantization, Adv. Comput. Math., 1-30 (2008)
[40] Lorentz, G. G.; von Golitschek, M.; Makovoz, Y., Constructive Approximation: Advanced Problems, Grundlehren Math. Wiss. (1996), Springer · Zbl 0910.41001
[41] Mansour, H.; Saab, R., Recovery analysis for weighted \(\ell_1\)-minimization using a null space property (2012), arXiv preprint
[42] Needell, D.; Tropp, J. A., Cosamp: iterative signal recovery from incomplete and inaccurate samples, Appl. Comput. Harmon. Anal., 26, 3, 301-321 (2009) · Zbl 1163.94003
[43] (Norsworthy, S. R.; Schreier, R.; Temes, G. C., Delta-Sigma-Converters: Theory, Design and Simulation (1996), Wiley-IEEE)
[44] Pfander, Götz E.; Rauhut, Holger; Tropp, Joel A., The restricted isometry property for time-frequency structured random matrices, Probab. Theory Related Fields, 156, 3-4, 707-737 (2013) · Zbl 1284.60018
[45] Plan, Y.; Vershynin, R., One-bit compressed sensing by linear programming, Comm. Pure Appl. Math., 66, 8, 1275-1297 (2013) · Zbl 1335.94018
[46] Powell, A. M.; Saab, R.; Yılmaz, Ö., Quantization and finite frames, (Casazza, P. G.; Kutyniok, G., Finite Frames. Finite Frames, ANHA (2013), Birkhäuser: Birkhäuser Boston), 267-302 · Zbl 1264.42013
[47] Rauhut, Holger; Romberg, Justin; Tropp, Joel A., Restricted isometries for partial random circulant matrices, Appl. Comput. Harmon. Anal., 32, 2, 242-254 (2012) · Zbl 1245.15040
[48] Rudelson, M.; Vershynin, R., Smallest singular value of a random rectangular matrix, Comm. Pure Appl. Math., 62, 12, 1707-1739 (2009) · Zbl 1183.15031
[49] Saab, Rayan; Yılmaz, Özgür, Sparse recovery by non-convex optimization - instance optimality, Appl. Comput. Harmon. Anal., 29, 1, 30-48 (2010) · Zbl 1200.90158
[50] Carsten, Schütt, Entropy numbers of diagonal operators between symmetric Banach spaces, J. Approx. Theory, 40, 2, 121-128 (1984) · Zbl 0497.41017
[51] Vershynin, R., Introduction to the non-asymptotic analysis of random matrices, (Eldar, Y. C.; Kutyniok, G., Compressed Sensing: Theory and Applications (2012), Cambridge Univ. Press: Cambridge Univ. Press Cambridge), pages xii+544
[52] Yilmaz, Özgür, Stability analysis for several second-order sigma-delta methods of coarse quantization of bandlimited functions, Constr. Approx., 18, 4, 599-623 (2002) · Zbl 1020.94510
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.