Skip to main content
Springer Nature Link
Log in

An analysis of a multi-level projected steepest descent iteration for nonlinear inverse problems in Banach spaces subject to stability constraints

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

We consider nonlinear inverse problems described by operator equations in Banach spaces. Assuming conditional stability of the inverse problem, that is, assuming that stability holds on a compact, convex subset of the domain of the operator, we introduce a novel nonlinear projected steepest descent iteration and analyze its convergence to an approximate solution given limited accuracy data. We proceed with developing a multi-level algorithm based on a nested family of compact, convex subsets on which stability holds and the stability constants are ordered. Growth of the stability constants is coupled to the increase in accuracy of approximation between neighboring levels to ensure that the algorithm can continue from level to level until the iterate satisfies a desired discrepancy criterion, after a finite number of steps.

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

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Alber, Y.I., Butnariu, D.: Convergence of Bregman projection methods for solving consistent convex feasibility problems in reflexive Banach spaces. J. Optim. Theory Appl. 92, 33–61 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  2. Alber, Y.I., Kartsatos, A.G., Litsyn, E.: Iterative solution of unstable variational inequalities on approximately given sets. Abstr. Appl. Anal. 1(1), 45–64 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  3. Alessandrini, G., Vessella, S.: Lipschitz stability for the inverse conductivity problem. Adv. Appl. Math. 35(2), 207–241 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  4. Ammari, H., Bahouri, H., Dos Santos Ferreira, D., Gallagher, I.: Stability estimates for an inverse scattering problem at high frequencies. ArXiv e-prints (2012)

  5. Beretta, E., de Hoop, M.V., Qiu, L.: Lipschitz stability of an inverse boundary value problem for a Schrödinger-type equation. SIAM J. Math. Anal. 45(2), 679–699 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  6. Beretta, E., Francini, E.: Lipschitz stability for the electrical impedance tomography problem: the complex case. Commun. Partial Differ. Equ. 36(10), 1723–1749 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  7. Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7(3), 200–217 (1967)

    Article  Google Scholar 

  8. Butnariu, D., Iusem, A.N., Resmerita, E.: Total convexity for powers of the norm in uniformly convex Banach spaces. J. Convex Anal. 7(2), 319–334 (2000)

    MATH  MathSciNet  Google Scholar 

  9. Chavent, G., Kunisch, K.: On weakly nonlinear inverse problems. SIAM. J. Appl. Math. 56(2), 542–572 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  10. Cioranescu, I.: Geometry of Banach Spaces, Duality Mappings and Nonlinear Problems. Mathematics and Its Applications, vol. 62. Kluwer Academic Publishers Group, Dordrecht (1990)

  11. Daubechies, I., Fornasier, M., Loris, I.: Accelerated projected gradient method for linear inverse problems with sparsity constraints. J. Fourier Anal. Appl. 14(5–6), 764–792 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  12. de Hoop, M.V., Qiu, L., Scherzer, O.: Local analysis of inverse problems: Hölder stability and iterative reconstruction. Inverse Probl. 28(4), 045001 (2012)

    Article  Google Scholar 

  13. Eicke, B.: Iteration methods for convexly constrained ill-posed problems in Hilbert space. Numer. Funct. Anal. Optim. 13(5–6), 413–429 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  14. Gilyazov, S.F.: Iterative solution methods for inconsistent linear equations with nonself-adjoint operator. Moscow Univ. Comput. Math. Cybernet. 13, 8–13 (1977)

    Google Scholar 

  15. Hanke, M.: Accelerated Landweber iterations for the solution of ill-posed equations. Numer. Math. 60(3), 341–373 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  16. Kaltenbacher, B.: Toward global convergence for strongly nonlinear ill-posed problems via a regularizing multilevel approach. Numer. Funct. Anal. Optim. 27(5–6), 637–665 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  17. Kaltenbacher, B.: Convergence rates of a multilevel method for the regularization of nonlinear ill-posed problems. J. Integral Equ. Appl. 20(2), 201–228 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  18. Kaltenbacher, B., Neubauer, A., Scherzer, O.: Iterative Regularization Methods for Nonlinear Ill-Posed Problems. Radon Series on Computational and Applied Mathematics, vol. 6. Walter de Gruyter GmbH & Co. KG, Berlin (2008)

  19. Mandache, N.: Exponential instability in an inverse problem for the Schrödinger equation. Inverse Probl. 17(5), 1435–1444 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  20. Neubauer, A., Scherzer, O.: A convergence rate result for a steepest descent method and a minimal error method for the solution of nonlinear ill-posed problems. Z. Anal. Anwend. 14(2), 369–377 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  21. Scherzer, O.: A convergence analysis of a method of steepest descent and a two-step algorithm for nonlinear ill-posed problems. Numer. Funct. Anal. Optim. 17(1–2), 197–214 (1996)

    MATH  MathSciNet  Google Scholar 

  22. Scherzer, O.: An iterative multi-level algorithm for solving nonlinear ill-posed problems. Numer. Math. 80(4), 579–600 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  23. Schuster, T., Kaltenbacher, B., Hofmann, B., Kazimierski, K.S.: Regularization Methods in Banach Spaces. Radon Series on Computational and Applied Mathematics, vol. 10. Walter de Gruyter GmbH & Co. KG, Berlin (2012)

  24. Teschke, G., Borries, C.: Accelerated projected steepest descent method for nonlinear inverse problems with sparsity constraints. Inverse Probl. 26(2), 025007 (23 pp) (2010)

    Google Scholar 

  25. Xu, Z.B., Roach, G.F.: Characteristic inequalities of uniformly convex and uniformly smooth Banach spaces. J. Math. Anal. Appl. 157(1), 189–210 (1991)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The research was initiated at the Isaac Newton Institute for Mathematical Sciences (Cambridge, England) during a programme on Inverse Problems in Fall 2011. The authors would like to thank the anonymous referees for their valuable comments and suggestions to improve the quality of the paper.

Author information

Authors and Affiliations

  1. Center for Computational and Applied Mathemematics, Purdue University, West Lafayette, IN, 47907, USA

    Maarten V. de Hoop

  2. Institute for Mathematics and its Applications, University of Minnesota, Minneapolis, MN, 55455, USA

    Lingyun Qiu

  3. Computational Science Center, University of Vienna, Nordbergstr. 15, 1090 , Vienna, Austria

    Otmar Scherzer

Authors
  1. Maarten V. de Hoop
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lingyun Qiu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Otmar Scherzer
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lingyun Qiu.

Additional information

This research was supported in part National Science Foundation grant CMG DMS-1025318 and in part by the members of the Geo-Mathematical Imaging Group at Purdue University. The work of OS has been supported by the Austrian Science Fund (FWF) within the national research networks Photoacoustic Imaging in Biology and Medicine, project S10505 and Geometry and Simulation S11704.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

de Hoop, M.V., Qiu, L. & Scherzer, O. An analysis of a multi-level projected steepest descent iteration for nonlinear inverse problems in Banach spaces subject to stability constraints. Numer. Math. 129, 127–148 (2015). https://doi.org/10.1007/s00211-014-0629-x

Download citation

  • Received:

  • Revised:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-014-0629-x

Mathematics Subject Classification

Search

Navigation