×

A simple Gaussian measurement bound for exact recovery of block-sparse signals. (English) Zbl 1419.94016

Summary: We present a probabilistic analysis on conditions of the exact recovery of block-sparse signals whose nonzero elements appear in fixed blocks. We mainly derive a simple lower bound on the necessary number of Gaussian measurements for exact recovery of such block-sparse signals via the mixed \(l_2/l_q\) (\(0 < q \leq 1\)) norm minimization method. In addition, we present numerical examples to partially support the correctness of the theoretical results. The obtained results extend those known for the standard \(l_q\) minimization and the mixed \(l_2 / l_1\) minimization methods to the mixed \(l_2/l_q\) (\(0 < q \leq 1\)) minimization method in the context of block-sparse signal recovery.

MSC:

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

Software:

PDCO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Parvaresh, F.; Vikalo, H.; Misra, S.; Hassibi, B., Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays, IEEE Journal on Selected Topics in Signal Processing, 2, 3, 275-285 (2008) · doi:10.1109/JSTSP.2008.924384
[2] Rao, N. S.; Nowak, R. D.; Wright, S. J.; Kingsbury, N. G., Convex approaches to model wavelet sparsity patterns, Proceedings of the 18th IEEE International Conference on Image Processing (ICIP ’11) · doi:10.1109/ICIP.2011.6115845
[3] Majumdar, A.; Ward, R. K., Compressed sensing of color images, Signal Processing, 90, 12, 3122-3127 (2010) · Zbl 1197.94089 · doi:10.1016/j.sigpro.2010.05.016
[4] Mishali, M.; Eldar, Y. C., Blind multiband signal reconstruction: compressed sensing for analog signals, IEEE Transactions on Signal Processing, 57, 3, 993-1009 (2009) · Zbl 1391.94324 · doi:10.1109/TSP.2009.2012791
[5] Donoho, D. L., Compressed sensing, IEEE Transactions on Information Theory, 52, 4, 1289-1306 (2006) · Zbl 1288.94016 · doi:10.1109/TIT.2006.871582
[6] Candès, E. J.; Romberg, J.; Tao, T., Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information, IEEE Transactions on Information Theory, 52, 2, 489-509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[7] Candes, E. J.; Tao, T., Near-optimal signal recovery from random projections: universal encoding strategies?, IEEE Transactions on Information Theory, 52, 12, 5406-5425 (2006) · Zbl 1309.94033 · doi:10.1109/TIT.2006.885507
[8] Eldar, Y. C.; Mishali, M., Robust recovery of signals from a structured union of subspaces, IEEE Transactions on Information Theory, 55, 11, 5302-5316 (2009) · Zbl 1367.94087 · doi:10.1109/TIT.2009.2030471
[9] Stojnic, M.; Parvaresh, F.; Hassibi, B., On the reconstruction of block-sparse signals with an optimal number of measurements, IEEE Transactions on Signal Processing, 57, 8, 3075-3085 (2009) · Zbl 1391.94402 · doi:10.1109/TSP.2009.2020754
[10] Eldar, Y. C.; Kuppinger, P.; Bolcskei, H., Block-sparse signals: uncertainty relations and efficient recovery, IEEE Transactions on Signal Processing, 58, 6, 3042-3054 (2010) · Zbl 1392.94195 · doi:10.1109/TSP.2010.2044837
[11] Wang, Y.; Wang, J.; Xu, Z., On recovery of block-sparse signals via mixed \(l_2 = l q(0 < q \leq 1)\) norm minimization, Eurasip Journal on Advances in Signal Processing, 2013, 1, article 76 (2013) · doi:10.1186/1687-6180-2013-76
[12] Chen, S. S.; Donoho, D. L.; Saunders, M. A., Atomic decomposition by basis pursuit, SIAM Journal on Scientific Computing, 20, 1, 33-61 (1998) · Zbl 0919.94002 · doi:10.1137/S1064827596304010
[13] Yuan, M.; Lin, Y., Model selection and estimation in regression with grouped variables, Journal of the Royal Statistical Society B, 68, 1, 49-67 (2006) · Zbl 1141.62030 · doi:10.1111/j.1467-9868.2005.00532.x
[14] Fornasier, M.; Rauhut, H., Recovery algorithms for vector-valued data with joint sparsity constraints, SIAM Journal on Numerical Analysis, 46, 2, 577-613 (2008) · Zbl 1211.65066 · doi:10.1137/0606668909
[15] Huang, J.; Zhang, T., The benefit of group sparsity, The Annals of Statistics, 38, 4, 1978-2004 (2010) · Zbl 1202.62052 · doi:10.1214/09-AOS778
[16] Chartrand, R., Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters, 14, 10, 707-710 (2007) · doi:10.1109/LSP.2007.898300
[17] Chartrand, R.; Staneva, V., Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24, 3 (2008) · Zbl 1143.94004 · doi:10.1088/0266-5611/24/3/035020
[18] Foucart, S.; Lai, M. J., Sparsest solutions of underdetermined linear systems via \(l_q\)-minimization for \(\text{0} < q \leq \text{1} \), Applied and Computational Harmonic Analysis, 26, 3, 395-407 (2009)
[19] Xu, Z.; Zhang, H.; Wang, Y.; Chang, X.; Liang, Y., \(L_{1/2}\) regularization, Science China. Information Sciences, 53, 6, 1159-1169 (2010) · Zbl 1497.62192 · doi:10.1007/s11432-010-0090-0
[20] Xu, Z.; Chang, X.; Xu, F.; Zhang, H., \(L_{1 / 2}\) regularization: a thresholding representation theory and a fast solver, IEEE Transactions on Neural Networks and Learning Systems, 23, 7, 1013-1027 (2012) · doi:10.1109/TNNLS.2012.2197412
[21] Sun, Q., Recovery of sparsest signals via \(\ell q\)-minimization, Applied and Computational Harmonic Analysis, 32, 3, 329-341 (2012) · Zbl 1266.94017 · doi:10.1016/j.acha.2011.07.001
[22] Daubechies, I.; DeVore, R.; Fornasier, M.; Güntürk, C. S., Iteratively reweighted least squares minimization for sparse recovery, Communications on Pure and Applied Mathematics, 63, 1, 1-38 (2010) · Zbl 1202.65046 · doi:10.1002/cpa.20303
[23] Baraniuk, R.; Davenport, M.; DeVore, R.; Wakin, M., A simple proof of the restricted isometry property for random matrices, Constructive Approximation, 28, 3, 253-263 (2008) · Zbl 1177.15015 · doi:10.1007/s00365-007-9003-x
[24] Lai, M. J.; Liu, L. Y., A new estimate of restricted isometry constants for sparse solutions, Applied and Computational Harmonic Analysis, 30, 402-406 (2011) · Zbl 1228.65057 · doi:10.1016/j.acha.2010.11.002
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.