  Finding a good regularization parameter for Tikhonov regularization problems
is a though yet often asked question. One approach is to use leave-one-out
cross-validation scores to indicate the goodness of fit. This utilizes only the
noisy function values but, on the downside, comes with a high computational
cost. In this paper we present a general approach to shift the main
computations from the function in question to the node distribution and, making
use of FFT and FFT-like algorithms, even reduce this cost tremendously to the
cost of the Tikhonov regularization problem itself. We apply this technique in
different settings on the torus, the unit interval, and the two-dimensional
sphere. Given that the sampling points satisfy a quadrature rule our algorithm
computes the cross-validations scores in floating-point precision. In the cases
of arbitrarily scattered nodes we propose an approximating algorithm with the
same complexity. Numerical experiments indicate the applicability of our
algorithms.
