Convergence of the gradient method for ill-posed problems

Previous Article
Non-convex TV denoising corrupted by impulse noise
IPI Home
This Issue
Next Article
Numerical optimization algorithms for wavefront phase retrieval from multiple measurements

August 2017, 11(4): 703-720. doi: 10.3934/ipi.2017033

Convergence of the gradient method for ill-posed problems

Stefan Kindermann ^,

Industrial Mathematics Institute, Johannes Kepler University Linz, Altenbergerstrasse 69,4040 Linz, Austria

Received June 2016 Revised May 2017 Published June 2017

We study the convergence of the gradient descent method for solving ill-posed problems where the solution is characterized as a global minimum of a differentiable functional in a Hilbert space. The classical least-squares functional for nonlinear operator equations is a special instance of this framework, and the gradient method then reduces to Landweber iteration. The main result of this article is a proof of weak and strong convergence under new nonlinearity conditions that generalize the classical tangential cone conditions.

Keywords: Inverse problems, iterative Regularization, Landweber iteration, tangential cone condition, quasiconvexity.

Mathematics Subject Classification: Primary: 65J20, 65J15; Secondary: 47J06.

Citation: Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033

References:

[1]	K. J. Arrow and A. C. Enthoven, Quasi-concave programming, Econometrica, 29 (1961), 779-800. doi: 10.2307/1911819. Google Scholar
[2]	M. Avriel, W. E. Diewert, S. Schaible and I. Zang, Generalized Concavity, vol. 63 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898719437.ch1. Google Scholar
[3]	A. Bakushinsky and A. Goncharsky, Ill-posed Problems: Theory and Applications, vol. 301 of Mathematics and its Applications, Kluwer Academic Publishers Group, Dordrecht, 1994. doi: 10.1007/978-94-011-1026-6. Google Scholar
[4]	A. B. Bakushinsky and M. Y. Kokurin, Iterative Methods for Approximate Solution of Inverse Problems, vol. 577 of Mathematics and Its Applications (New York), Springer, Dordrecht, 2004. Google Scholar
[5]	A. Bakushinsky and A. Smirnova, A posteriori stopping rule for regularized fixed point iterations, Nonlinear Anal., 64 (2006), 1255-1261. doi: 10.1016/j.na.2005.06.031. Google Scholar
[6]	A. Bakushinsky and A. Smirnova, Iterative regularization and generalized discrepancy principle for monotone operator equations, Numer. Funct. Anal. Optim., 28 (2007), 13-25. doi: 10.1080/01630560701190315. Google Scholar
[7]	A. B. Bakushinsky, M. Y. Kokurin and A. Smirnova, Iterative Methods for Ill-Posed Problems, vol. 54 of Inverse and Ill-posed Problems Series, Walter de Gruyter GmbH & Co. KG, Berlin, 2011. Google Scholar
[8]	F. E. Browder and W. V. Petryshyn, Construction of fixed points of nonlinear mappings in Hilbert space, J. Math. Anal. Appl., 20 (1967), 197-228. doi: 10.1016/0022-247X(67)90085-6. Google Scholar
[9]	A. -P. Calderón, On an inverse boundary value problem, in Seminar on Numerical Analysis and its Applications to Continuum Physics (Rio de Janeiro, 1980), Soc. Brasil. Mat., Rio de Janeiro, 1980, 65-73. Google Scholar
[10]	H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, vol. 375 of Mathematics and its Applications, Kluwer, Dordrecht, 1996. doi: 10.1007/978-94-009-1740-8. Google Scholar
[11]	M. Haltmeier, A. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. Ⅰ. Convergence analysis, Inverse Probl. Imaging, 1 (2007), 289-298. doi: 10.3934/ipi.2007.1.289. Google Scholar
[12]	M. Hanke, A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems, Inverse Problems, 13 (1997), 79-95. doi: 10.1088/0266-5611/13/1/007. Google Scholar
[13]	M. Hanke, A. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72 (1995), 21-37. doi: 10.1007/s002110050158. Google Scholar
[14]	T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces Inverse Problems, 26 (2002), Art. 055002, 17 pages. doi: 10.1088/0266-5611/26/5/055002. Google Scholar
[15]	N. S. Hoang and A. G. Ramm, Dynamical systems gradient method for solving nonlinear equations with monotone operators, Acta Appl. Math., 106 (2009), 473-499. doi: 10.1007/s10440-008-9308-1. Google Scholar
[16]	N. S. Hoang and A. G. Ramm, The dynamical systems method for solving nonlinear equations with monotone operators, Asian-Eur. J. Math., 3 (2010), 57-105. doi: 10.1142/S1793557110000064. Google Scholar
[17]	Q. Jin, A general convergence analysis of some Newton-type methods for nonlinear inverse problems, SIAM J. Numer. Anal., 49 (2011), 549-573. doi: 10.1137/100804231. Google Scholar
[18]	B. Kaltenbacher, Some Newton-type methods for the regularization of nonlinear ill-posed problems, Inverse Problems, 13 (1997), 729-753. doi: 10.1088/0266-5611/13/3/012. Google Scholar
[19]	B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems, vol. 6 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. doi: 10.1515/9783110208276. Google Scholar
[20]	A. Neubauer, On Landweber iteration for nonlinear ill-posed problems in Hilbert scales, Numer. Math., 85 (2000), 309-328. doi: 10.1007/s002110050487. Google Scholar
[21]	A. Neubauer, Some generalizations for Landweber iteration for nonlinear ill-posed problems, Journal Inverse and Ill-posed Problems, 24 (2016), 393-406. doi: 10.1515/jiip-2015-0086. Google Scholar
[22]	S. S. Pereverzyev, R. Pinnau and N. Siedow, Regularized fixed-point iterations for nonlinear inverse problems, Inverse Problems, 22 (2006), 1-22. doi: 10.1088/0266-5611/22/1/001. Google Scholar
[23]	A. G. Ramm, Dynamical systems method for ill-posed equations with monotone operators, Commun. Nonlinear Sci. Numer. Simul., 10 (2005), 935-940. doi: 10.1016/j.cnsns.2003.07.002. Google Scholar
[24]	O. Scherzer, Convergence criteria of iterative methods based on Landweber iteration for solving nonlinear problems, J. Math. Anal. Appl., 194 (1995), 911-933. doi: 10.1006/jmaa.1995.1335. Google Scholar
[25]	T. Schuster, B. Kaltenbacher, B. Hofmann and K. S. Kazimierski, Regularization Methods in Banach Spaces, vol. 10 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2012. doi: 10.1515/9783110255720. Google Scholar
[26]	V. V. Vasin, Convergence of gradient-type methods for nonlinear equations, Dokl. Akad. Nauk, 359 (1998), 7-9. Google Scholar

