Skip to main content
SpringerLink
Log in

Fast Block-Sparse Decomposition Based on SL0

  • Conference paper
Latent Variable Analysis and Signal Separation (LVA/ICA 2010)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 6365))

Abstract

In this paper we present a new algorithm based on Smoothed ℓ0 (SL0), called Block SL0 (BSL0), for Under-determined Systems of Linear Equations (USLE) in which the nonzero elements of the unknown vector occur in clusters. Contrary to the previous algorithms such as Block Orthogonal Matching Pursuit (BOMP) and mixed ℓ2/ℓ1 norm, our approach provides a fast algorithm, while providing the same (or better) accuracy. Moreover, we will see experimentally that BSL0 has better performance than SL0, BOMP and mixed ℓ2/ℓ1 norm when the number of nonzero elements of the source vector approaches the upper bound of uniqueness theorem.

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

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. Donoho, D.L.: Compressed sensing. IEEE Trans. Info. Theory 52(4), 1289–1306 (2006)

    Article  MathSciNet  Google Scholar 

  2. Baraniuk, R.G.: Compressive sensing. IEEE Signal Processing Magazine 24(4), 118–124 (2007)

    Article  Google Scholar 

  3. Gribonval, R., Lesage, S.: A survey of sparse component analysis for blind source separation: principles, perspectives, ans new challenges. In: ESANN 2006, pp. 323–330 (April 2006)

    Google Scholar 

  4. Li, Y., Cichocki, A., Amari, S.: Sparse component analysis for blind source separation with less sensors than sources. In: ICA 2003, pp. 89–94 (2003)

    Google Scholar 

  5. Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM Journal on Scientific Computing 20(1), 33–61 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  6. Donoho, D.L., Elad, M., Temlyakov, V.: Stable recovery of sparse overcomplete representations in the presence of noise. IEEE Trans. Info. Theory 52(1), 6–18 (2006)

    Article  MathSciNet  Google Scholar 

  7. Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via l 1 minimization. Proc. Natl. Acad. Sci. 100(5), 2197–2202 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  8. Mohimani, H., Babaie-Zadeh, M., Jutten, C.: A fast approach for overcomplete sparse decomposition based on smoothed ℓ0 norm. IEEE Trans. Signal Processing 57, 289–301 (2009)

    Article  Google Scholar 

  9. Candès, E.J., Romberg, J.K., Tao, T.: Robust uncertainty principles: Exact signal representation from highly incomplete frequency information. IEEE Trans. Info. Theory 52(2), 489–509 (2006)

    Article  Google Scholar 

  10. Mohimani, H., Babaie-Zadeh, M., Gorodnitsky, I., Jutten, C.: Sparse recovery using smoothed ℓ0 (sl0): Convergence analysis. arXiv:cs.IT/1001.5073

    Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  12. Eldar, Y.C., Kuppinger, P., Bölcskei, H.: Compressed sensing of block-sparse signals: Uncertainty relations and efficient recovery. arXiv:cs.IT/0906.3173

    Google Scholar 

  13. Mishali, M., Eldar, Y.C.: Blind multi-band signal reconstruction: Compressed sensing for analog signals. IEEE Trans. Signal Processing 57(3), 993–1009 (2009)

    Article  Google Scholar 

  14. Cotter, S., Rao, B.: Sparse channel estimation via matching pursuit with application to equalization. IEEE Trans. on Comm. (March 2002)

    Google Scholar 

  15. Stojnic, M., Parversh, F., Hassibi, B.: On the reconstruction of block-sparse signals with an optional number of measurements. IEEE Trans. Sig. Proc. (2009)

    Google Scholar 

  16. Majumdar, A., Ward, R.: Fast group sparse classification. In: PACRIM, pp. 11–16 (2009)

    Google Scholar 

  17. Mallat, S., Zhand, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. on Signal proc. 41(12), 3397–3415 (1993)

    Article  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

    Sina Hamidi Ghalehjegh & Massoud Babaie-Zadeh

  2. GIPSA-Lab, Grenoble, and Institut Universitaire de France, France

    Christian Jutten

Authors
  1. Sina Hamidi Ghalehjegh
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Massoud Babaie-Zadeh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Christian Jutten
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Dept. of Electrical Engineering, Universitè d’Evry Val d’Essone, 40 rue du Pelvoux, 91020, Courcouronnes, France

    Vincent Vigneron

  2. Laboratoire I3S, Les Algorithmes - Euclide-B, BP 121, Université de Nice-Sophia Antipolis, 2000 Route des Lucioles, 06903, Sophia Antipolis Cedex, France

    Vicente Zarzoso

  3. School of Engineering, Dept. of Telecommunications, ISITSchool of Engineering, Dept. of Telecommunications, ISITV, Université de Toulon, Avenue George Pompidou, BP 56, La Valette du Var, Cedex, 83162, France

    Eric Moreau

  4. INRIA France, Equipe-projet METISS, Centre de Recherche INRIA Rennes-Bretagne Atlantique, Campus de Beaulieu, 35042, Rennes cedex, France

    Rémi Gribonval

  5. INRIA France, Equipe-projet METISS, Centre de Recherche INRIA Rennes-Bretagne Atlantique, Campus de Beaulieu, 35042, Rennes Cedex, France

    Emmanuel Vincent

Rights and permissions

Reprints and permissions

Copyright information

© 2010 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Hamidi Ghalehjegh, S., Babaie-Zadeh, M., Jutten, C. (2010). Fast Block-Sparse Decomposition Based on SL0. In: Vigneron, V., Zarzoso, V., Moreau, E., Gribonval, R., Vincent, E. (eds) Latent Variable Analysis and Signal Separation. LVA/ICA 2010. Lecture Notes in Computer Science, vol 6365. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15995-4_53

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-15995-4_53

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-15994-7

  • Online ISBN: 978-3-642-15995-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation