A fast ``Monte-Carlo cross-validation'' procedure for large least squares problems with noisy data (Q1116267)

We propose a fast Monte-Carlo algorithm for calculating reliable estimates of the trace of the influence matrix \(A_{\tau}\) involved in regularization of linear equations or data smoothing problems, where \(\tau\) is the regularization or smoothing parameter. This general algorithm is simply as follows: i) generate n-pseudo-random values \(w_ 1,...,w_ n\), from the standard normal distribution (where n is the number of data points) and let \(w=(w_ 1,...,w_ n)^ T\), ii) compute the residual vector \(w-A_{\tau}w\), iii) take the `normalized' inner product \((w^ T(w-A_{\tau}w))/(w^ Tw)\) as an approximation to \((1/n)tr(I-A_{\tau}).\) We show, both by theoretical bounds and by numerical simulations on some typical problems, that the expected relative precision of these estimates is very good when n is large enough, and that they can be used in practice for the minimization with respect to \(\tau\) of the well-known generalized cross validation (GCV) function. This permits the use of the GCV method for choosing \(\tau\) in any particular large-scale application, with only a similar amount of work as the standard residual method. Numerical applications of this procedure to optimal spline smoothing in one or two dimensions show its efficiency.