An inner-outer regularizing method for ill-posed problems

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

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 and 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, 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.

show all references

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.

[1]	You-Wei Wen, Raymond Honfu Chan. Using generalized cross validation to select regularization parameter for total variation regularization problems. Inverse Problems and 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 and Optimization, 2012, 2 (4) : 855-862. doi: 10.3934/naco.2012.2.855
[3]	Dang Van Hieu, Le Dung Muu, Pham Kim Quy. New iterative regularization methods for solving split variational inclusion problems. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021185
[4]	Ye Zhang, Bernd Hofmann. Two new non-negativity preserving iterative regularization methods for ill-posed inverse problems. Inverse Problems and Imaging, 2021, 15 (2) : 229-256. doi: 10.3934/ipi.2020062
[5]	Shishun Li, Zhengda Huang. Guaranteed descent conjugate gradient methods with modified secant condition. Journal of Industrial and Management Optimization, 2008, 4 (4) : 739-755. doi: 10.3934/jimo.2008.4.739
[6]	Wataru Nakamura, Yasushi Narushima, Hiroshi Yabe. Nonlinear conjugate gradient methods with sufficient descent properties for unconstrained optimization. Journal of Industrial and Management Optimization, 2013, 9 (3) : 595-619. doi: 10.3934/jimo.2013.9.595
[7]	Anulekha Dhara, Aparna Mehra. Conjugate duality for generalized convex optimization problems. Journal of Industrial and Management Optimization, 2007, 3 (3) : 415-427. doi: 10.3934/jimo.2007.3.415
[8]	Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[9]	El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial and Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[10]	ShiChun Lv, Shou-Qiang Du. A new smoothing spectral conjugate gradient method for solving tensor complementarity problems. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021150
[11]	Yanxing Cui, Chuanlong Wang, Ruiping Wen. On the convergence of generalized parallel multisplitting iterative methods for semidefinite linear systems. Numerical Algebra, Control and Optimization, 2012, 2 (4) : 863-873. doi: 10.3934/naco.2012.2.863
[12]	Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1503-1518. doi: 10.3934/jimo.2019013
[13]	Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157
[14]	Gaohang Yu, Lutai Guan, Guoyin Li. Global convergence of modified Polak-Ribière-Polyak conjugate gradient methods with sufficient descent property. Journal of Industrial and Management Optimization, 2008, 4 (3) : 565-579. doi: 10.3934/jimo.2008.4.565
[15]	Lili Ju, Wei Leng, Zhu Wang, Shuai Yuan. Numerical investigation of ensemble methods with block iterative solvers for evolution problems. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4905-4923. doi: 10.3934/dcdsb.2020132
[16]	Ya Li, ShouQiang Du, YuanYuan Chen. Modified spectral PRP conjugate gradient method for solving tensor eigenvalue complementarity problems. Journal of Industrial and Management Optimization, 2022, 18 (1) : 157-172. doi: 10.3934/jimo.2020147
[17]	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 and Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[18]	Yuhong Dai, Ya-xiang Yuan. Analysis of monotone gradient methods. Journal of Industrial and Management Optimization, 2005, 1 (2) : 181-192. doi: 10.3934/jimo.2005.1.181
[19]	Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure and Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791
[20]	C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial and Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193

2021 Impact Factor: 1.483

Tools

Metrics

Other articles
by authors

on AIMS
Paola Favati Grazia Lotti Ornella Menchi Francesco Romani
on Google Scholar
Paola Favati Grazia Lotti Ornella Menchi Francesco Romani

[Back to Top]