Finite-grid generalized cross-validation for Tikhonov regularization

Input a real matrix $A\in {\mathbb{R}}^{m\times n}$ with $m\ge 1$, data $b\in {\mathbb{R}}^m$, and a nonempty strictly increasing finite grid $0<{\lambda }_1<\cdots <{\lambda }_N$. For each ${\lambda }_j$, compute the unique Tikhonov minimizer $x_j=(A^{T}A+{\lambda }_{j}I{)}^{-1}{A}^{T}b$, form $H_j=A(A^{T}A+{\lambda }_{j}I{)}^{-1}{A}^T$, and compute $G_j=\frac{\mathrm{\parallel }(I-H_j)b{\mathrm{\parallel }}^2}{m(1-\mathrm{tr}(H_j)\mathrm{/}m{)}^2}\mathrm{.}$ The denominator is positive because ${\lambda }_j>0$ makes every eigenvalue of $H_j$ strictly less than one. Return the pair $({\lambda }_j,G_j)$ with minimal score; if several grid points minimize it, return the smallest index. Also return the full finite list of scores. This rule minimizes the stated GCV score on its supplied grid; it does not claim to minimize the unknown solution error or to be universally optimal.