The Randomized Generalized Cross Validation (RGCV) Criterion

Cross-validation divides the data into two sets. It uses one set to determine some characteristics of the data, and then uses the other set to verify the characteristics. Extending this concept, generalized cross-validation (GCV) uses each data point as the testing set, and then averages a weighted prediction error over the entire data set (Golub et al. 1979).

The GCV criterion can be stated as

where is the number of data points. The matrix is called the influence matrix at the th iteration. If we define as the th estimate for the original data as determined by some iterative algorithm, then is defined as

The main drawback of the GCV criterion comes from the denominator of . Unlike the numerator, which can be easily computed at each iteration, the denominator term, needs the equivalent of restoration computations to be computed explicitly. This computational expense is due to the trace term. Therefore, we estimate the trace term using the following lemma.

Proof The proof is straightforward.

Several researchers independently observed that the denominator term can be estimated using this property (Girard 1989, Hutchinson 1990, Reeves and Mersereau 1991). So the denominator of V(n) can be computed as

and is now called the Randomized GCV (RGCV) criterion. Still, we do not want to compute . So using the relationship , we define a new image that satisfies

which means that is like a ``restored'' version of at the th iteration.

Therefore, instead of computing explicitly, we can compute by restoring in the same manner as we restore . Thus, now has the form

The computation of the RGCV criterion simply boils down to the computation of . The factor we must deal with is ``restoring'' in the same manner as . Fortunately, the influence matrix can also be defined as (Wahba 1983)

where is the th entry in the matrix , and

Therefore, if one computes for each iteration, and uses

as the update for , then the ``restoration'' on proceeds as the restoration on . Equivalently, from ,

Thus, if the derivative can be computed analytically for all , then the update for can be established.