×

Linear regression models, least-squares problems, normal equations, and stopping criteria for the conjugate gradient method. (English) Zbl 1305.65021

Summary: Minimum-variance unbiased estimates for linear regression models can be obtained by solving least-squares problems. The conjugate gradient method can be successfully used in solving the symmetric and positive definite normal equations obtained from these least-squares problems. Taking into account the results of G. H. Golub and G. Meurant [BIT 37, No. 3, 687–705 (1997; Zbl 0888.65050); Matrices, moments and quadrature with applications. Princeton, NJ: Princeton University Press (2010; Zbl 1217.65056)], M. R. Hestenes and E. Stiefel [J. Res. Natl. Bur. Stand. 49, 409–436 (1952; Zbl 0048.09901)], and Z. Strakoš and P. Tichý [ETNA, Electron. Trans. Numer. Anal. 13, 56–80 (2002; Zbl 1026.65027)], which make it possible to approximate the energy norm of the error during the conjugate gradient iterative process, we adapt the stopping criterion introduced by M. Arioli [Numer. Math. 97, No. 1, 1–24 (2004; Zbl 1048.65029)] to the normal equations taking into account the statistical properties of the underpinning linear regression problem. Moreover, we show how the energy norm of the error is linked to the \(\chi^{2}\)-distribution and to the Fisher-Snedecor distribution. Finally, we present the results of several numerical tests that experimentally validate the effectiveness of our stopping criteria.

MSC:

65C60 Computational problems in statistics (MSC2010)
62J05 Linear regression; mixed models
65F20 Numerical solutions to overdetermined systems, pseudoinverses
65F10 Iterative numerical methods for linear systems

Software:

