[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

k Block Sparse Vector Recovery via Block \(\ell _1-\ell _2\) Minimization

  • Published:
Circuits, Systems, and Signal Processing Aims and scope Submit manuscript

Abstract

In this paper, k block sparse vectors are studied, and the block \(\ell _1-\ell _2\) model is adopted. It is proved theoretically that when the block sparsity satisfies some conditions, the k block sparse vector can be accurately recovered by the noise free block \(\ell _1-\ell _2\) model, and it can also be stably recovered by the noisy block \(\ell _1-\ell _2\) model. In the algorithm, we use the convex difference algorithm, and prove that the aggregation points of the sequence generated by the algorithm converge to the stable point of the objective function. We prove that when the parameter \(\lambda >0\) is less than a certain number \(\lambda _k\), the aggregation points of the sequence generated by the algorithm are block sparse. Finally, we conduct data experiments. The experiments show that when the vector is block sparse, the block \(\ell _1-\ell _2\) model can recover the unknown vector better than the traditional \(\ell _1-\ell _2\) model.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

References

  1. N. Bi, W. Tang, A necessary and sufficient condition for sparse vector recovery via \(\ell _1-\ell _2\) minimization. Appl. Comput. Harmon. Anal. 56, 337–350 (2022)

    Article  MathSciNet  Google Scholar 

  2. N. Bi, J. Tan, W. Tang, A new sufficient condition for sparse vector recovery via \(\ell _1-\ell _2\) local minimization. Anal. Appl. 19(06), 1019–1031 (2021)

    Article  MathSciNet  Google Scholar 

  3. W. Bian, X. Chen, Y. Ye, Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization. Math. Program. 149(1–2), 301–327 (2014)

    MathSciNet  MATH  Google Scholar 

  4. S. Boyd, N. Parikh et al., Distributed optimization and statistical learning via the alternating direction method of multipliers. Found.Trends Mach. Learn. 3(1), 1–122 (2010)

    Article  MATH  Google Scholar 

  5. T. Cai, L. Wang, G. Xu, New bounds for restricted isometry constants 56(9), 4388–4394 (2009)

    Google Scholar 

  6. T. Cai, L. Wang, G. Xu, Shifting inequality and recovery of sparse signals. IEEE Trans. Signal Process. 58(3), 1300–1308 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  7. T. Cai, G. Xu, J. Zhang, On recovery of sparse signals via l1 minimization. IEEE Trans. Inf. Theory 55(7), 3388–3397 (2009)

    Article  MATH  Google Scholar 

  8. E. Candès, Y. Eldar, D. Needell et al., Compressed sensing with coherent and redundant dictionaries. Appl. Comput. Harm. Anal. 31(1), 59–73 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  9. X. Chen, F. Xu, Y. Ye, Lower bound theory of nonzero entries in solutions of l2-lp minimization. SIAM J. Sci. Comput. 32(5), 2832–2852 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  10. D. Donoho, Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Inf. Theory 52(1), 6–18 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  11. Y. Eldar, M. Mishali, Robust recovery of signals from a structured union of subspaces. IEEE Trans. Inf. Theory 55(11), 5302–5316 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  12. S. Foucart, A note on guaranteed sparse recovery via -minimization. Appl. Comput. Harm. Anal. 29(1), 97–103 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  13. S. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing, Applied and Numerical Harmonic Analysis Series (Birkh auser/Springer, New York, 2013)

    MATH  Google Scholar 

  14. S. Foucart, M. Lai, Sparsest solutions of underdetermined linear systems via q-minimization for \(0<q\le 1\). Appl. Comput. Harmon. Anal. 26(3), 395–407 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  15. J. Huang, J. Wang, W. Wang et al., Sharp sufficient condition of block signal recovery via \(l_2/l_1\)-minimization. IET Signal Proc. 13(5), 495–505 (2017)

    Article  Google Scholar 

  16. P. Li, W. Chen, H. Ge, et al., \(\ell _1-\alpha \ell _2\) minimization methods for signal and image reconstruction with impulsive noise removal. Inverse Problems, 36(5), (2020)

  17. Y. Lou, S. Osher, J. Xin, Computational aspects of constrained L1–L2 minimization for compressive sensing. Adv. Intell. Syst. Comput. 359, 169–180 (2015)

    MATH  Google Scholar 

  18. Y. Lou, H. Qi et al., Minimization of l(1–2) for compressed sensing. SIAM J. Sci. Comput. 37(1), A536–A563 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  19. T. Ma, Y. Lou, T. Huang, Truncated \(l_{1-2}\) models for sparse recovery and rank minimization. SIAM J. Imag. Sci. 10(3), 1346–1380 (2017)

    Article  MATH  Google Scholar 

  20. H. Shen, X. Li, L. Zhang, D. Tao, C. Zeng, Compressed sensing-based inpainting of aqua moderate resolution imaging spectroradiometer band 6 using adaptive spectrum-weighted sparse bayesian dictionary learning. IEEE Trans. Geosci. Remote Sens. 52(2), 894–906 (2014)

    Article  Google Scholar 

  21. Y. Shin, D. Xiu, L. Yan, Sparse approximation using l(1)-l(2) minimization and its application to stochastic collocation. SIAM J. Sci. Comput. 39(1), A229–A254 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  22. M. Vehkapera, Y. Kabashima, S. Chatterjee, Analysis of regularized ls reconstruction and random matrix ensembles in compressed sensing, IEEE Int. Symp. Inf. Theory (ISIT), 3185–3189 (2014)

  23. R. Zhang, S. Li, Optimal RIP bounds for sparse signals recovery via p minimization. Appl. Comput. Harmon. Anal. 47(3), 566–584 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  24. X. Zhang, W. Xu, Y. Cui, L. Lu, J. Lin, On recovery of block sparse signals via block compressive sampling matching pursuit. IEEE Access 1(1), 99 (2019)

    Google Scholar 

  25. Y. Zhao, RSP-Based analysis for sparsest and lease \(\ell _1\) norm solutions to underdetermined linear systems. IEEE Trans. Signal Process. 61(22), 5777–5788 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Y. Zhao, Equivalence and strong equivalence between the sparsest and least \(\ell _1\)-norm nonnegative solutions of linear systems and their applications. J. Oper. Res. Soc. China 2(2), 171–193 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  27. C. Zhu, Stable recovery of sparse signals via \(l_p-\)minimization. IEEE Trans. Inf. Theory 54(7), 3364–3367 (2008)

    Article  MATH  Google Scholar 

Download references

Acknowledgements

Kaihao Liang’s work is partially supported by the NSF of Guangdong under Grant No. 2018A0303130136, the Science and Technology Planning Project of Guangdong under Grant No. 2015A070704059 and 2015A030402008.

Author information

Author notes

  1. Shaohua Xie and Kaihao Liang contributed equally to this work.

Authors and Affiliations

  1. School of Mathematics, Sun Yat-Sen University, 135 Xin Gang Xi Lu, Guangzhou, 510275, Guangdong, China

    Shaohua Xie

  2. Department of Mathematics, Zhongkai University of Agriculture and Engineering, No 501, Zhongkai Road, Guangzhou, 510225, Guangdong, China

    Kaihao Liang

Authors
  1. Shaohua Xie
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kaihao Liang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kaihao Liang.

Ethics declarations

Conflict of interest

All data generated or analysed during this study are included in this published article. Research data are not shared. The authors have no relevant financial or non-financial interests to disclose. All authors contributed to the study conception and design. The first draft of the manuscript was written by Shaohua Xie, the corresponding author is Kaihao Liang and all authors commented on previous versions of the manuscript.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Xie, S., Liang, K. k Block Sparse Vector Recovery via Block \(\ell _1-\ell _2\) Minimization. Circuits Syst Signal Process 42, 2897–2915 (2023). https://doi.org/10.1007/s00034-022-02244-8

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00034-022-02244-8

Keywords

Search

Navigation