Applications of Mathematics, Vol. 70, No. 1, pp. 125-148, 2025
Theoretical analysis for $\ell_1$-$\ell_2$ minimization with partial support information
Haifeng Li, Leiyan Guo
Received March 23, 2024. Published online November 26, 2024.
Abstract: We investigate the recovery of $k$-sparse signals using the $\ell_1$-$\ell_2$ minimization model with prior support set information. The prior support set information, which is believed to contain the indices of nonzero signal elements, significantly enhances the performance of compressive recovery by improving accuracy, efficiency, reducing complexity, expanding applicability, and enhancing robustness. We assume $k$-sparse signals ${\bf x}$ with the prior support $T$ which is composed of $g$ true indices and $b$ wrong indices, i.e., $|T|=g+b\leq k$. First, we derive a new condition based on RIP of order $2\alpha$ $(\alpha=k-g)$ to guarantee signal recovery via $\ell_1$-$\ell_2$ minimization with partial support information. Second, we also derive the high order RIP with $t\alpha$ for some $t\geq3$ to guarantee signal recovery via $\ell_1$-$\ell_2$ minimization with partial support information.
References: [1] N. Bi, J. Tan, W.-S. Tang: A new sufficient condition for sparse vector recovery via $\ell_1$-$\ell_2$ local minimization. Anal. Appl., Singap. 19 (2021), 1019-1031. DOI 10.1142/S0219530521500068 | MR 4328764 | Zbl 1492.94029
[2] N. Bi, W.-S. Tang: A necessary and sufficient condition for sparse vector recovery via $\ell_1-\ell_2$ minimization. Appl. Comput. Harmon. Anal. 56 (2022), 337-350. DOI 10.1016/j.acha.2021.09.003 | MR 4324183 | Zbl 1485.90095
[3] T. Cai, L. Wang, G. Xu: Shifting inequality and recovery of sparse signals. IEEE Trans. Signal Process. 58 (2010), 1300-1308. DOI 10.1109/TSP.2009.2034936 | MR 2730209 | Zbl 1392.94117
[4] T. Cai, A. Zhang: Compressed sensing and affine rank minimization under restricted isometry. IEEE Trans. Signal Process. 61 (2013), 3279-3290. DOI 10.1109/TSP.2013.2259164 | MR 3070321 | Zbl 1393.94185
[5] E. J. Candès: The restricted isometry property and its implications for compressed sensing. C. R., Math., Acad. Sci. Paris 346 (2008), 589-592. DOI 10.1016/j.crma.2008.03.014 | MR 2412803 | Zbl 1153.94002
[6] E. J. Candès, Y. Plan: Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements. IEEE Trans. Inf. Theory 57 (2011), 2342-2359. DOI 10.1109/TIT.2011.2111771 | MR 2809094 | Zbl 1366.90160
[7] E. J. Candès, T. Tao: Decoding by linear programming. IEEE Trans. Inf. Theory 51 (2005), 4203-4215. DOI 10.1109/TIT.2005.858979 | MR 2243152 | Zbl 1264.94121
[8] D. L. Donoho, M. Elad, V. N. Temlyakov: Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inf. Theory 52 (2006), 6-18. DOI 10.1109/TIT.2005.860430 | MR 2237332 | Zbl 1288.94017
[9] D. L. Donoho, X. Huo: Uncertainty principles and ideal atomic decomposition. IEEE Trans. Inf. Theory 47 (2001), 2845-2862. DOI 10.1109/18.959265 | MR 1872845 | Zbl 1019.94503
[10] S. Foucart, H. Rauhut: A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser, New York (2013). DOI 10.1007/978-0-8176-4948-7 | MR 3100033 | Zbl 1315.94002
[11] H. Ge, W. Chen: An optimal recovery condition for sparse signals with partial support information via OMP. Circuits Syst. Signal Process. 38 (2019), 3295-3320. DOI 10.1007/s00034-018-01022-9
[12] H. Ge, W. Chen, M. K. Ng: New restricted isometry property analysis for $\ell_1-\ell_2$ minimization methods. SIAM J. Imaging Sci. 14 (2021), 530-557. DOI 10.1137/20M136517X | MR 4252074 | Zbl 1474.94041
[13] Z. He, H. He, X. Liu, J. Wen: An improved sufficient condition for sparse signal recovery with minimization of $\ell_1-\ell_2$. IEEE Signal Process. Lett. 29 (2022), 907-911. DOI 10.1109/LSP.2022.3158839
[14] C. Herzet, C. Soussen, J. Idier, R. Gribonval: Exact recovery conditions for sparse representations with partial support information. IEEE Trans. Inf. Theory 59 (2013), 7509-7524. DOI 10.1109/TIT.2013.2278179 | MR 3124657 | Zbl 1364.94128
[15] L. Jacques: A short note on compressed sensing with partially known signal support. Signal Process. 90 (2010), 3308-3312. DOI 10.1016/j.sigpro.2010.05.025 | Zbl 1197.94063
[16] P. Li, W. Chen: Signal recovery under cumulative coherence. J. Comput. Appl. Math. 346 (2019), 399-417. DOI 10.1016/j.cam.2018.07.019 | MR 3864169 | Zbl 1405.94025
[17] T.-H. Ma, Y. Lou, T.-Z. Huang: Truncated $\ell_{1-2}$ models for sparse recovery and rank minimization. SIAM J. Imaging Sci. 10 (2017), 1346-1380. DOI 10.1137/16M1098929 | MR 3687849 | Zbl 1397.94021
[18] Q. Mo, S. Li: New bounds on the restricted isometry constant $\delta_{2k}$. Appl. Comput. Harmon. Anal. 31 (2011), 460-468. DOI 10.1016/j.acha.2011.04.005 | MR 2836035 | Zbl 1231.94027
[19] J. Scarlett, J. S. Evans, S. Dey: Compressed sensing with prior information: Information-theoretic limits and practical decoders. IEEE Trans. Signal Process. 61 (2013), 427-439. DOI 10.1109/TSP.2012.2225051 | MR 3009136 | Zbl 1393.94759
[20] R. von Borries, C. J. Miosso, C. Potes: Compressed sensing using prior information. 2nd IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing. IEEE, Philadelphia (2007), 121-124. DOI 10.1109/CAMSAP.2007.4497980
[21] W. Wang, J. Wang: Improved sufficient condition of $\ell_{1-2}$-minimisation for robust signal recovery. Electron. Lett. 55 (2019), 1199-1201. DOI 10.1049/el.2019.2205
[22] J. Wen, J. Weng, C. Tong, C. Ren, Z. Zhou: Sparse signal recovery with minimization of 1-norm minus 2-norm. IEEE Trans. Vehicular Technol. 68 (2019), 6847-6854. DOI 10.1109/TVT.2019.2919612
[23] P. Yin, Y. Lou, Q. He, J. Xin: Minimization of $\ell_{1-2}$ for compressed sensing. SIAM J. Sci. Comput. 37 (2015), A536-A563. DOI 10.1137/140952363 | MR 3315229 | Zbl 1316.90037
[24] J. Zhang, S. Zhang, X. Meng: $\ell_{1-2}$ minimisation for compressed sensing with partially known signal support. Electron. Lett. 56 (2020), 405-408. DOI 10.1049/el.2019.3859
Affiliations: Haifeng Li (corresponding author), Leiyan Guo, Henan Engineering Laboratory for Big Data Statistical Analysis and Optimal Control, College of Mathematics and Information Science, Henan Normal University, 46 Jianshe E Rd, Muye District, Xinxiang, 453007, P. R. China, e-mail: lihaifengxx@126.com, guoleiyan@163.com