CRAIG; SparseMatrix; LSQR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Paige, C. C.; Saunders, M., LSQR: an algorithm for sparse linear equations and sparse least squares, ACM Transactions on Mathematical Software, 8, 43-71 (1982) · Zbl 0478.65016
[2] Abramowitz, M.; Stegun, I. A., (Handbook of Mathematical Functions. Handbook of Mathematical Functions, National Bureau of Standards, Series, vol. #55 (1964), Dover Publications: Dover Publications USA) · Zbl 0171.38503
[3] Hocking, R. R., (Methods and Applications of Linear Models. Methods and Applications of Linear Models, Wiley Series in Probability and Statistics (1996), Wiley-Interscience: Wiley-Interscience New York) · Zbl 0934.62067
[4] Magnus, J. R.; Neudecker, H., (Matrix Differential Calculus with Applications in Statistic and Econometrics. Matrix Differential Calculus with Applications in Statistic and Econometrics, Wiley Series in Probability and Statistics (1999), John Wiley & Sons: John Wiley & Sons Chichester, UK) · Zbl 0912.15003
[5] Seber, G. A.F., (The Linear Hypothesis: A General Theory. The Linear Hypothesis: A General Theory, Griffin’s Statistical Monographs and Courses (1966), Charles Griffin and Company Limited: Charles Griffin and Company Limited London) · Zbl 0147.37202
[6] Ashby, S. F.; Holst, M. J.; Manteuffel, T. A.; Saylor, P. E., The role of the inner product in stopping criteria for conjugate gradient iterations, BIT, 41, 1, 26-52 (2001) · Zbl 0984.65025
[7] Axelsson, O.; Kaporin, I., Error norm estimation and stopping criteria in preconditioned conjugate gradient iterations, Journal of Numerical Linear Algebra with Applications, 8, 265-286 (2001) · Zbl 1051.65024
[8] Calvetti, D.; Morigi, S.; Reichel, L.; Sgallari, F., Computable error bounds and estimates for the conjugate gradient method, Numerical Algorithms, 25, 75-88 (2000) · Zbl 0976.65033
[9] Calvetti, D.; Morigi, S.; Reichel, L.; Sgallari, F., An iterative method with error estimators, Journal of Computational and Applied Mathematics, 127, 93-119 (2001) · Zbl 0970.65028
[10] Golub, G.; Meurant, G., Matrices, moments and quadrature II: how to compute the norm of the error in iterative methods, BIT, 37, 687-705 (1997) · Zbl 0888.65050
[11] Golub, G.; Meurant, G., Matrices, Moments and Quadrature with Applications (2009), Princeton University Press: Princeton University Press Princeton, New Jersey · Zbl 0888.65050
[12] Golub, G.; Strakoš, Z., Estimates in quadratic formulas, Numerical Algorithms, 8, 241-268 (1994) · Zbl 0822.65022
[13] Meurant, G., The computation of bounds for the norm of the error in the conjugate gradient algorithm, Numerical Algorithms, 16, 77-87 (1997) · Zbl 0897.65026
[14] Meurant, G., (Computer Solution of Large Linear Systems. Computer Solution of Large Linear Systems, Studies in Mathematics and its Application, vol. 28 (1999), Elsevier, North-Holland: Elsevier, North-Holland Amsterdam, The Netherlands)
[15] Meurant, G., Numerical experiments in computing bounds for the norm of the error in the preconditioned conjugate gradient algorithm, Numerical Algorithms, 22, 353-365 (1999) · Zbl 0954.65025
[16] Strakoš, Z.; Tichý, P., On error estimation in the conjugate gradient method and why it works in finite precision computations, Electronic Transactions on Numerical Analysis (ETNA), 13, 56-80 (2002) · Zbl 1026.65027
[17] Hestenes, M.; Stiefel, E., Methods of conjugate gradients for solving linear systems, Journal of Research of the National Bureau of Standards, 49, 409-436 (1952) · Zbl 0048.09901
[18] Arioli, M., A stopping criterion for the conjugate gradient algorithm in a finite element method framework, Numerische Mathematik, 97, 1-24 (2005), Electronic version · Zbl 1048.65029
[19] Strakoš, Z.; Tichý, P., Error estimation in preconditioned conjugate gradients, BIT Numerical Mathematics, 45, 789-817 (2005) · Zbl 1095.65029
[20] Arioli, M.; Noulard, E.; Russo, A., Stopping criteria for iterative methods: applications to PDE’s, Calcolo, 38, 97-112 (2001) · Zbl 1072.65045
[21] Rigal, J. L.; Gaches, J., On the compatibility of a given solution with the data of a linear system, Journal of the Association for Computing Machinery, 14, 543-548 (1967) · Zbl 0183.17704
[22] Jiranek, P.; Titley-Peloquin, D., Estimating the backward error in LSQR, SIAM Journal on Matrix Analysis and Applications, 31, 2055-2074 (2010) · Zbl 1202.65047
[23] Garthwaite, P. H.; Jolliffe, I. T.; Jones, B., Statistical Inference (1995), Prentice Hall International Limited: Prentice Hall International Limited UK · Zbl 0862.62002
[24] Greenbaum, A., Iterative Methods for Solving Linear Systems (1997), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA · Zbl 0883.65022
[25] Björck, Å.; Elfving, T.; Strakoš, Z., Stability of conjugate gradient and Lanczos methods for linear least-squares problems, SIAM Journal on Matrix Analysis and Applications, 19, 720-736 (1998) · Zbl 0924.65035
[26] Davis, T. A., The university of Florida sparse matrix collection, ACM Transactions on Mathematical Software, 38, 1 (2011) · Zbl 1365.65123
[27] Tshimanga, J.; Gratton, S.; Weaver, A. T.; Sartenaer, A., Limited-memory preconditioners with application to incremental four-dimensional variational data assimilation, Quarterly Journal of the Royal Meteorological Society, 134, 753-771 (2008)
[28] Rust, B. W., Parameter selection for constrained solutions to ill-posed problems, Computing Science and Statistics, 32, 333-347 (2000)
[29] Rust, B. W.; O’Leary, D., Residual periodograms for choosing regularization parameters for ill-posed problems, Inverse Problems, 24, 034005 (2008), p. 30 · Zbl 1137.62036
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.