# 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, Bristol, 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-134. 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-23. 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-223. doi: 10.1080/00401706.1979.10489751.  Google Scholar [6] M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems, Pitman Research Notes in Mathematics, Longman, Harlow, 1995.  Google Scholar [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.  Google Scholar [8] P. C. Hansen, Regularization tools, Numer. Algo., 46 (2007), 189-194. 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-1732. 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-1264. 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-118. 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-128. 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-667. doi: 10.1137/0714044.  Google Scholar [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.  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-643. 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-628. 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, Bristol, 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-134. 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-23. 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-223. doi: 10.1080/00401706.1979.10489751.  Google Scholar [6] M. Hanke, Conjugate Gradient Type Methods for Ill-Posed Problems, Pitman Research Notes in Mathematics, Longman, Harlow, 1995.  Google Scholar [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.  Google Scholar [8] P. C. Hansen, Regularization tools, Numer. Algo., 46 (2007), 189-194. 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-1732. 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-1264. 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-118. 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-128. 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-667. doi: 10.1137/0714044.  Google Scholar [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.  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-643. 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-628. 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] Dang Van Hieu, Le Dung Muu, Pham Kim Quy. New iterative regularization methods for solving split variational inclusion problems. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2020  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 & 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 & 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 & 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 & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193

2020 Impact Factor: 1.639

## Metrics

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

## Other articlesby authors

• on AIMS
• on Google Scholar

[Back to Top]