STABLE RECOVERY OF SPARSE SIGNALS WITH NON-CONVEX WEIGHTED r-NORM MINUS 1-NORM

Jianwen Huang, Feng Zhang, Xinling Liu, Jianjun Wang, Jinping Jia, Runke Wang

Journal of Computational Mathematics ›› 2025, Vol. 43 ›› Issue (1) : 43-62.

中国科学院数学与系统科学研究院期刊网
Advanced Search
JCM
Journal of Computational Mathematics ›› 2025, Vol. 43 ›› Issue (1) : 43-62. DOI: 10.4208/jcm.2307-m2022-0225

STABLE RECOVERY OF SPARSE SIGNALS WITH NON-CONVEX WEIGHTED r-NORM MINUS 1-NORM

  • Jianwen Huang1,2, Feng Zhang3, Xinling Liu4, Jianjun Wang5,6, Jinping Jia7, Runke Wang8
Author information +
History +

Abstract

Given the measurement matrix A and the observation signal y, the central purpose of compressed sensing is to find the most sparse solution of the underdetermined linear system y = Ax + z, where x is the s-sparse signal to be recovered and z is the noise vector. Zhou and Yu [Front. Appl. Math. Stat., 5 (2019), Article 14] recently proposed a novel non-convex weighted ℓr - ℓ1 minimization method for effective sparse recovery. In this paper, under newly coherence-based conditions, we study the non-convex weighted ℓr - ℓ1 minimization in reconstructing sparse signals that are contaminated by different noises.Concretely, the results reveal that if the coherence μ of measurement matrix A fulfills μ<κ(s;r,α,N),s>1,α1rN12<1, then any s-sparse signals in the noisy scenarios could be ensured to be reconstructed robustly by solving weighted ℓr - ℓ1 minimization non-convex optimization problem. Furthermore, some central remarks are presented to clear that the reconstruction assurance is much weaker than the existing ones. To the best of our knowledge, this is the first mutual coherence-based sufficient condition for such approach.

Key words

Compressed sensing / Sparse recovery / Mutual coherence / Sufficient condition

Cite this article

EndNote

Ris (Procite)

Bibtex

Download Citations
Jianwen Huang, Feng Zhang, Xinling Liu, Jianjun Wang, Jinping Jia, Runke Wang. STABLE RECOVERY OF SPARSE SIGNALS WITH NON-CONVEX WEIGHTED r-NORM MINUS 1-NORM. Journal of Computational Mathematics, 2025, 43(1): 43-62 https://doi.org/10.4208/jcm.2307-m2022-0225

References

