American Institute of Mathematical Sciences

Advanced
February  2014, 8(1): 149-172. doi: 10.3934/ipi.2014.8.149

Convergence rates for Kaczmarz-type regularization methods

Stefan Kindermann 1, and  Antonio Leitão 2,

1. 

Industrial Mathematics Institute, Johannes Kepler University Linz, A-4040 Linz
2. 

Department of Mathematics, Federal University of St. Catarina, P.O. Box 476, 88040-900 Florianópolis

Received  August 2012 Revised  November 2013 Published  March 2014

This article is devoted to the convergence analysis of a special family of iterative regularization methods for solving systems of ill--posed operator equations in Hilbert spaces, namely Kaczmarz-type methods. The analysis is focused on the Landweber--Kaczmarz (LK) explicit iteration and the iterated Tikhonov--Kaczmarz (iTK) implicit iteration. The corresponding symmetric versions of these iterative methods are also investigated (sLK and siTK). We prove convergence rates for the four methods above, extending and complementing the convergence analysis established originally in [22,13,12,8].
Keywords: Ill-posed systems, regularization., convergence rates, Landweber--Kaczmarz.
Mathematics Subject Classification: Primary: 65J20, 65J15; Secondary: 47J0.
Citation: Stefan Kindermann, Antonio Leitão. Convergence rates for Kaczmarz-type regularization methods. Inverse Problems & Imaging, 2014, 8 (1) : 149-172. doi: 10.3934/ipi.2014.8.149
References:
[1]

P. K. Anh and C. V. Chung, Parallel regularized Newton method for nonlinear ill-posed equations,, Numer. Algorithms, 58 (2011), 379.  doi: 10.1007/s11075-011-9460-y.  Google Scholar

[2]

A. B. Bakushinsky, M. Y. Kokurin and A. Smirnova, Iterative Methods for Ill-Posed Problems,, Walter de Gruyter GmbH & Co. KG, (2011).   Google Scholar

[3]

J. Baumeister, B. Kaltenbacher and A. Leitão, On Levenberg-Marquardt-Kaczmarz iterative methods for solving systems of nonlinear ill-posed equations,, Inverse Probl. Imaging, 4 (2010), 335.  doi: 10.3934/ipi.2010.4.335.  Google Scholar

[4]

H. Bui and Q. Nguyen, Thermomechanical Couplings in Solids,, North-Holland Publishing Co., (1987).   Google Scholar

[5]

M. Burger and B. Kaltenbacher, Regularizing Newton-Kaczmarz methods for nonlinear ill-posed problems,, SIAM J. Numer. Anal., 44 (2006), 153.  doi: 10.1137/040613779.  Google Scholar

[6]

M. Crouzeix, Numerical range and functional calculus in Hilbert space,, J. Funct. Anal., 244 (2007), 668.  doi: 10.1016/j.jfa.2006.10.013.  Google Scholar

[7]

A. De Cezaro, M. Haltmeier, A. Leitão and O. Scherzer, On steepest-descent-Kaczmarz methods for regularizing systems of nonlinear ill-posed equations,, Appl. Math. Comput., 202 (2008), 596.  doi: 10.1016/j.amc.2008.03.010.  Google Scholar

[8]

A. De Cezaro, J. Baumeister and A. Leitão, Modified iterated Tikhonov methods for solving systems of nonlinear ill-posed equations,, Inverse Probl. Imaging, 5 (2011), 1.  doi: 10.3934/ipi.2011.5.1.  Google Scholar

[9]

T. Elfving and T. Nikazad, Properties of a class of block-iterative methods,, Inverse Problems, 25 (2009).  doi: 10.1088/0266-5611/25/11/115011.  Google Scholar

[10]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, vol. 375 of Mathematics and its Applications, (1996).   Google Scholar

[11]

M. Haltmeier, A. Leitão and E. Resmerita, On regularization methods of EM-Kaczmarz type,, Inverse Problems, 25 (2009).  doi: 10.1088/0266-5611/25/7/075008.  Google Scholar

[12]

M. Haltmeier, Convergence analysis of a block iterative version of the loping Landweber-Kaczmarz iteration,, Nonlinear Anal., 71 (2009).  doi: 10.1016/j.na.2009.07.016.  Google Scholar

[13]

M. Haltmeier, R. Kowar, A. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. II. Applications,, Inverse Probl. Imaging, 1 (2007), 507.  doi: 10.3934/ipi.2007.1.507.  Google Scholar

[14]

