Next: RGCV for Steepest
Up: Generalized Cross-Validation as a
Previous: The Richardson-Lucy Algorithm
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.
Next: RGCV for Steepest
Up: Generalized Cross-Validation as a
Previous: The Richardson-Lucy Algorithm