show all references

References:

[1]	K. J. Arrow and A. C. Enthoven, Quasi-concave programming, Econometrica, 29 (1961), 779-800. doi: 10.2307/1911819. Google Scholar
[2]	M. Avriel, W. E. Diewert, S. Schaible and I. Zang, Generalized Concavity, vol. 63 of Classics in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2010. doi: 10.1137/1.9780898719437.ch1. Google Scholar
[3]	A. Bakushinsky and A. Goncharsky, Ill-posed Problems: Theory and Applications, vol. 301 of Mathematics and its Applications, Kluwer Academic Publishers Group, Dordrecht, 1994. doi: 10.1007/978-94-011-1026-6. Google Scholar
[4]	A. B. Bakushinsky and M. Y. Kokurin, Iterative Methods for Approximate Solution of Inverse Problems, vol. 577 of Mathematics and Its Applications (New York), Springer, Dordrecht, 2004. Google Scholar
[5]	A. Bakushinsky and A. Smirnova, A posteriori stopping rule for regularized fixed point iterations, Nonlinear Anal., 64 (2006), 1255-1261. doi: 10.1016/j.na.2005.06.031. Google Scholar
[6]	A. Bakushinsky and A. Smirnova, Iterative regularization and generalized discrepancy principle for monotone operator equations, Numer. Funct. Anal. Optim., 28 (2007), 13-25. doi: 10.1080/01630560701190315. Google Scholar
[7]	A. B. Bakushinsky, M. Y. Kokurin and A. Smirnova, Iterative Methods for Ill-Posed Problems, vol. 54 of Inverse and Ill-posed Problems Series, Walter de Gruyter GmbH & Co. KG, Berlin, 2011. Google Scholar
[8]	F. E. Browder and W. V. Petryshyn, Construction of fixed points of nonlinear mappings in Hilbert space, J. Math. Anal. Appl., 20 (1967), 197-228. doi: 10.1016/0022-247X(67)90085-6. Google Scholar
[9]	A. -P. Calderón, On an inverse boundary value problem, in Seminar on Numerical Analysis and its Applications to Continuum Physics (Rio de Janeiro, 1980), Soc. Brasil. Mat., Rio de Janeiro, 1980, 65-73. Google Scholar
[10]	H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems, vol. 375 of Mathematics and its Applications, Kluwer, Dordrecht, 1996. doi: 10.1007/978-94-009-1740-8. Google Scholar
[11]	M. Haltmeier, A. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. Ⅰ. Convergence analysis, Inverse Probl. Imaging, 1 (2007), 289-298. doi: 10.3934/ipi.2007.1.289. Google Scholar
[12]	M. Hanke, A regularizing Levenberg-Marquardt scheme, with applications to inverse groundwater filtration problems, Inverse Problems, 13 (1997), 79-95. doi: 10.1088/0266-5611/13/1/007. Google Scholar
[13]	M. Hanke, A. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems, Numer. Math., 72 (1995), 21-37. doi: 10.1007/s002110050158. Google Scholar
[14]	T. Hein and K. S. Kazimierski, Accelerated Landweber iteration in Banach spaces Inverse Problems, 26 (2002), Art. 055002, 17 pages. doi: 10.1088/0266-5611/26/5/055002. Google Scholar
[15]	N. S. Hoang and A. G. Ramm, Dynamical systems gradient method for solving nonlinear equations with monotone operators, Acta Appl. Math., 106 (2009), 473-499. doi: 10.1007/s10440-008-9308-1. Google Scholar
[16]	N. S. Hoang and A. G. Ramm, The dynamical systems method for solving nonlinear equations with monotone operators, Asian-Eur. J. Math., 3 (2010), 57-105. doi: 10.1142/S1793557110000064. Google Scholar
[17]	Q. Jin, A general convergence analysis of some Newton-type methods for nonlinear inverse problems, SIAM J. Numer. Anal., 49 (2011), 549-573. doi: 10.1137/100804231. Google Scholar
[18]	B. Kaltenbacher, Some Newton-type methods for the regularization of nonlinear ill-posed problems, Inverse Problems, 13 (1997), 729-753. doi: 10.1088/0266-5611/13/3/012. Google Scholar
[19]	B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems, vol. 6 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2008. doi: 10.1515/9783110208276. Google Scholar
[20]	A. Neubauer, On Landweber iteration for nonlinear ill-posed problems in Hilbert scales, Numer. Math., 85 (2000), 309-328. doi: 10.1007/s002110050487. Google Scholar
[21]	A. Neubauer, Some generalizations for Landweber iteration for nonlinear ill-posed problems, Journal Inverse and Ill-posed Problems, 24 (2016), 393-406. doi: 10.1515/jiip-2015-0086. Google Scholar
[22]	S. S. Pereverzyev, R. Pinnau and N. Siedow, Regularized fixed-point iterations for nonlinear inverse problems, Inverse Problems, 22 (2006), 1-22. doi: 10.1088/0266-5611/22/1/001. Google Scholar
[23]	A. G. Ramm, Dynamical systems method for ill-posed equations with monotone operators, Commun. Nonlinear Sci. Numer. Simul., 10 (2005), 935-940. doi: 10.1016/j.cnsns.2003.07.002. Google Scholar
[24]	O. Scherzer, Convergence criteria of iterative methods based on Landweber iteration for solving nonlinear problems, J. Math. Anal. Appl., 194 (1995), 911-933. doi: 10.1006/jmaa.1995.1335. Google Scholar
[25]	T. Schuster, B. Kaltenbacher, B. Hofmann and K. S. Kazimierski, Regularization Methods in Banach Spaces, vol. 10 of Radon Series on Computational and Applied Mathematics, Walter de Gruyter GmbH & Co. KG, Berlin, 2012. doi: 10.1515/9783110255720. Google Scholar
[26]	V. V. Vasin, Convergence of gradient-type methods for nonlinear equations, Dokl. Akad. Nauk, 359 (1998), 7-9. Google Scholar

