High-order block RIP for nonconvex block-sparse compressed sensing. (English) Zbl 07892349
Summary: This paper concentrates on the recovery of block-sparse signals, which are not only sparse but also nonzero elements are arrayed into some blocks (clusters) rather than being arbitrary distributed all over the vector, from linear measurements. We establish high-order sufficient conditions based on block RIP, which could ensure the exact recovery of every block \(s\)-sparse signal in the noiseless case via mixed \(l_2/l_p\) minimization method, and the stable and robust recovery in the case that signals are not accurately block-sparse in the presence of noise. Additionally, a lower bound on necessary number of random Gaussian measurements is gained for the condition to be true with overwhelming probability. Furthermore, a series of numerical experiments are conducted to demonstrate the performance of the mixed \(l_2/l_p\) minimization. To the best of the authors’ knowledge, the recovery guarantees established in this paper are superior to those currently available.
MSC:
| 94A12 | Signal theory (characterization, reconstruction, filtering, etc.) |
| 90C25 | Convex programming |
| 94A20 | Sampling theory in information and communication theory |
Keywords:
compressed sensing; block restricted isometry property; block sparsity; mixed \(l_2/l_p\) minimizationSoftware:
Yall1References:
| [1] | U. Ayaz, S. Dirksen and H. Rauhut, Uniform recovery of fusion frame structured sparse signals, Appl. Comput. Harmon. Anal. 41 (2016), no. 2, 341-361. · Zbl 1360.94061 |
| [2] | R. Baraniuk, M. Davenport, R. DeVore and M. Wakin, A simple proof of the restricted isometry property for random matrices, Constr. Approx. 28 (2008), no. 3, 253-263. · Zbl 1177.15015 |
| [3] | T. T. Cai and A. Zhang, Sharp RIP bound for sparse signal and low-rank matrix recovery, Appl. Comput. Harmon. Anal. 35 (2013), no. 1, 74-93. · Zbl 1310.94021 |
| [4] | T. T. Cai and A. Zhang, Sparse representation of a polytope and recovery of sparse signals and low-rank matrices, IEEE Trans. Inform. Theory 60 (2014), no. 1, 122-132. · Zbl 1364.94114 |
| [5] | Y. Cai, Weighted l_p-l_1 minimization methods for block sparse recovery and rank minimization, Anal. Appl. (Singap.) 19 (2021), no. 2, 343-361. · Zbl 1461.90092 |
| [6] | E. J. Candès, J. Romberg and T. Tao, Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information, IEEE Trans. Inform. Theory 52 (2006), no. 2, 489-509. · Zbl 1231.94017 |
| [7] | R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems 24 (2008), no. 3, Article ID 035020. · Zbl 1143.94004 |
| [8] | B. Chen and A. Wan, General RIP bounds of \(\delta_{tk}\) for sparse signals recovery by \(l_p\) minimization, Neurocomputing 363 (2019), 306-312. |
| [9] | S. F. Cotter and B. D. Rao, Sparse channel estimation via matching pursuit with application to equalization, IEEE Trans. Commun. 50 (2002), no. 3, 374-377. |
| [10] | W. Deng, W. Yin and Y. Zhang, Group sparse optimization by alternating direction method. Wavelets and sparsity XV, Int. Soc. Optics Photonics 8858 (2013), Article ID 88580. |
| [11] | S. Dirksen, G. Lecué and H. Rauhut, On the gap between restricted isometry properties and sparse recovery conditions, IEEE Trans. Inform. Theory 64 (2018), no. 8, 5478-5487. · Zbl 1401.94031 |
| [12] | D. L. Donoho, Compressed sensing, IEEE Trans. Inform. Theory 52 (2006), no. 4, 1289-1306. · Zbl 1288.94016 |
| [13] | Y. C. Eldar, P. Kuppinger and H. Bolcskei, Block-sparse signals: Uncertainty relations and efficient recovery, IEEE Trans. Signal Process. 58 (2010), no. 6, 3042-3054. · Zbl 1392.94195 |
| [14] | Y. C. Eldar and M. Mishali, Robust recovery of signals from a structured union of subspaces, IEEE Trans. Inform. Theory 55 (2009), no. 11, 5302-5316. · Zbl 1367.94087 |
| [15] | E. Elhamifar and R. Vidal, Block-sparse recovery via convex optimization, IEEE Trans. Signal Process. 60 (2012), no. 8, 4094-4107. · Zbl 1393.94681 |
| [16] | A. Elzanaty, A. Giorgetti and M. Chiani, Limits on sparse data acquisition: RIC analysis of finite Gaussian matrices, IEEE Trans. Inform. Theory 65 (2019), no. 3, 1578-1588. · Zbl 1431.94016 |
| [17] | Y. Gao and M. Ma, A new bound on the block restricted isometry constant in compressed sensing, J. Inequal. Appl. 2017 (2017), Paper No. 174. · Zbl 1380.46008 |
| [18] | Y. Gao, J. Peng and S. Yue, Stability and robustness of the \(l_2/l_q\)-minimization for block sparse recovery, Signal Process. 137 (2017), 287-297. |
| [19] | Y. Gao, J. Peng, S. Yue and Y. Zhao, On the null space property of l_q-minimization for 0<q\leq 1 in compressed sensing, J. Funct. Spaces 2015 (2015), Article ID 579853. · Zbl 1366.94099 |
| [20] | H. Ge and W. Chen, Recovery of signals by a weighted \(l_2/l_1\) minimization under arbitrary prior support information, Signal Process. 148 (2018), 288-302. |
| [21] | S. H. Ghalehjegh, M. Babaie-Zadeh and C. Jutten, Fast block-sparse decomposition based on SL0, International Conference on Latent Variable Analysis and Signal Separation, Springer, Berlin (2010), 426-433. |
| [22] | J. Huang, X. Huang and D. Metaxas, Learning with dynamic group sparsity, 2009 IEEE 12th International Conference on Computer Vision, IEEE Press, Piscataway (2009), 64-71. |
| [23] | J. Huang, J. Wang and W. Wang, Sharp sufficient condition of block signal recovery via \(l_2/l_1\)-minimisation, IET Signal Process. 13 (2019), no. 5, 495-505. |
| [24] | M.-J. Lai, Y. Xu and W. Yin, Improved iteratively reweighted least squares for unconstrained smoothed \ell_q minimization, SIAM J. Numer. Anal. 51 (2013), no. 2, 927-957. · Zbl 1268.49038 |
| [25] | H. Li and J. Wen, A new analysis for support recovery with block orthogonal matching pursuit, IEEE Signal Process. Lett. 26 (2018), no. 2, 247-251. |
| [26] | Y. Li, Signal and low-rank matrix recovery based on the restricted isometric property, Chinese Academy of Engineering Physics, 2017. |
| [27] | Y. Li and W. Chen, The high order block RIP condition for signal recovery, J. Comput. Math. 37 (2019), no. 1, 61-75. · Zbl 1438.94033 |
| [28] | J. H. Lin and S. Li, Block sparse recovery via mixed l_2/l_1 minimization, Acta Math. Sin. (Engl. Ser.) 29 (2013), no. 7, 1401-1412. · Zbl 1322.94034 |
| [29] | C. Liu, F. Zhang, W. Qiu, C. Li and Z. Leng, A perturbation analysis based on group sparse representation with orthogonal matching pursuit, J. Inverse Ill-Posed Probl. 29 (2021), no. 5, 653-674. · Zbl 1473.94017 |
| [30] | C. Lu, J. Feng and Z. Lin, Exact low tubal rank tensor recovery from Gaussian measurements, Proceedings of the 27th International Joint Conference on Artificial Intelligence, AAAI Press, Washington (2018), 2504-2510. |
| [31] | A. Majumdar and R. K. Ward, Compressed sensing of color images, Signal Process. 90 (2010), no. 12, 3122-3127. · Zbl 1197.94089 |
| [32] | F. Parvaresh, H. Vikalo and S. Misra, Recovering sparse signals using sparse measurement matrices in compressed DNA microarrays, IEEE J. Selected Topics Signal Process. 2 (2008), no. 3, 275-285. |
| [33] | A. Petukhov, Fast implementation of orthogonal greedy algorithm for tight wavelet frames, Signal Process. 86 (2006), no. 3, 471-479. · Zbl 1163.94371 |
| [34] | Y. Shen and S. Li, Restricted p-isometry property and its application for nonconvex compressive sensing, Adv. Comput. Math. 37 (2012), no. 3, 441-452. · Zbl 1260.94028 |
| [35] | M. Stojnic, F. Parvaresh and B. Hassibi, On the reconstruction of block-sparse signals with an optimal number of measurements, IEEE Trans. Signal Process. 57 (2009), no. 8, 3075-3085. · Zbl 1391.94402 |
| [36] | A. Wan, Uniform RIP conditions for recovery of sparse signals by \ell_p(0<p\leq 1) minimization, IEEE Trans. Signal Process. 68 (2020), 5379-5394. · Zbl 07591111 |
| [37] | J. Wang, J. Huang, F. Zhang and W. Wang, Group sparse recovery in impulsive noise via alternating direction method of multipliers, Appl. Comput. Harmon. Anal. 49 (2020), no. 3, 831-862. · Zbl 1458.94139 |
| [38] | W. Wang, Perturbation analysis of L_{1-2} method for robust sparse recovery, J. Inverse Ill-Posed Probl. 30 (2022), no. 5, 767-776. · Zbl 1498.94027 |
| [39] | W. Wang, J. Wang and Z. Zhang, Block-sparse signal recovery via \(l_2/l_{1-2}\) minimisation method, IET Signal Process. 12 (2017), no. 4, 422-430. |
| [40] | W. Wang, F. Zhang, Z. Wang and J. Wang, Coherence-based robust analysis of basis pursuit de-noising and beyond, IEEE Access 7 (2019), 173216-173229. |
| [41] | Y. Wang, J. Wang and Z. Xu, On recovery of block-sparse signals via mixed \(l_2/l_q(0<q\leq 1)\) norm minimization, EURASIP J. Adv. Signal Process. 2013 (2013), no. 1, 1-17. |
| [42] | Y. Wang, J. Wang and Z. Xu, Restricted p-isometry properties of nonconvex block-sparse compressed sensing, Signal Process. 104 (2014), 188-196. |
| [43] | F. Wen, P. Liu, Y. Liu, R. C. Qiu and W. Yu, Robust sparse recovery in impulsive noise via \ell_p-\ell_1 optimization, IEEE Trans. Signal Process. 65 (2017), no. 1, 105-118. · Zbl 1414.94672 |
| [44] | J. Wen, Z. Zhou, Z. Liu, M.-J. Lai and X. Tang, Sharp sufficient conditions for stable recovery of block sparse signals by block orthogonal matching pursuit, Appl. Comput. Harmon. Anal. 47 (2019), no. 3, 948-974. · Zbl 1422.94017 |
| [45] | C.-H. Zhang and T. Zhang, A general theory of concave regularization for high-dimensional sparse estimation problems, Statist. Sci. 27 (2012), no. 4, 576-593. · Zbl 1331.62353 |
| [46] | J. Zhang and S. Zhang, Recovery analysis for block \ell_p-\ell_1 minimization with prior support information, Int. J. Wavelets Multiresolut. Inf. Process. 20 (2022), no. 4, Article ID 2150057. · Zbl 1493.90136 |
| [47] | R. Zhang and S. Li, Optimal RIP bounds for sparse signals recovery via \ell_p minimization, Appl. Comput. Harmon. Anal. 47 (2019), no. 3, 566-584. · Zbl 1422.94018 |
| [48] | Z. Zhou, RIP analysis for the weighted \(\ell_r-\ell_1\) minimization method, Signal Process. 202 (2023), Article ID 108754. |
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.
