×

zbMATH — the first resource for mathematics

Fast generalized cross validation using Krylov subspace methods. (English) Zbl 1157.65012
The key step of the generalized cross-validation (GCV) method, used in a smoothing spline fitting of noisy data, is the computation of the optimal parameter \(\lambda \) by minimization of the GCV function \[ \text{GCV}(\lambda )= n\, {z^T (Q+\lambda I)^{-2} z \over [ \text{tr}\, ((Q+\lambda I)^{-1})]^2}, \] for the influence matrix \(Q\) and the vector of observations \(z\). A standard approach to minimization is a line-search, so that a straightforward implementation of this method makes it necessary to solve in each iteration two large linear systems with dense matrices of the form \(Q+\lambda I\) and \((Q+\lambda I)^2\). Without a good preconditioner, even an iterative approach to the solution of these systems is time consuming.
A key observation of the authors is that the Krylov subspaces are invariant with respect to shifting the original matrix by a multiple of \(I\), which suggests a possibility of a “re-usable” generation of the orthogonal Krylov basis. Using the Lanczos method of computing such a basis and taking into account some recurrence relations connecting different values of \(\lambda \), an algorithm is suggested, in which each evaluation of the GCV function makes use of the work that was previously performed. This fast GCV framework allows a substantial saving in computational cost. The paper contains the theoretical development of the algorithm, discusses convergence, stability and complexity issues, as well as presents a series of numerical examples illustrating the benefits of this approach.