M. Haltmeier, A. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. I. Convergence analysis,, Inverse Probl. Imaging, 1 (2007), 289.  doi: 10.3934/ipi.2007.1.289.  Google Scholar

[15]

M. Hanke, A. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems,, Numer. Math., 72 (1995), 21.  doi: 10.1007/s002110050158.  Google Scholar

[16]

M. Hanke and W. Niethammer, On the acceleration of Kaczmarz's method for inconsistent linear systems,, Linear Algebra Appl., 130 (1990), 83.  doi: 10.1016/0024-3795(90)90207-S.  Google Scholar

[17]

S. Kaczmarz, Angenäherte Auflösung von Systemen linearer Gleichungen,, Bull. Internat. Acad. Polon. Sci. A, 1937 (1937), 355.   Google Scholar

[18]

B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems,, Walter de Gruyter GmbH & Co. KG, (2008).  doi: 10.1515/9783110208276.  Google Scholar

[19]

N. Kalton, S. Montgomery-Smith, K. Oleszkiewicz and Y. Tomilov, Power-bounded operators and related norm estimates,, J. London Math. Soc. (2), 70 (2004), 463.  doi: 10.1112/S0024610704005514.  Google Scholar

[20]

T. Kato, A generalization of the Heinz inequality,, Proc. Japan Acad., 37 (1961), 305.  doi: 10.3792/pja/1195523678.  Google Scholar

[21]

T. Kato, Perturbation Theory for Linear Operators,, Classics in Mathematics, (1995).   Google Scholar

[22]

R. Kowar and O. Scherzer, Convergence analysis of a Landweber-Kaczmarz method for solving nonlinear ill-posed problems,, in Ill-posed and inverse problems, (2002), 253.   Google Scholar

[23]

Y. Lyubich, Spectral localization, power boundedness and invariant subspaces under Ritt's type condition,, Studia Math., 134 (1999), 153.   Google Scholar

[24]

S. McCormick, An iterative procedure for the solution of constrained nonlinear equations with application to optimization problems,, Numer. Math., 23 (1975), 371.  doi: 10.1007/BF01437037.  Google Scholar

[25]

S. McCormick, The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space,, Indiana Univ. Math. J., 26 (1977), 1137.  doi: 10.1512/iumj.1977.26.26090.  Google Scholar

[26]

K.-H. Meyn, Solution of underdetermined nonlinear equations by stationary iteration methods,, Numer. Math., 42 (1983), 161.  doi: 10.1007/BF01395309.  Google Scholar

[27]

B. Nagy and J. Zemánek, A resolvent condition implying power boundedness,, Studia Math., 134 (1999), 143.   Google Scholar

[28]