[1] T. Cai, L. Wang, and G. Xu, Stable recovery of sparse signals and an oracle inequality, IEEE Trans. Inf. Theory, 56:7(2010), 3516-3522.
[2] Y. Cai, Weighted lp - l1 minimization methods for block sparse recovery and rank minimization, Anal. Appl., 19:2(2021), 343-361.
[3] E.J. Candès and T. Tao, Decoding by linear programming, IEEE Trans. Inf. Theory, 51:12(2005), 4203-4215.
[4] E.J. Candès and T. Tao, The Dantzig selector: Statistical estimation when p is much larger than n, Ann. Statist., 35:6(2007), 2313-2351.
[5] R. Chartrand, Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Process. Lett., 14:10(2007), 707-710.
[6] R. Chartrand and V. Staneva, Restricted isometry properties and nonconvex compressive sensing, Inverse Problems, 24:3(2008), 035020.
[7] S. Chen, D.L. Donoho, and M.A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev., 43:1(2001), 129-159.
[8] D.L. Donoho, Compressed sensing, IEEE Trans. Inf. Theory, 52:4(2006), 1289-1306.
[9] D.L. Donoho, M. Elad, and V.N. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Inf. Theory, 52:1(2006), 6-18.
[10] D.L. Donoho and X. Huo, Uncertainty principles and ideal atomic decomposition, IEEE Trans. Inf. Theory, 47:7(2001), 2845-2862.
[11] H. Ge, W. Chen, and M.K. Ng, On recovery of sparse signals with prior support information via weighted ℓp-minimization, IEEE Trans. Inf. Theory, 67:11(2021), 7579-7595.
[12] Z. He, H. He, X. Liu, and J. Wen, An improved sufficient condition for sparse signal recovery with minimization of L1-L2, IEEE Signal Process. Lett., 29(2022), 907-911.
[13] W. Kong, J. Wang, W. Wang, and F. Zhang, Enhanced block-sparse signal recovery performance via truncated ℓ2/ℓ1-2 minimization, J. Comput. Math., 38:3(2020), 437-451.
[14] M. Lai, Y. Xu, and W. Yin, Improved iteratively reweighted least squares for unconstrained smoothed ℓq minimization, SIAM J. Numer. Anal., 51:2(2013), 927-957.
[15] Y. Li and W. Chen, The high order block RIP condition for signal recovery, J. Comput. Math., 37:1(2018), 61-75.
[16] J. Lin and S. Li, Block sparse recovery via mixed l2/l1 minimization, Acta Math. Sin. Engl. Ser., 29:7(2013), 1401-1412.
[17] J. Lin and S. Li, Restricted q-isometry properties adapted to frames for nonconvex lq-analysis, IEEE Trans. Inf. Theory, 62:8(2016), 4733-4747.
[18] J.A. Tropp, Greed is good: Algorithmic results for sparse approximation, IEEE Trans. Inf. Theory, 50:10(2004), 2231-2242.
[19] J.A. Tropp, I.S. Dhillon, R.W. Heath, and T. Strohmer, Designing structured tight frames via an alternating projection method, IEEE Trans. Inf. Theory, 51:1(2005), 188-209.
[20] W. Wang, J. Wang, Y. Wang, and Z. Zhang, A coherence theory of nonconvex block-sparse compressed sensing, Sci. China, 46:3(2016), 376-390.
[21] 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.
[22] Z. Wang, A.C. Bovik, H.R. Sheikh, and E.P. Simoncelli, Image quality assessment: From error visibility to structural similarity, IEEE Trans. Image Process., 13:4(2004), 600-612.
[23] L. Welch, Lower bounds on the maximum cross correlation of signals, IEEE Trans. Inf. Theory, 20:3(1974), 397-399.
[24] F. Wen, P. Liu, Y. Liu, R. Qiu, and W. Yu, Robust sparse recovery in impulsive noise via ℓp-ℓ1 optimization, IEEE Trans. Signal Process., 65:1(2016), 105-118.
[25] F. Wen, R. Ying, P. Liu, and R. Qiu, Robust PCA using generalized nonconvex regularization, IEEE Trans. Circuits Syst. Video Technol., 30:6(2019), 1497-1510.
[26] J. Wen, J. Weng, C. Tong, C. Ren, and Z. Zhou, Sparse signal recovery with minimization of 1-norm minus 2-norm, IEEE Trans. Veh. Technol., 68:7(2019), 6847-6854.
[27] Z. Xu, Deterministic sampling of sparse trigonometric polynomials, J. Complexity, 27:2(2011), 133-140.
[28] J. Zhang and S. Zhang, Recovery analysis for block ℓp - ℓ1 minimization with prior support information, Int. J. Wavelets Multiresolut. Inf. Process., 20:4(2022), 2150057.
[29] R. Zhang and S. Li, Optimal RIP bounds for sparse signals recovery via ℓp minimization, Appl. Comput. Harmon. Anal., 47:3(2019), 566-584.
[30] Z. Zhou, RIP Analysis for the weighted ℓr -ℓ1 minimization method, Signal Process., 202(2023), 108754.
[31] Z. Zhou and J. Yu, A new nonconvex sparse recovery method for compressive sensing, Front. Appl. Math. Stat., 5(2019), 14.

Funding

The work was supported in part by the National Natural Science Foundation of China (Grant Nos. 12101454, 12101512, 12071380, 62063031), by the Chongqing Normal University Foundation Project (Grant No. 23XLB013), by the Fuxi Scientific Research Innovation Team of Tianshui Normal University (Grant No. FXD2020-03), by the National Natural Science Foundation of China (Grant No. 12301594), by the China Postdoctoral Science Foundation (Grant No. 2021M692681), by the Natural Science Foundation of Chongqing, China (Grant No. cstc2021jcyj-bshX0155), by the Fundamental Research Funds for the Central Universities (Grant No. SWU120078), by the Natural Science Foundation of Gansu Province (Grant No. 21JR1RE292), by the College Teachers Innovation Foundation of Gansu Province (Grant No. 2023B-132), by the Joint Funds of the Natural Science Innovation-driven development of Chongqing (Grant No. 2023NSCQ-LZX0218) and by the Chongqing Talent Project (Grant No. cstc2021ycjh-bgzxm0015).

35

Accesses

0

Citation

Detail
Sections
Recommended

/

〈 〉