Simple stopping criteria for the LSQR method applied to discrete ill-posed problems. (English) Zbl 1462.65040
Summary: The LSQR iterative method is one of the most popular numerical schemes for computing an approximate solution of large linear discrete ill-posed problems with an error-contaminated right-hand side, which represents available data. It is important to terminate the iterations after a suitable number of steps, because too many steps yield an approximate solution that suffers from a large propagated error due to the error in the data, and too few iterations give an approximate solution that may lack many details that can be of interest. When the error in the right-hand side is white Gaussian and a tight bound on its variance is known, the discrepancy principle typically furnishes a suitable termination criterion for the LSQR iterations. However, in many applications in science and engineering that give rise to large linear discrete ill-posed problems, the variance of the error is not known. This has spurred the development of a variety of stopping rules for assessing when to terminate the iterations in this situation. The present paper proposes new simple stopping rules that are based on comparing the residual errors associated with iterates generated by the LSQR and Craig iterative methods.
MSC:
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65F10 | Iterative numerical methods for linear systems |
Keywords:
discrete ill-posed problem; Golub-Kahan bidiagonalization; LSQR; Craig’s method; stopping criterionReferences:
| [1] | Baart, ML, The use of auto-correlation for pseudorank determination in noisy ill-conditioned linear least-squares problems, IMA J. Numer. Anal., 2, 241-247 (1982) · Zbl 0484.65021 · doi:10.1093/imanum/2.2.241 |
| [2] | Bauer, F.; Kindermann, S., The quasi-optimality criterion for classical inverse problems, Inverse Problems, 24, 035002 (2008) · Zbl 1143.65043 · doi:10.1088/0266-5611/24/3/035002 |
| [3] | Bauer, F.; Lukas, MA, Comparing parameter choice methods for regularization of ill-posed problems, Math. Comput. Simulation, 81, 1795-1841 (2011) · Zbl 1220.65063 · doi:10.1016/j.matcom.2011.01.016 |
| [4] | Bouhamidi, A.; Jbilou, K.; Reichel, L.; Sadok, H.; Wang, Z., Vector extrapolation applied to truncated singular value decomposition and truncated iteration, J. Eng. Math., 93, 99-112 (2015) · Zbl 1360.65109 · doi:10.1007/s10665-013-9677-y |
| [5] | Brezinski, C.; Redivo Zaglia, M.; Rodriguez, G.; Seatzu, S., Extrapolation techniques for ill-conditioned linear systems, Numer. Math., 81, 1-29 (1998) · Zbl 0921.65032 · doi:10.1007/s002110050382 |
| [6] | Brezinski, C.; Rodriguez, G.; Seatzu, S., Error estimates for linear systems with applications to regularization, Numer. Algorithms, 49, 85-104 (2008) · Zbl 1162.65018 · doi:10.1007/s11075-008-9163-1 |
| [7] | Brezinski, C.; Rodriguez, G.; Seatzu, S., Error estimates for the regularization of least squares problems, Numer. Algorithms, 51, 61-76 (2009) · Zbl 1166.65331 · doi:10.1007/s11075-008-9243-2 |
| [8] | Fenu, C.; Reichel, L.; Rodriguez, G.; Sadok, H., GCV for Tikhonov regularization by partial SVD, BIT Numer. Math., 57, 1019-1039 (2017) · Zbl 1386.65118 · doi:10.1007/s10543-017-0662-0 |
| [9] | Fox, L.; Goodwin, ET, The numerical solution of non-singular linear integral equations, Philos. Trans. Roy. Soc. London. Ser. A., 245, 501-534 (1953) · Zbl 0050.12902 · doi:10.1098/rsta.1953.0005 |
| [10] | Hanke, M., On Lanczos based methods for the regularization of discrete ill-posed problems, BIT Numer. Math., 41, 1008-1018 (2001) · doi:10.1023/A:1021941328858 |
| [11] | Hansen, PC, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev., 34, 561-580 (1992) · Zbl 0770.65026 · doi:10.1137/1034115 |
| [12] | Hansen, PC, Rank-deficient and discrete ill-Posed problems: Numerical aspects of linear inversion (1998), Philadelphia: SIAM, Philadelphia |
| [13] | Hansen, PC, Regularization Tools version 4.0 for Matlab 7.3, Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029 · doi:10.1007/s11075-007-9136-9 |
| [14] | Hansen, PC, Discrete inverse problems: insight and algorithms (2010), Philadelphia: SIAM, Philadelphia · Zbl 1197.65054 |
| [15] | Hochstenbach, ME; Reichel, L.; Rodriguez, G., Regularization parameter determination for discrete ill-posed problems, J. Comput. Appl. Math., 273, 132-149 (2015) · Zbl 1295.65046 · doi:10.1016/j.cam.2014.06.004 |
| [16] | Kindermann, S., Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems, Electron. Trans. Numer. Anal., 38, 233-257 (2011) · Zbl 1287.65043 |
| [17] | Meurant, G., Computer solution of large linear systems (1999), Amsterdam: Elsevier, Amsterdam · Zbl 0934.65032 |
| [18] | Meurant, G., The Lanczos and conjugate gradient algorithms (2006), Philadelphia: SIAM, Philadelphia · Zbl 1113.65032 |
| [19] | Morigi, S.; Reichel, L.; Sgallari, F.; Zama, F., Iterative methods for ill-posed problems and semiconvergent sequences, J. Comput. Appl. Math., 193, 157-167 (2006) · Zbl 1092.65025 · doi:10.1016/j.cam.2005.05.028 |
| [20] | Paige, CC, Bidiagonalization of matrices and solutions of linear equations, SIAM J. Numer. Anal., 11, 197-209 (1974) · Zbl 0244.65023 · doi:10.1137/0711019 |
| [21] | Paige, CC; Saunders, MA, LSQR: An algorithm for sparse linear equations and sparse least squares, ACM Trans. Math. Soft., 8, 43-71 (1982) · Zbl 0478.65016 · doi:10.1145/355984.355989 |
| [22] | Park, Y.; Reichel, L.; Rodriguez, G.; Yu, X., Parameter determination for Tikhonov regularization problems in general form, J. Comput. Appl. Math., 343, 12-25 (2018) · Zbl 1391.65100 · doi:10.1016/j.cam.2018.04.049 |
| [23] | Phillips, DL, A technique for the numerical solution of certain integral equations of the first kind, J. Assoc. Comput. Mach., 9, 84-97 (1962) · Zbl 0108.29902 · doi:10.1145/321105.321114 |
| [24] | Regińska, T., A regularization parameter in discrete ill-posed problems, SIAM J. Sci. Comput., 17, 740-749 (1996) · Zbl 0865.65023 · doi:10.1137/S1064827593252672 |
| [25] | Reichel, L.; Rodriguez, G., Old and new parameter choice rules for discrete ill-posed problems, Numer. Algorithms, 63, 65-87 (2013) · Zbl 1267.65045 · doi:10.1007/s11075-012-9612-8 |
| [26] | Reichel, L.; Sadok, H., A new L-curve for ill-posed problems, J. Comput. Appl. Math., 219, 493-508 (2008) · Zbl 1145.65035 · doi:10.1016/j.cam.2007.01.025 |
| [27] | Saunders, MA, Solution of sparse rectangular systems using LSQR and Craig, BIT Numer. Math., 35, 588-604 (1995) · Zbl 0844.65029 · doi:10.1007/BF01739829 |
| [28] | Shaw, CBJr, Improvement of the resolution of an instrument by numerical solution of an integral equation, J. Math. Anal. Appl., 37, 83-112 (1972) · Zbl 0237.65086 · doi:10.1016/0022-247X(72)90259-4 |
| [29] | Wilkinson, JH, The algebraic eigenvalue problem (1965), New York: Oxford University Press, New York · Zbl 0258.65037 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
