Fast generalized cross validation using Krylov subspace methods (Q2481402)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Fast generalized cross validation using Krylov subspace methods |
scientific article |
Statements
Fast generalized cross validation using Krylov subspace methods (English)
0 references
9 April 2008
0 references
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.
0 references
generalized cross validation
0 references
Krylov subspace method
0 references
smoothing spline fitting of noisy data
0 references
Lanczos method
0 references
algorithm
0 references
convergence
0 references
stability
0 references
complexity
0 references
complexity issues
0 references
0 references
0 references
0 references
0 references
0 references