Fast generalized cross validation using Krylov subspace methods (Q2481402)

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.