# American Institute of Mathematical Sciences

2014, 8(2): 409-420. doi: 10.3934/ipi.2014.8.409

## An inner-outer regularizing method for ill-posed problems

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

Received  September 2013 Revised  February 2014 Published  May 2014

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.
Citation: 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
##### References:
 [1] M. Bertero and P. Boccacci, Introduction to Inverse Problems in Imaging,, Institute of Physics Publishing, (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. 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: , (): 09. [4] D. A. Girard, A fast ‘Monte-Carlo Cross-Validation' procedure for large least squares problems with noisy data,, Numer. Math., 56 (1989), 1. 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. doi: 10.1080/00401706.1979.10489751. [6] M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems,, Pitman Research Notes in Mathematics, (1995). [7] P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems,, SIAM Monographs on Mathematical Modeling and Computation, (1998). doi: 10.1137/1.9780898719697. [8] P. C. Hansen, Regularization tools,, Numer. Algo., 46 (2007), 189. 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. 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. 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. 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. 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. doi: 10.1137/0714044. [15] Y. Wang, A restarted conjugate gradient method for ill-posed problems,, Acta Mathematicae Applicatae Sinica, 19 (2003), 31. 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. 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. doi: 10.1080/10556780500140409.

show all references

##### References:
 [1] M. Bertero and P. Boccacci, Introduction to Inverse Problems in Imaging,, Institute of Physics Publishing, (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. 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: , (): 09. [4] D. A. Girard, A fast ‘Monte-Carlo Cross-Validation' procedure for large least squares problems with noisy data,, Numer. Math., 56 (1989), 1. 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. doi: 10.1080/00401706.1979.10489751. [6] M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems,, Pitman Research Notes in Mathematics, (1995). [7] P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems,, SIAM Monographs on Mathematical Modeling and Computation, (1998). doi: 10.1137/1.9780898719697. [8] P. C. Hansen, Regularization tools,, Numer. Algo., 46 (2007), 189. 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. 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. 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. 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. 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. doi: 10.1137/0714044. [15] Y. Wang, A restarted conjugate gradient method for ill-posed problems,, Acta Mathematicae Applicatae Sinica, 19 (2003), 31. 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. 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. doi: 10.1080/10556780500140409.

2017 Impact Factor: 1.465