M. Z. Nashed, Continuous and semicontinuous analogues of iterative methods of Cimmino and Kaczmarz with applications to the inverse Radon transform,, in Mathematical aspects of computerized tomography (Oberwolfach, (1981), 160.  doi: 10.1007/978-3-642-93157-4_14.  Google Scholar

[29]

F. Natterer, The Mathematics of Computerized Tomography,, SIAM, (2001).  doi: 10.1137/1.9780898719284.  Google Scholar

[30]

F. Natterer and F. Wübbeling, Mathematical Methods in Image Reconstruction,, SIAM Monographs on Mathematical Modeling and Computation, (2001).  doi: 10.1137/1.9780898718324.  Google Scholar

[31]

O. Nevanlinna, Convergence of Iterations for Linear Equations,, Lectures in Mathematics ETH Zürich, (1993).  doi: 10.1007/978-3-0348-8547-8.  Google Scholar

[32]

R. Plato and U. Hämarik, On pseudo-optimal parameter choices and stopping rules for regularization methods in Banach spaces,, Numer. Funct. Anal. Optim., 17 (1996), 181.  doi: 10.1080/01630569608816690.  Google Scholar

[33]

R. Plato, Iterative and Other Methods for Linear Ill-Posed Equations,, Habilitation thesis, (1995).   Google Scholar

[34]

A. Rieder, On the regularization of nonlinear ill-posed problems via inexact Newton iterations,, Inverse Problems, 15 (1999), 309.  doi: 10.1088/0266-5611/15/1/028.  Google Scholar

[35]

O. Scherzer, Convergence criteria of iterative methods based on Landweber iteration for solving nonlinear problems,, J. Math. Anal. Appl., 194 (1995), 911.  doi: 10.1006/jmaa.1995.1335.  Google Scholar

show all references

References:
[1]

P. K. Anh and C. V. Chung, Parallel regularized Newton method for nonlinear ill-posed equations,, Numer. Algorithms, 58 (2011), 379.  doi: 10.1007/s11075-011-9460-y.  Google Scholar

[2]

A. B. Bakushinsky, M. Y. Kokurin and A. Smirnova, Iterative Methods for Ill-Posed Problems,, Walter de Gruyter GmbH & Co. KG, (2011).   Google Scholar

[3]

J. Baumeister, B. Kaltenbacher and A. Leitão, On Levenberg-Marquardt-Kaczmarz iterative methods for solving systems of nonlinear ill-posed equations,, Inverse Probl. Imaging, 4 (2010), 335.  doi: 10.3934/ipi.2010.4.335.  Google Scholar

[4]

H. Bui and Q. Nguyen, Thermomechanical Couplings in Solids,, North-Holland Publishing Co., (1987).   Google Scholar

[5]

M. Burger and B. Kaltenbacher, Regularizing Newton-Kaczmarz methods for nonlinear ill-posed problems,, SIAM J. Numer. Anal., 44 (2006), 153.  doi: 10.1137/040613779.  Google Scholar

[6]

M. Crouzeix, Numerical range and functional calculus in Hilbert space,, J. Funct. Anal., 244 (2007), 668.  doi: 10.1016/j.jfa.2006.10.013.  Google Scholar

[7]

A. De Cezaro, M. Haltmeier, A. Leitão and O. Scherzer, On steepest-descent-Kaczmarz methods for regularizing systems of nonlinear ill-posed equations,, Appl. Math. Comput., 202 (2008), 596.  doi: 10.1016/j.amc.2008.03.010.  Google Scholar

[8]

A. De Cezaro, J. Baumeister and A. Leitão, Modified iterated Tikhonov methods for solving systems of nonlinear ill-posed equations,, Inverse Probl. Imaging, 5 (2011), 1.  doi: 10.3934/ipi.2011.5.1.  Google Scholar

[9]

T. Elfving and T. Nikazad, Properties of a class of block-iterative methods,, Inverse Problems, 25 (2009).  doi: 10.1088/0266-5611/25/11/115011.  Google Scholar

[10]

H. W. Engl, M. Hanke and A. Neubauer, Regularization of Inverse Problems,, vol. 375 of Mathematics and its Applications, (1996).   Google Scholar

[11]

M. Haltmeier, A. Leitão and E. Resmerita, On regularization methods of EM-Kaczmarz type,, Inverse Problems, 25 (2009).  doi: 10.1088/0266-5611/25/7/075008.  Google Scholar

[12]

M. Haltmeier, Convergence analysis of a block iterative version of the loping Landweber-Kaczmarz iteration,, Nonlinear Anal., 71 (2009).  doi: 10.1016/j.na.2009.07.016.  Google Scholar

[13]

M. Haltmeier, R. Kowar, A. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. II. Applications,, Inverse Probl. Imaging, 1 (2007), 507.  doi: 10.3934/ipi.2007.1.507.  Google Scholar

[14]

M. Haltmeier, A. Leitão and O. Scherzer, Kaczmarz methods for regularizing nonlinear ill-posed equations. I. Convergence analysis,, Inverse Probl. Imaging, 1 (2007), 289.  doi: 10.3934/ipi.2007.1.289.  Google Scholar

[15]

M. Hanke, A. Neubauer and O. Scherzer, A convergence analysis of the Landweber iteration for nonlinear ill-posed problems,, Numer. Math., 72 (1995), 21.  doi: 10.1007/s002110050158.  Google Scholar

[16]

M. Hanke and W. Niethammer, On the acceleration of Kaczmarz's method for inconsistent linear systems,, Linear Algebra Appl., 130 (1990), 83.  doi: 10.1016/0024-3795(90)90207-S.  Google Scholar

[17]

S. Kaczmarz, Angenäherte Auflösung von Systemen linearer Gleichungen,, Bull. Internat. Acad. Polon. Sci. A, 1937 (1937), 355.   Google Scholar

[18]

B. Kaltenbacher, A. Neubauer and O. Scherzer, Iterative Regularization Methods for Nonlinear Ill-Posed Problems,, Walter de Gruyter GmbH & Co. KG, (2008).  doi: 10.1515/9783110208276.  Google Scholar

[19]

N. Kalton, S. Montgomery-Smith, K. Oleszkiewicz and Y. Tomilov, Power-bounded operators and related norm estimates,, J. London Math. Soc. (2), 70 (2004), 463.  doi: 10.1112/S0024610704005514.  Google Scholar

[20]

T. Kato, A generalization of the Heinz inequality,, Proc. Japan Acad., 37 (1961), 305.  doi: 10.3792/pja/1195523678.  Google Scholar

[21]

T. Kato, Perturbation Theory for Linear Operators,, Classics in Mathematics, (1995).   Google Scholar

[22]

R. Kowar and O. Scherzer, Convergence analysis of a Landweber-Kaczmarz method for solving nonlinear ill-posed problems,, in Ill-posed and inverse problems, (2002), 253.   Google Scholar

[23]

Y. Lyubich, Spectral localization, power boundedness and invariant subspaces under Ritt's type condition,, Studia Math., 134 (1999), 153.   Google Scholar

[24]

S. McCormick, An iterative procedure for the solution of constrained nonlinear equations with application to optimization problems,, Numer. Math., 23 (1975), 371.  doi: 10.1007/BF01437037.  Google Scholar

[25]

S. McCormick, The methods of Kaczmarz and row orthogonalization for solving linear equations and least squares problems in Hilbert space,, Indiana Univ. Math. J., 26 (1977), 1137.  doi: 10.1512/iumj.1977.26.26090.  Google Scholar

[26]

K.-H. Meyn, Solution of underdetermined nonlinear equations by stationary iteration methods,, Numer. Math., 42 (1983), 161.  doi: 10.1007/BF01395309.  Google Scholar

[27]

B. Nagy and J. Zemánek, A resolvent condition implying power boundedness,, Studia Math., 134 (1999), 143.   Google Scholar

[28]

M. Z. Nashed, Continuous and semicontinuous analogues of iterative methods of Cimmino and Kaczmarz with applications to the inverse Radon transform,, in Mathematical aspects of computerized tomography (Oberwolfach, (1981), 160.  doi: 10.1007/978-3-642-93157-4_14.  Google Scholar

[29]

F. Natterer, The Mathematics of Computerized Tomography,, SIAM, (2001).  doi: 10.1137/1.9780898719284.  Google Scholar

[30]

F. Natterer and F. Wübbeling, Mathematical Methods in Image Reconstruction,, SIAM Monographs on Mathematical Modeling and Computation, (2001).  doi: 10.1137/1.9780898718324.  Google Scholar

[31]

O. Nevanlinna, Convergence of Iterations for Linear Equations,, Lectures in Mathematics ETH Zürich, (1993).  doi: 10.1007/978-3-0348-8547-8.  Google Scholar

[32]

R. Plato and U. Hämarik, On pseudo-optimal parameter choices and stopping rules for regularization methods in Banach spaces,, Numer. Funct. Anal. Optim., 17 (1996), 181.  doi: 10.1080/01630569608816690.  Google Scholar

[33]

R. Plato, Iterative and Other Methods for Linear Ill-Posed Equations,, Habilitation thesis, (1995).   Google Scholar

[34]

A. Rieder, On the regularization of nonlinear ill-posed problems via inexact Newton iterations,, Inverse Problems, 15 (1999), 309.  doi: 10.1088/0266-5611/15/1/028.  Google Scholar

[35]

O. Scherzer, Convergence criteria of iterative methods based on Landweber iteration for solving nonlinear problems,, J. Math. Anal. Appl., 194 (1995), 911.  doi: 10.1006/jmaa.1995.1335.  Google Scholar

[1]

Markus Haltmeier, Antonio Leitão, Otmar Scherzer. Kaczmarz methods for regularizing nonlinear ill-posed equations I: convergence analysis. Inverse Problems & Imaging, 2007, 1 (2) : 289-298. doi: 10.3934/ipi.2007.1.289
[2]

Johann Baumeister, Barbara Kaltenbacher, Antonio Leitão. On Levenberg-Marquardt-Kaczmarz iterative methods for solving systems of nonlinear ill-posed equations. Inverse Problems & Imaging, 2010, 4 (3) : 335-350. doi: 10.3934/ipi.2010.4.335
[3]

Markus Haltmeier, Richard Kowar, Antonio Leitão, Otmar Scherzer. Kaczmarz methods for regularizing nonlinear ill-posed equations II: Applications. Inverse Problems & Imaging, 2007, 1 (3) : 507-523. doi: 10.3934/ipi.2007.1.507
[4]

Guozhi Dong, Bert Jüttler, Otmar Scherzer, Thomas Takacs. Convergence of Tikhonov regularization for solving ill-posed operator equations with solutions defined on surfaces. Inverse Problems & Imaging, 2017, 11 (2) : 221-246. doi: 10.3934/ipi.2017011
[5]

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

Matthew A. Fury. Regularization for ill-posed inhomogeneous evolution problems in a Hilbert space. Conference Publications, 2013, 2013 (special) : 259-272. doi: 10.3934/proc.2013.2013.259
[7]

Felix Lucka, Katharina Proksch, Christoph Brune, Nicolai Bissantz, Martin Burger, Holger Dette, Frank Wübbeling. Risk estimators for choosing regularization parameters in ill-posed problems - properties and limitations. Inverse Problems & Imaging, 2018, 12 (5) : 1121-1155. doi: 10.3934/ipi.2018047
[8]

Adriano De Cezaro, Johann Baumeister, Antonio Leitão. Modified iterated Tikhonov methods for solving systems of nonlinear ill-posed equations. Inverse Problems & Imaging, 2011, 5 (1) : 1-17. doi: 10.3934/ipi.2011.5.1
[9]

Matthew A. Fury. Estimates for solutions of nonautonomous semilinear ill-posed problems. Conference Publications, 2015, 2015 (special) : 479-488. doi: 10.3934/proc.2015.0479
[10]

Paola Favati, Grazia Lotti, Ornella Menchi, Francesco Romani. An inner-outer regularizing method for ill-posed problems. Inverse Problems & Imaging, 2014, 8 (2) : 409-420. doi: 10.3934/ipi.2014.8.409
[11]

Misha Perepelitsa. An ill-posed problem for the Navier-Stokes equations for compressible flows. Discrete & Continuous Dynamical Systems - A, 2010, 26 (2) : 609-623. doi: 10.3934/dcds.2010.26.609
[12]

Youri V. Egorov, Evariste Sanchez-Palencia. Remarks on certain singular perturbations with ill-posed limit in shell theory and elasticity. Discrete & Continuous Dynamical Systems - A, 2011, 31 (4) : 1293-1305. doi: 10.3934/dcds.2011.31.1293
[13]

Olha P. Kupenko, Rosanna Manzo. On optimal controls in coefficients for ill-posed non-Linear elliptic Dirichlet boundary value problems. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1363-1393. doi: 10.3934/dcdsb.2018155
[14]

Sergiy Zhuk. Inverse problems for linear ill-posed differential-algebraic equations with uncertain parameters. Conference Publications, 2011, 2011 (Special) : 1467-1476. doi: 10.3934/proc.2011.2011.1467
[15]

Alfredo Lorenzi, Luca Lorenzi. A strongly ill-posed integrodifferential singular parabolic problem in the unit cube of $\mathbb{R}^n$. Evolution Equations & Control Theory, 2014, 3 (3) : 499-524. doi: 10.3934/eect.2014.3.499
[16]

Faker Ben Belgacem. Uniqueness for an ill-posed reaction-dispersion model. Application to organic pollution in stream-waters. Inverse Problems & Imaging, 2012, 6 (2) : 163-181. doi: 10.3934/ipi.2012.6.163
[17]

Lianwang Deng. Local integral manifolds for nonautonomous and ill-posed equations with sectorially dichotomous operator. Communications on Pure & Applied Analysis, 2020, 19 (1) : 145-174. doi: 10.3934/cpaa.2020009
[18]

Eliane Bécache, Laurent Bourgeois, Lucas Franceschini, Jérémi Dardé. Application of mixed formulations of quasi-reversibility to solve ill-posed problems for heat and wave equations: The 1D case. Inverse Problems & Imaging, 2015, 9 (4) : 971-1002. doi: 10.3934/ipi.2015.9.971
[19]

Peter I. Kogut, Olha P. Kupenko. On optimal control problem for an ill-posed strongly nonlinear elliptic equation with $p$-Laplace operator and $L^1$-type of nonlinearity. Discrete & Continuous Dynamical Systems - B, 2019, 24 (3) : 1273-1295. doi: 10.3934/dcdsb.2019016
[20]

Frank Blume. Minimal rates of entropy convergence for rank one systems. Discrete & Continuous Dynamical Systems - A, 2000, 6 (4) : 773-796. doi: 10.3934/dcds.2000.6.773

2018 Impact Factor: 1.469

Tools

Metrics

  • PDF downloads (22)
  • HTML views (0)
  • Cited by (8)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences