Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Iterative Thresholding for Sparse Approximations

  • Published:
Journal of Fourier Analysis and Applications Aims and scope Submit manuscript

Abstract

Sparse signal expansions represent or approximate a signal using a small number of elements from a large collection of elementary waveforms. Finding the optimal sparse expansion is known to be NP hard in general and non-optimal strategies such as Matching Pursuit, Orthogonal Matching Pursuit, Basis Pursuit and Basis Pursuit De-noising are often called upon. These methods show good performance in practical situations, however, they do not operate on the ℓ 0 penalised cost functions that are often at the heart of the problem. In this paper we study two iterative algorithms that are minimising the cost functions of interest. Furthermore, each iteration of these strategies has computational complexity similar to a Matching Pursuit iteration, making the methods applicable to many real world problems. However, the optimisation problem is non-convex and the strategies are only guaranteed to find local solutions, so good initialisation becomes paramount. We here study two approaches. The first approach uses the proposed algorithms to refine the solutions found with other methods, replacing the typically used conjugate gradient solver. The second strategy adapts the algorithms and we show on one example that this adaptation can be used to achieve results that lie between those obtained with Matching Pursuit and those found with Orthogonal Matching Pursuit, while retaining the computational complexity of the Matching Pursuit algorithm.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Donoho, D.L., Vetterli, M., DeVore, R.A., Daubechies, I.: Data compression and harmonic analysis. IEEE Trans. Inf. Theory 44, 2435–2476 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  2. Mallat, S., Falzon, F.: Analysis of low bit rate image transform coding. IEEE Trans. Signal Process. 46, 1027–1042 (1998)

    Article  Google Scholar 

  3. Donoho, D.L.: De-noising by soft-thresholding. IEEE Trans. Inf. Theory 41(3), 613–627 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  4. Davies, M., Mitianoudis, N.: A simple mixture model for sparse overcomplete ICA. IEE Proc. Vis. Image Signal Process. 151, 35–43 (2004)

    Article  Google Scholar 

  5. Blumensath, T., Davies, M.: Sparse and shift-invariant representations of music. IEEE Trans. Audio, Speech Lang. Process. 14, 50–57 (2006)

    Article  Google Scholar 

  6. Donoho, D.L., Elad, M.: Optimally-sparse representation in general (non-orthogonal) dictionaries via l1 minimization. Proc. Natt. Acad. Sci. 100, 2197–2202 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  7. Tropp, J.: Just relax: Convex programming methods for identifying sparse signals in noise. IEEE Trans. Inf. Theory 51(3), 1031–1051 (2006)

    MathSciNet  Google Scholar 

  8. Mallat, S.: A Wavelet Tour of Signal Processing. Academic, New York (1999)

    MATH  Google Scholar 

  9. Davis, G.: Adaptive nonlinear approximations. PhD thesis, New York University (1994)

  10. Natarajan, B.K.: Sparse approximate solutions to linear systems. SIAM J. Comput. 24, 227–234 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  11. Mallat, S., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Signal Process. 41(12), 3397–3415 (1993)

    Article  MATH  Google Scholar 

  12. Tropp, J.A.: Greed is good: algorithmic results for sparse approximation. IEEE Trans. Inf. Theory 50(10), 2231–2242 (2004)

    Article  MathSciNet  Google Scholar 

  13. Gribonval, R., Vandergheynst, P.: On the exponential convergence of matching pursuits in quasi-incoherent dictionaries. IEEE Trans. Inf. Theory 52(1), 255–261 (2006)

    Article  MathSciNet  Google Scholar 

  14. Murray, J.F., Kreutz-Delgado, K.: An improved FOCUSS-based learning algorithm for solving sparse linear inverse problems. In: Conf. Record of the Thirty-Fifth Asilomar Conf. on Signals, Systems and Computers, pp. 347–351 (2001)

  15. Chen, S.S., Donoho, D.L., Saunders, M.A.: Atomic decomposition by basis pursuit. SIAM J. Sci. Comput. 20(1), 33–61 (1998)

    Article  MathSciNet  Google Scholar 

  16. Daubechies, I., Defries, M., De Mol, C.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1457 (2004)

    Article  MATH  Google Scholar 

  17. Bect, J., Blanc Féraud, L., Aubert, G., Chambolle, A.: In: A l1-Unified Variational Framework for Image Restoration. Lecture Notes in Computer Sciences, vol. 3024, pp. 1–13. Springer, New York (2004)

    Google Scholar 

  18. Elad, M.: Why simple shrinkage is still relevant for redundant representation. IEEE Trans. Inf. Theory 52(12), 5559–5569 (2006)

    Article  MathSciNet  Google Scholar 

  19. Elad, M., Matalon, B., Zibulevsky, M.: Coordinate and subspace optimization methods for linear least squares with non-quadratic regularization. Appl. Comput. Harmon. Anal. 23, 346–367 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  20. Candès, E., Romberg, J.: Practical signal recovery from random projections. In: Proc. SPIE Conf., Wavelet Applications in Signal and Image Processing XI, Jan. 2005

  21. Bredies, K., Lorenz, D.A.: Iterated hard shrinkage for minimization problems with sparsity constraints (2006)

  22. Kingsbury, N.G.: Complex wavelets for shift invariant analysis and filtering of signals. J. Appl. Comput. Harmon. Anal. 10, 234–253 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  23. Herrity, K.K., Gilbert, A.C., Tropp, J.A.: Sparse approximation via iterative thresholding. In: Proceedings of the Int. Conf. on Acoustics, Speech and Signal Processing, 2006

  24. Nowak, R., Figueiredo, M.: Fast wavelet-based image deconvolution using the EM algorithm. In: Proceedings of the 35th Asilomar Conference on Signals, Systems, and Computers, (Monterey), November 2001

  25. Figueiredo, M., Nowak, R.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Process. 12(8), 906–916 (2003)

    Article  MathSciNet  Google Scholar 

  26. Starck, J., Nguyen, M., Murtagh, F.: Wavelet and curvelet for image deconvolution: A combined approach. J. Signal Process. 83(10), 2279–2283 (2003)

    Article  MATH  Google Scholar 

  27. Elad, M., Matalon, B., Shtok, J., Zibulevsky, M.: A wide-angle view at iterated shrinkage algorithms. In: SPIE (Wavelet XII) (San-Diego, CA, USA), August 2007

  28. Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. SIAM J. Multiscale Model. Simul. 4, 1168–1200 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  29. Lange, K., Hunter, D.R., Yang, I.: Optimization transfer using surrogate objective functions. J. Comput. Graph. Stat. 9, 1–20 (2006)

    Article  MathSciNet  Google Scholar 

  30. Lange, K.: Optimization. Springer, New York (2004)

    MATH  Google Scholar 

  31. Landweber, L.: An iterative formula for Fredholm integrals of the first kind. Am. J. Math. 73, 615–624 (1951)

    Article  MATH  MathSciNet  Google Scholar 

  32. Kingsbury, N.G., Reeves, T.H.: Iterative image coding with overcomplete complex wavelet transforms. In: Proc. Conf. on Visual Communications and Image Processing, 2003

  33. Donoho, D., Tsaig, Y., Drori, I., Starck, J.: Sparse solutions of underdetermined linear equations by stagewise orthogonal matching pursuit (2006)

  34. Krustulovic, S., Gribonval, R.: MPTK: Matching pursuit made tractable. In: Proc. Int. Conf. on Acoustic Speech and Signal Processing (Toulouse, France), May 2006

  35. Rudin, W.: Principles of Mathematical Analysis. McGraw-Hill, New York (1976)

    MATH  Google Scholar 

  36. Horn, R.A., Johnson, C.R.: Matrix Analysis. Cambridge University Press, Cambridge (1985)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. IDCOM & Joint Research Institute for Signal and Image Processing, The University of Edinburgh, King’s Buildings, Mayfield Road, Edinburgh, EH9 3JL, UK

    Thomas Blumensath & Mike E. Davies

Authors
  1. Thomas Blumensath
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mike E. Davies
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Thomas Blumensath.

Additional information

Communicated by Michael Elad.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Blumensath, T., Davies, M.E. Iterative Thresholding for Sparse Approximations. J Fourier Anal Appl 14, 629–654 (2008). https://doi.org/10.1007/s00041-008-9035-z

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00041-008-9035-z

Keywords

Mathematics Subject Classification (2000)

Search

Navigation