MSC:
65D10 Numerical smoothing, curve fitting
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ashby, S., Manteuffel, T., Saylor, P.: A taxonomy for conjugate gradient methods. SIAM J. Numer. Anal. 27, 1542–1568 (1990) · Zbl 0723.65018 · doi:10.1137/0727091
[2] Axelsson, O.: A class of iterative methods for finite element equations. Comput. Methods Appl. Mech. Eng. 9, 123–137 (1976) · Zbl 0334.65028 · doi:10.1016/0045-7825(76)90056-6
[3] Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J., Dongarra, J., Eijkhout, V., Pozo, R., Romine, C., Van der Vorst, H.: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd edn. SIAM, Philadelphia, PA, USA (1994) · Zbl 0814.65030
[4] Burrage, K., Erhel, J., Pohl, B., Williams, A.: A deflation technique for systems of linear equations. SIAM J. Sci. Comput. 19(4), 1245–1260 (1998) · Zbl 0914.65025 · doi:10.1137/S1064827595294721
[5] Burrage, K., Williams, A., Erhel, J., Pohl, B.: Implementation of a generalised cross validation algorithm using deflation techniques for systems of linear equations. Appl. Numer. Math. 19, 17–31 (1995) · Zbl 0853.65043 · doi:10.1016/0168-9274(95)00016-N
[6] Choquet, R.: Étude de la methode de Newton-GMRES. Application aux équations de Navier–Stokes compressibles. Ph.D. thesis, University of Rennes 1. No 1499, Dec 1995
[7] Concus, P., Golub, G., Meurant, G.: Block preconditioning for the conjugate gradient method. SIAM J. Sci. Statist. Comp. 6, 220–252 (1985) · Zbl 0556.65022 · doi:10.1137/0906018
[8] Datta, B.N., Saad, Y.: Arnoldi methods for large Sylvester-like observer matrix equations, and an associated algorithm ofr partial spectrum assignment. Linear Algebra Appl. 154–156, 225–244 (1991) · Zbl 0734.65037 · doi:10.1016/0024-3795(91)90378-A
[9] Eisenstat, S.C.: Efficient implementation of a class of preconditioned conjugate gradient methods. SIAM J. Sci. Statist. Comput. 2, 1–4 (1981) · Zbl 0474.65020 · doi:10.1137/0902001
[10] Erhel, J., Burrage, K., Pohl, B.: Restarted GMRES preconditioned by deflation. J. Comput. Appl. Math. 69, 303–318 (1996) · Zbl 0854.65025 · doi:10.1016/0377-0427(95)00047-X
[11] Freund, R.W.: Solution of shifted linear systems by quasi-minimal residual iterations. In: Reichel, L., Ruttan, A., Varga, R.S. (eds.) Numerical Linear Algebra, pp. 101–121. de Gruyter, Berlin (1993) · Zbl 0794.65028
[12] Gear, C.W., Saad, Y.: Iterative solution of linear equations in ODE codes. SIAM J. Sci. Statist. Comput. 4(4), 583–601 (1983) · Zbl 0541.65051 · doi:10.1137/0904040
[13] Golub, G., Heath, M., Wahba, G.: Generalized cross validation as a method for choosing a good ridge parameter. Technometrics 21, 215–224 (1979) · Zbl 0461.62059 · doi:10.2307/1268518
[14] Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[15] Golub, G., Meurant, G.: Matrices, moments and quadrature. In: Griffiths, D.F., Waston, G.A. (eds.) Numerical Analysis 93. Pitman Research Notes in Mathematics 303, Longman Scientific and Technical (1993) · Zbl 0795.65019
[16] Golub, G.H., von Matt, U.: Generalized cross-validation for large scale problems. J. Comput. Graph. Stat. 6(1), 1–34 (1997) · Zbl 0878.65032 · doi:10.2307/1390722
[17] Gu, C., Bates, D., Chen, Z., Wahba, G.: The computation of GCV functions through Householder tridiagonalisation with application to the fitting of interaction spline models. SIAM J. Matrix Anal. Appl. 10, 459–480 (1989) · Zbl 0685.65134 · doi:10.1137/0610033
[18] Hestenes, M., Stiefel, E.: Methods of conjugate gradients for solving linear systems. NBS J. Research 49, 409–436 (1952) · Zbl 0048.09901
[19] Hutchinson, M.F.: A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines. Commun. Stat. Simul. Comput. 18, 1059–1076 (1989) · Zbl 0695.62113 · doi:10.1080/03610918908812806
[20] Hutchinson, M.F., DeHoog, F.: Smoothing noisy data with spline functions. Numer. Math. 47, 99–106 (1985) · Zbl 0578.65009 · doi:10.1007/BF01389878
[21] Johnson, O., Michelli, C., Paul, G.: Polynomial preconditioners for conjugate gradient calculations. SIAM J. Numer. Anal. 20, 362–376 (1983) · Zbl 0563.65020 · doi:10.1137/0720025
[22] Meijerink, J.A., van der Vorst, H.A.: An iterative solution method for linear systems of which the coefficient matrix is a symmetric M-matrix. Math. Comput. 31, 148–152 (1977) · Zbl 0349.65020
[23] Meurant, G.: A review of the inverse of tridiagonal and block tridiagonal matrices. SIAM J. Matrix Anal. Appl. 13(3), 707–728 (1992) · Zbl 0754.65029 · doi:10.1137/0613045
[24] O’Leary, D.P.: The block conjugate gradient algorithm and related methods. Linear Algebra Appl. 29, 293–322 (1980) · Zbl 0426.65011 · doi:10.1016/0024-3795(80)90247-5
[25] Ortega, J.: Introduction to Parallel and Vector Solution of Linear Systems. Plenum Press (1988) · Zbl 0669.65017
[26] Parlett, B.: The Symmetric Eigenvalue Problem. Prentice Hall (1980) · Zbl 0431.65017
[27] Parlett, B.N.: A new look at the Lanczos method for solving symmetric systems of linear equations. Linear Algebra Appl. 29, 323–346 (1980) · Zbl 0431.65016 · doi:10.1016/0024-3795(80)90248-7
[28] Parlett, B.N., Scott, D.S.: The Lanczos algorithm with selective orthogonalization. Math. Comput. 33, 217–238 (1979) · Zbl 0405.65015 · doi:10.1090/S0025-5718-1979-0514820-3
[29] Philippe, B., Sidje, R.B.: Cumulative solutions of Markov processes by Krylov subspaces. In: Sixth International Conference of Scientific Computing, Benin City, Nigeria, 24–28 Jan 1992
[30] Saad, Y.: A flexible inner outer preconditioned GMRES algorithm. SIAM J. Sci. Comput. 14, 461–469 (1993) · Zbl 0780.65022 · doi:10.1137/0914028
[31] Saad, Y., Schultz, M.H.: GMRES: a generalized minimal residual algorithm for solving nonsymmetric linear systems. SIAM J. Sci. Statist. Comput. 7, 856–869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058
[32] Schoenauer, W., Weiss, R.: An engineering approach to generalized conjugate gradient methods and beyond. Appl. Numer. Math. 19, 175–206 (1995) · Zbl 0854.65030 · doi:10.1016/0168-9274(95)00083-6
[33] Sidje, R.B.: Parallel algorithms for large sparse matrix exponentials: application to numerical transient analysis of Markov processes. Ph.D. thesis, University of Rennes 1, July 1994
[34] Simon, H.D.: The Lanczos algorithm with partial reorthogonalization. Math. Comput. 42, 115–142 (1984) · Zbl 0546.65017 · doi:10.1090/S0025-5718-1984-0725988-X
[35] van der Vorst, H.: An iterative solution method for solving f(A)x = b using Krylov subspace information obtained for the symmetric positive definite matrix A. J. Comput. Appl. Math. 18, 249–263 (1987) · Zbl 0621.65022 · doi:10.1016/0377-0427(87)90020-3
[36] Wahba, G.: Smoothing noisy data by spline functions. Numer. Math. 24, 383–393 (1975) · Zbl 0299.65008 · doi:10.1007/BF01437407
[37] Wahba, G.: Spline bases, regularization, and generalized cross validation for solving approximation problems with large quantities of noisy data. In: Cheney, W. (ed.) Approximation Theory III, pp. 905–912. Academic Press, New York (1980) · Zbl 0485.41012
[38] Wahba, G.: A comparison of GCV and GML for choosing the smoothing parameter in the generalized spline smoothing problem. Ann. Statist. 13, 1378–1402 (1985) · Zbl 0596.65004 · doi:10.1214/aos/1176349743
[39] Wahba, G.: Spline Models for Observational Data. SIAM. CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 59 (1990) · Zbl 0813.62001
[40] Wahba, G., Wendelberger, J.: Some new mathematical methods for variational objective analysis using splines and cross validation. Mon. Weather Rev. 108, 1122–1145 (1980) · doi:10.1175/1520-0493(1980)108<1122:SNMMFV>2.0.CO;2
[41] Wilkinson, J.: The Algebraic Eigenvalue Problem. Claredon Press (1965) · Zbl 0258.65037
[42] Williams, A., Burrage, K.: Surface fitting using GCV smoothing splines on supercomputers. Conference proceedings, Supercomputing95, San Diego, USA (1995)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.