Fast generalized cross validation using Krylov subspace methods
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.
- The Computation of Generalized Cross-Validation Functions Through Householder Tridiagonalization with Applications to the Fitting of Interaction Spline Models
- Fast compact algorithms and software for spline smoothing.
- Efficient algorithms for robust generalized cross-validation spline smoothing
- A fast ``Monte-Carlo cross-validation procedure for large least squares problems with noisy data
- scientific article; zbMATH DE number 3992077
- A class of iterative methods for finite element equations
- A comparison of GCV and GML for choosing the smoothing parameter in the generalized spline smoothing problem
- A Deflation Technique for Linear Systems of Equations
- A Flexible Inner-Outer Preconditioned GMRES Algorithm
- A new look at the Lanczos algorithm for solving symmetric systems of linear equations
- A Review on the Inverse of Symmetric Tridiagonal and Block Tridiagonal Matrices
- A Stochastic Estimator of the Trace of the Influence Matrix for Laplacian Smoothing Splines
- A Taxonomy for Conjugate Gradient Methods
- An engineering approach to generalized conjugate gradient methods and beyond
- An Iterative Solution Method for Linear Systems of Which the Coefficient Matrix is a Symmetric M-Matrix
- An iterative solution method for solving \(f(A)x=b\), using Krylov subspace information obtained for the symmetric positive definite matrix A
- Arnoldi methods for large Sylvester-like observer matrix equations, and an associated algorithm for partial spectrum assignment
- Block Preconditioning for the Conjugate Gradient Method
- Efficient Implementation of a Class of Preconditioned Conjugate Gradient Methods
- Generalized Cross-Validation as a Method for Choosing a Good Ridge Parameter
- GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
- scientific article; zbMATH DE number 3671573 (Why is no real title available?)
- scientific article; zbMATH DE number 3762598 (Why is no real title available?)
- scientific article; zbMATH DE number 43693 (Why is no real title available?)
- scientific article; zbMATH DE number 45848 (Why is no real title available?)
- scientific article; zbMATH DE number 554737 (Why is no real title available?)
- scientific article; zbMATH DE number 592768 (Why is no real title available?)
- scientific article; zbMATH DE number 733664 (Why is no real title available?)
- scientific article; zbMATH DE number 1058089 (Why is no real title available?)
- scientific article; zbMATH DE number 3408799 (Why is no real title available?)
- scientific article; zbMATH DE number 961607 (Why is no real title available?)
- Iterative Solution of Linear Equations in ODE Codes
- Methods of conjugate gradients for solving linear systems
- Polynomial Preconditioners for Conjugate Gradient Calculations
- Restarted GMRES preconditioned by deflation
- Smoothing noisy data with spline functions
- Smoothing noisy data with spline functions
- The block conjugate gradient algorithm and related methods
- The Computation of Generalized Cross-Validation Functions Through Householder Tridiagonalization with Applications to the Fitting of Interaction Spline Models
- The implementation of a generalized cross validation algorithm using deflation techniques for linear systems
- The Lanczos Algorithm With Partial Reorthogonalization
- The Lanczos Algorithm with Selective Orthogonalization
- A fast ``Monte-Carlo cross-validation procedure for large least squares problems with noisy data
- The generalized cross validation filter
- Concentration inequalities for cross-validation in scattered data approximation
- A stochastic extended Rippa's algorithm for LpOCV
- GCV for Tikhonov regularization via global Golub-Kahan decomposition.
- Asymptotic Properties of Complete Smoothing Splines and Applications
- Sulla regolarizzazione mediante la «Generalized cross validation»: Una appliczione al caso dei polinomi ortogonali
- scientific article; zbMATH DE number 4074313 (Why is no real title available?)
- scientific article; zbMATH DE number 18427 (Why is no real title available?)
- scientific article; zbMATH DE number 1104522 (Why is no real title available?)
- Gcvpack – routines for generalized cross validation
- scientific article; zbMATH DE number 1875401 (Why is no real title available?)
- An eigenvalue approach for estimating the generalized cross validation function for correlated matrices
- scientific article; zbMATH DE number 2232685 (Why is no real title available?)
- Fast Generalized Cross-Validation Algorithm for Sparse Model Learning
- Fast cross-validation in harmonic approximation
- Fast cross-validation algorithms for least squares support vector machine and kernel ridge regression
This page was built for publication: Fast generalized cross validation using Krylov subspace methods
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2481402)
