An inner-outer regularizing method for ill-posed problems

Paola Favati; Grazia Lotti; Ornella Menchi; Francesco Romani

doi:10.3934/ipi.2014.8.409

Article Contents

2014, Volume 8, Issue 2: 409-420. Doi: 10.3934/ipi.2014.8.409

This issue Previous Article A variational algorithm for the detection of line segments Next Article Compressive optical deflectometric tomography: A constrained total-variation minimization approach

An inner-outer regularizing method for ill-posed problems

1.
IIT - CNR Via G. Moruzzi 1, 56124 Pisa
2.
Dipart. di Matematica e Informatica, University of Parma, Viale G. Usberti 53/A, 43100 Parma
3.
Dipart. di Informatica, University of Pisa, Largo B. Pontecorvo 3, 56127 Pisa

Received: September 2013

Revised: February 2014

Published: May 2014

Abstract / Introduction Related Papers Cited by

Abstract

Conjugate Gradient is widely used as a regularizing technique for solving linear systems with ill-conditioned coefficient matrix and right-hand side vector perturbed by noise. It enjoys a good convergence rate and computes quickly an iterate, say $x_{k_{opt}}$, which minimizes the error with respect to the exact solution. This behavior can be a disadvantage in the regularization context, because also the high-frequency components of the noise enter quickly the computed solution, leading to a difficult detection of $k_{opt}$ and to a sharp increase of the error after the $k_{opt}$th iteration. In this paper we propose an inner-outer algorithm based on a sequence of restarted Conjugate Gradients, with the aim of overcoming this drawback. A numerical experimentation validates the effectiveness of the proposed algorithm.

Keywords:

Mathematics Subject Classification: 65F22, 65F10.

Citation:

Related Papers

Cited by

References

[1]	M. Bertero and P. Boccacci, Introduction to Inverse Problems in Imaging, Institute of Physics Publishing, Bristol, 1998.doi: 10.1887/0750304359.
[2]	B. Eicke, A. K. Louis and R. Plato, The instability of some gradient methods for ill-posed problems, Numer. Math., 58 (1990), 129-134.doi: 10.1007/BF01385614.
[3]	P. Favati, G. Lotti, O. Menchi and F. Romani, Generalized Cross-Validation Applied to Conjugate Gradient for Discrete Ill-Posed Problems, Technical Report IIT TR-09/2013. Available from: http://www.iit.cnr.it/sites/default/files/TR-09-2013.pdf
[4]	D. A. Girard, A fast ‘Monte-Carlo Cross-Validation' procedure for large least squares problems with noisy data, Numer. Math., 56 (1989), 1-23.doi: 10.1007/BF01395775.
[5]	G. H. Golub, M. Heath and G. Wahba, Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21 (1979), 215-223.doi: 10.1080/00401706.1979.10489751.
[6]	M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems, Pitman Research Notes in Mathematics, Longman, Harlow, 1995.
[7]	P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems, SIAM Monographs on Mathematical Modeling and Computation, Philadelphia, 1998.doi: 10.1137/1.9780898719697.
[8]	P. C. Hansen, Regularization tools, Numer. Algo., 46 (2007), 189-194.doi: 10.1007/s11075-007-9136-9.
[9]	B. Jin, Y. Zhao and J. Zou, Iterative parameter choice by discrepancy principle, IMA J. Numer. Anal., 32 (2012), 1714-1732.doi: 10.1093/imanum/drr051.
[10]	K. Kunisch and J. Zou, Iterative choices of regularization parameters in linear inverse problems, Inverse Problems, 14 (1998), 1247-1264.doi: 10.1088/0266-5611/14/5/010.
[11]	R. Plato, Optimal algorithms for linear ill-posed problems yield regularization methods, Num. Funct. Anal. and Optimiz., 11 (1990), 111-118.doi: 10.1080/01630569008816364.
[12]	R. J. Santos and A. R. De Pierro, The effect of the nonlinearity on GCV applied to Conjugate Gradients in computerized tomography, Comput. Appl. Math., 25 (2006), 111-128.doi: 10.1590/S0101-82052006000100006.
[13]	C. Vogel, Computational Methods for Inverse Problems, SIAM Frontier in Applied Mathematics, Philadelphia, 2002.doi: 10.1137/1.9780898717570.
[14]	G. Wahba, Practical approximate solutions to linear operator equations when the data are noisy, SIAM J. Numer. Anal., 14 (1977), 651-667.doi: 10.1137/0714044.
[15]	Y. Wang, A restarted conjugate gradient method for ill-posed problems, Acta Mathematicae Applicatae Sinica, English Series, 19 (2003), 31-40.doi: 10.1007/s10255-003-0078-2.
[16]	J. Xie and J. Zou, An improved model function method for choosing regularization parameters in linear inverse problems, Inverse Problems, 18 (2002), 631-643.doi: 10.1088/0266-5611/18/3/307.
[17]	F. Zama and E. Loli Piccolomini, A descent method for regularization of ill-posed problems, Optimization Methods and Software, 20 (2005), 615-628.doi: 10.1080/10556780500140409.