# American Institute of Mathematical Sciences

May  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.
 [1] You-Wei Wen, Raymond Honfu Chan. Using generalized cross validation to select regularization parameter for total variation regularization problems. Inverse Problems & Imaging, 2018, 12 (5) : 1103-1120. doi: 10.3934/ipi.2018046 [2] Zhong-Zhi Bai. On convergence of the inner-outer iteration method for computing PageRank. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855 [3] Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial & Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739 [4] Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595 [5] Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial & Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415 [6] Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034 [7] El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883 [8] Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control & Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863 [9] Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157 [10] Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial & Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565 [11] Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-16. doi: 10.3934/jimo.2019013 [12] Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389 [13] Yuhong Dai, Ya-xiang Yuan. Analysis of monotone gradient methods. Journal of Industrial & Management Optimization, 2005, 1 (2) : 181-192. doi: 10.3934/jimo.2005.1.181 [14] Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791 [15] C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193 [16] Nam-Yong Lee, Bradley J. Lucier. Preconditioned conjugate gradient method for boundary artifact-free image deblurring. Inverse Problems & Imaging, 2016, 10 (1) : 195-225. doi: 10.3934/ipi.2016.10.195 [17] Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025 [18] 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 [19] Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics & Games, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020 [20] Xiangtuan Xiong, Jinmei Li, Jin Wen. Some novel linear regularization methods for a deblurring problem. Inverse Problems & Imaging, 2017, 11 (2) : 403-426. doi: 10.3934/ipi.2017019

2017 Impact Factor: 1.465

## Metrics

• PDF downloads (3)
• HTML views (0)
• Cited by (0)

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]