Skip to main content
SpringerLink
Log in

Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints

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

Abstract

Regularization of ill-posed linear inverse problems via ℓ 1 penalization has been proposed for cases where the solution is known to be (almost) sparse. One way to obtain the minimizer of such an ℓ 1 penalized functional is via an iterative soft-thresholding algorithm. We propose an alternative implementation to ℓ 1-constraints, using a gradient method, with projection on ℓ 1-balls. The corresponding algorithm uses again iterative soft-thresholding, now with a variable thresholding parameter. We also propose accelerated versions of this iterative method, using ingredients of the (linear) steepest descent method. We prove convergence in norm for one of these projected gradient methods, without and with acceleration.

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

Access this article

Log in via an institution

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. Alber, Y.I., Iusem, A.N., Solodov, M.V.: On the projected subgradient method for nonsmooth convex optimization in a Hilbert space. Math. Program. Ser. A 81(1), 23–35 (1998)

    Article  MathSciNet  Google Scholar 

  2. Anthoine, S.: Different Wavelet-based Approaches for the Separation of Noisy and Blurred Mixtures of Components. Application to Astrophysical Data. Ph.D. Thesis, Princeton University, 2005

  3. Brègman, L.M.: Finding the common point of convex sets by the method of successive projection. Dokl. Akad. Nauk SSSR 162, 487–490 (1965)

    MathSciNet  Google Scholar 

  4. Candès, E.J., Donoho, D.L.: New tight frames of curvelets and optimal representations of objects with piecewise C 2 singularities. Commun. Pure Appl. Math. 57(2), 219–266 (2004)

    Article  MATH  Google Scholar 

  5. Candès, E.J., Romberg, J.: Practical signal recovery from random projections. In: Wavelet Applications in Signal and Image Processing XI. Proc. SPIE Conf., vol. 5914 (2004)

  6. Candès, E.J., Tao, T.: Near-optimal signal recovery from random projections: universal encoding strategies? IEEE Trans. Inf. Theory 52(12), 5406–5425 (2006)

    Article  Google Scholar 

  7. Candès, E., Romberg, J., Tao, T.: Stable signal recovery from incomplete and inaccurate measurements. Commun. Pure Appl. Math. 59(8), 1207–1223 (2006)

    Article  MATH  Google Scholar 

  8. Candès, E.J., Romberg, J., Tao, T.: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006)

    Article  Google Scholar 

  9. Canuto, C., Urban, K.: Adaptive optimization of convex functionals in Banach spaces. SIAM J. Numer. Anal. 42(5), 2043–2075 (2004)

    Article  MathSciNet  Google Scholar 

  10. Chambolle, A., DeVore, R.A., Lee, N.-Y., Lucier, B.J.: Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage. IEEE Trans. Image Process. 7(3), 319–335 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  11. Christensen, O.: An Introduction to Frames and Riesz Bases. Birkhäuser, Boston (2003)

    MATH  Google Scholar 

  12. Cohen, A.: Numerical Analysis of Wavelet Methods. Studies in Mathematics and Its Applications, vol. 32. North-Holland, Amsterdam (2003)

    MATH  Google Scholar 

  13. Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods for elliptic operator equations—Convergence rates. Math. Comput. 70, 27–75 (2001)

    MATH  MathSciNet  Google Scholar 

  14. Cohen, A., Dahmen, W., DeVore, R.: Adaptive wavelet methods II: Beyond the elliptic case. Found. Comput. Math. 2(3), 203–245 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  15. Cohen, A., Hoffmann, M., Reiss, M.: Adaptive wavelet Galerkin methods for linear inverse problems. SIAM J. Numer. Anal. 42(4), 1479–1501 (2004)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  17. Dahlke, S., Maass, P.: An outline of adaptive wavelet Galerkin methods for Tikhonov regularization of inverse parabolic problems. In: Hon, J.-C., et al. (eds.) Recent Development in Theories and Numerics. Proceedings of the International Conference on Inverse Problems, Hong Kong, China, January 9–12 2002, pp. 56–66. World Scientific, Singapore (2003)

    Chapter  Google Scholar 

  18. Dahlke, S., Fornasier, M., Raasch, T.: Adaptive frame methods for elliptic operator equations. Adv. Comput. Math. 27(1), 27–63 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  19. Dahlke, S., Fornasier, M., Raasch, T., Stevenson, R., Werner, M.: Adaptive frame methods for elliptic operator equations: The steepest descent approach. IMA J. Numer. Anal. 27, 717–740 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  20. Daubechies, I.: Ten Lectures on Wavelets. SIAM, Philadelphia (1992)

    MATH  Google Scholar 

  21. Daubechies, I., Teschke, G.: Variational image restoration by means of wavelets: Simultaneous decomposition, deblurring, and denoising. Appl. Comput. Harmon. Anal. 19(1), 1–16 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  22. Daubechies, I., Defrise, M., DeMol, C.: An iterative thresholding algorithm for linear inverse problems. Commun. Pure Appl. Math. 57(11), 1413–1457 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  23. Donoho, D.L.: Superresolution via sparsity constraints. SIAM J. Math. Anal. 23(5), 1309–1331 (1992)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  25. Donoho, D.L.: Nonlinear solution of linear inverse problems by wavelet-vaguelette decomposition. Appl. Comput. Harmon. Anal. 2(2), 101–126 (1995)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  27. Donoho, D.L., Logan, B.F.: Signal recovery and the large sieve. SIAM J. Appl. Math. 52, 577–591 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  28. Donoho, D.L., Starck, P.: Uncertainty principles and signal recovery. SIAM J. Appl. Math. 49, 906–931 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  29. Efron, B., Hastie, T., Johnstone, I., Tibshirani, R.: Least angle regression. Ann. Stat. 32(2), 407–499 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  30. Engl, H.W., Hanke, M., Neubauer, A.: Regularization of Inverse Problems. Mathematics and Its Applications, vol. 375. Kluwer Academic, Dordrecht (1996)

    MATH  Google Scholar 

  31. Figueiredo, M.A.T., Nowak, R.D.: An EM algorithm for wavelet-based image restoration. IEEE Trans. Image Proc. 12(8), 906–916 (2003)

    Article  MathSciNet  Google Scholar 

  32. Figueiredo, M.A.T., Nowak, R.D., Wright, S.J.: Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE J. Sel. Top. Signal Process. 1(4), 586–597 (2007)

    Article  Google Scholar 

  33. Fornasier, M.: Domain decomposition methods for linear inverse problems with sparsity constraints. Inverse Probl. 23, 2505–2526 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  34. Fornasier, M., Pitolli, F.: Adaptive iterative thresholding algorithms for magnetoenceophalography (MEG). J. Comput. Appl. Math. (2008, to appear). doi:10.1016/j.cam.2007.10.048

    MathSciNet  Google Scholar 

  35. Fornasier, M., Rauhut, H.: Iterative thrsholding algorithms. Appl. Comput. Harmon. Anal. 25(2), 187–208 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  36. Fornasier, M., Rauhut, H.: Recovery algorithms for vector valued data with joint sparsity constraints. SIAM J. Numer. Anal. 46(2), 577–613 (2008)

    Article  MathSciNet  Google Scholar 

  37. Logan, B.F.: Properties of High-Pass Signals. Ph.D. Thesis, Columbia University, 1965

  38. Loris, I., Nolet, G., Daubechies, I., Dahlen, F.A.: Tomographic inversion using ℓ 1-norm regularization of wavelet coefficients. Geophys. J. Int. 170(1), 359–370 (2007)

    Article  Google Scholar 

  39. Mallat, S.: A Wavelet Tour of Signal Processing, 2nd edn. Academic Press, San Diego (1999)

    MATH  Google Scholar 

  40. Ramlau, R., Teschke, G.: Tikhonov replacement functionals for iteratively solving nonlinear operator equations. Inverse Probl. 21(5), 1571–1592 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  41. Rauhut, H.: Random sampling of sparse trigonometric polynomials. Appl. Comput. Harmon. Anal. 22(1), 16–42 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  42. Starck, J.-L., Candès, E.J., Donoho, D.L.: Astronomical image representation by curvelet transform. Astron. Astrophys. 298, 785–800 (2003)

    Article  Google Scholar 

  43. Starck, J.-L., Nguyen, M.K., Murtagh, F.: Wavelets and curvelets for image deconvolution: a combined approach. Signal Process. 83, 2279–2283 (2003)

    Article  MATH  Google Scholar 

  44. Teschke, G.: Multi-frame representations in linear inverse problems with mixed multi-constraints. Appl. Comput. Harmon. Anal. 22(1), 43–60 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  45. van den Berg, E., Friedlander, M.P.: In pursuit of a root. Preprint (2007)

  46. Wolfram, S.: The Mathematica Book, 5th edn. Wolfram Media/Cambridge University Press, Cambridge (2003)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Program in Computational and Applied Mathematics, Princeton University, Fine Hall, Washington Road, 08544-1000, Princeton, NJ, USA

    Ingrid Daubechies & Massimo Fornasier

  2. Dienst Theoretische Natuurkunde, Vrije Universiteit Brussel, Pleinlaan 2, 1050, Brussel, Belgium

    Ignace Loris

Authors
  1. Ingrid Daubechies
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Massimo Fornasier
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ignace Loris
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Massimo Fornasier.

Additional information

Communicated by Ronald A. DeVore.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Daubechies, I., Fornasier, M. & Loris, I. Accelerated Projected Gradient Method for Linear Inverse Problems with Sparsity Constraints. J Fourier Anal Appl 14, 764–792 (2008). https://doi.org/10.1007/s00041-008-9039-8

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00041-008-9039-8

Keywords

Mathematics Subject Classification (2000)

Search

Navigation