[1]	Plamen Stefanov, Yang Yang. Multiwave tomography with reflectors: Landweber's iteration. Inverse Problems & Imaging, 2017, 11 (2) : 373-401. doi: 10.3934/ipi.2017018
[2]	David Maxwell. Kozlov-Maz'ya iteration as a form of Landweber iteration. Inverse Problems & Imaging, 2014, 8 (2) : 537-560. doi: 10.3934/ipi.2014.8.537
[3]	Kenrick Bingham, Yaroslav Kurylev, Matti Lassas, Samuli Siltanen. Iterative time-reversal control for inverse problems. Inverse Problems & Imaging, 2008, 2 (1) : 63-81. doi: 10.3934/ipi.2008.2.63
[4]	Gabriel Peyré, Sébastien Bougleux, Laurent Cohen. Non-local regularization of inverse problems. Inverse Problems & Imaging, 2011, 5 (2) : 511-530. doi: 10.3934/ipi.2011.5.511
[5]	Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[6]	Barbara Kaltenbacher, Ivan Tomba. Enhanced choice of the parameters in an iteratively regularized Newton-Landweber iteration in Banach space. Conference Publications, 2015, 2015 (special) : 686-695. doi: 10.3934/proc.2015.0686
[7]	Bernadette N. Hahn. Dynamic linear inverse problems with moderate movements of the object: Ill-posedness and regularization. Inverse Problems & Imaging, 2015, 9 (2) : 395-413. doi: 10.3934/ipi.2015.9.395
[8]	Thorsten Hohage, Mihaela Pricop. Nonlinear Tikhonov regularization in Hilbert scales for inverse boundary value problems with random noise. Inverse Problems & Imaging, 2008, 2 (2) : 271-290. doi: 10.3934/ipi.2008.2.271
[9]	Alina Toma, Bruno Sixou, Françoise Peyrin. Iterative choice of the optimal regularization parameter in TV image restoration. Inverse Problems & Imaging, 2015, 9 (4) : 1171-1191. doi: 10.3934/ipi.2015.9.1171
[10]	Luca Rondi. On the regularization of the inverse conductivity problem with discontinuous conductivities. Inverse Problems & Imaging, 2008, 2 (3) : 397-409. doi: 10.3934/ipi.2008.2.397
[11]	Xin-He Miao, Jein-Shan Chen. Error bounds for symmetric cone complementarity problems. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 627-641. doi: 10.3934/naco.2013.3.627
[12]	Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[13]	Ya-Zheng Dang, Zhong-Hui Xue, Yan Gao, Jun-Xiang Li. Fast self-adaptive regularization iterative algorithm for solving split feasibility problem. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019017
[14]	Colin Guillarmou, Antônio Sá Barreto. Inverse problems for Einstein manifolds. Inverse Problems & Imaging, 2009, 3 (1) : 1-15. doi: 10.3934/ipi.2009.3.1
[15]	Sergei Avdonin, Pavel Kurasov. Inverse problems for quantum trees. Inverse Problems & Imaging, 2008, 2 (1) : 1-21. doi: 10.3934/ipi.2008.2.1
[16]	Maciej Zworski. A remark on inverse problems for resonances. Inverse Problems & Imaging, 2007, 1 (1) : 225-227. doi: 10.3934/ipi.2007.1.225
[17]	Guanghui Hu, Peijun Li, Xiaodong Liu, Yue Zhao. Inverse source problems in electrodynamics. Inverse Problems & Imaging, 2018, 12 (6) : 1411-1428. doi: 10.3934/ipi.2018059
[18]	Michael Herty, Giuseppe Visconti. Kinetic methods for inverse problems. Kinetic & Related Models, 2019, 12 (5) : 1109-1130. doi: 10.3934/krm.2019042
[19]	Johnathan M. Bardsley. A theoretical framework for the regularization of Poisson likelihood estimation problems. Inverse Problems & Imaging, 2010, 4 (1) : 11-17. doi: 10.3934/ipi.2010.4.11
[20]	Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141

American Institute of Mathematical Sciences