A note on the computation of the generalized cross-validation function for ill-conditioned least squares problems (Q760164)

In solving the finite-dimensional regularization problem of the form \(\min (\| Kf-g\|^ 2+\mu^ 2\| Lf\|^ 2)\) one suitable choice for the regularization parameter \(\mu\) is given by the method of generalized cross-validation. In this method one has to compute trace (I- KM\({}_{\mu}^{-1}K^ T)\) with \(M_{}\mu =K^ TK+\mu^ 2I.\) Normally a singular value decomposition (SVD) of K is used for this purpose. The author uses instead a bidiagonalization algorithm for computing \(K=U\left( \begin{matrix} B\\ 0\end{matrix} \right)V^ T\) with U, V orthogonal and B bidiagonal. Then the cross-validation function V(\(\mu)\) can be computed in O(n) operations. Execution time tests demonstrate, that this algorithm is about three times faster than the SVD-algorithm. But for this test the SVD of LINPACK is used, not the product form-SVD proposed by \textit{J. J. M. Cuppen} [SIAM J. Sci. Stat. Comput. 4, 216-222 (1983; Zbl 0517.65017)], which should give a considerable speed-up.