An inner-outer regularizing method for ill-posed problems

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

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

An inner-outer regularizing method for ill-posed problems

Paola Favati ^1, , Grazia Lotti ^2, , Ornella Menchi ^3, and Francesco Romani ^3,

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

Abstract
Related Papers

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: iterative methods, generalized cross validation, inner-outer algorithms., Regularization problems, conjugate gradient.

Mathematics Subject Classification: 65F22, 65F1.

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

American Institute of Mathematical Sciences