American Institute of Mathematical Sciences

Advanced
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

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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems,, Pitman Research Notes in Mathematics, (1995).   Google Scholar

[7]

P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems,, SIAM Monographs on Mathematical Modeling and Computation, (1998).  doi: 10.1137/1.9780898719697.  Google Scholar

[8]

P. C. Hansen, Regularization tools,, Numer. Algo., 46 (2007), 189.  doi: 10.1007/s11075-007-9136-9.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

C. Vogel, Computational Methods for Inverse Problems, SIAM Frontier in Applied Mathematics,, Philadelphia, (2002).  doi: 10.1137/1.9780898717570.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems,, Pitman Research Notes in Mathematics, (1995).   Google Scholar

[7]

P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems,, SIAM Monographs on Mathematical Modeling and Computation, (1998).  doi: 10.1137/1.9780898719697.  Google Scholar

[8]

P. C. Hansen, Regularization tools,, Numer. Algo., 46 (2007), 189.  doi: 10.1007/s11075-007-9136-9.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

C. Vogel, Computational Methods for Inverse Problems, SIAM Frontier in Applied Mathematics,, Philadelphia, (2002).  doi: 10.1137/1.9780898717570.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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]

Ai-Guo Wu, Ying Zhang, Hui-Jie Sun. Parametric Smith iterative algorithms for discrete Lyapunov matrix equations. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-17. doi: 10.3934/jimo.2019093
[19]

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
[20]

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

2018 Impact Factor: 1.469

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences