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 that 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. This article demonstrates numerical approximation techniques that 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-that is, 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, 1,000, and 10,000 unknowns.