Generalized Cross-Validation for Large-Scale Problems

. Although generalized cross-validation is a popular tool for calculating a regularization parameter it has been rarely applied to large scale problems until recently. A major difficulty lies in the evaluation of the cross-validation function which requires the calculation of the trace of an inverse matrix. In the last few years stochastic trace estimators have been proposed to alleviate this problem. In this paper numerical approximation techniques are used to further reduce the computational complexity. The new approach employs Gauss quadrature to compute lower and upper bounds on the cross-validation function. It only requires the operator form of the system matrix, i.e., a subroutine to evaluate matrix-vector products. Thus the factorization of large matrices can be avoided. The new approach has been implemented in MATLAB. Numerical experiments confirm the remarkable accuracy of the stochastic trace estimator. Regularization parameters are computed for ill-posed problems with 100, ...