Finite Dimensional Approximation and Tikhonov Regularization Method

The Tikhonov regularized solution of the convolution equation (1) is the minimizer in of the regularization functional (Tikhonov &Arsenin 1977, Morozov 1984, Groetsch 1984):

where is the regularization parameter to be chosen depending on the noise level. This functional can be expressed by the Plancherel theorem in the frequency space as follows:

Hence it is straightforward to prove, by variational calculus, that the minimizer of is the solution of the equation

where denotes the complex conjugate of .

Since any image is numerically represented as a non-negative function with finite support (in other words: outside ), we restrict our considerations to the rectangle . The regularized solution , in a discrete set of equally spaced points of , is then the inverse discrete Fourier transform of

which can be evaluated easily by the Fast Fourier Transform (FFT) method.

Let be the set of knots of a regular mesh of the space domain and be the B-spline of order relative to the equally spaced knots of the extended interval . Then, the unknown function can be approximated by the order spline

whose coefficients, as a direct consequence of (6), may be obtained solving in a regular mesh of points the system

where

Let be the set of knots of a uniform decomposition of the frequency domain . The matrix is an orthogonal matrix since , where is the adjoint of and is the identity matrix of order ; then we can solve the system (8) using the inverse discrete Fourier transform. Thus we obtain:

where and is the Tikhonov regularized solution in the frequency space.

Since the approximation properties of splines are only asymptotically satisfied, that is they hold only if converges to , we replace the above expression of by its limit for . In this way converges to and then, excep for edge effects, . In other words, the coefficients of B-splines converge, for each value of , to the values of the Tikhonov regularized solution obtained by the discrete Fourier transform applied to .

This regularization technique, based on approximation by splines, can then be seen as a method, with a very low computational complexity, for recovering the image in all the points (except for the edges) of its domain and not only in the knots of its mesh. It is remarkable that these limits can also been obtained by expressing as a linear combination of sinc functions and then applying the Tikhonov regularization method in the frequency space. Such an expansion is usual for band limited functions, as a direct consequence of the sampling theorem which states that, if outside the domain , then the values of at the sampling points can be interpolated by a bi-infinite series of sinc functions to reproduce . In our numerical computations we approximate this series by the finite sum

where the coefficients are the values of at the sampling points. We recall, for the reader's convenience, that the Fourier transform of a sinc function is a square pulse. More precisely Therefore the Tikhonov regularized solution of equation (1) sought in a finite-dimensional span of sinc functions, is the solution on a discrete set of values of the problem

For each value of we have a regularized solution whose expansion by sinc is uniquely characterized by the coefficients which can be easily obtained applying the FFT to relation (12). These coefficients, as already remarked, are the limits (for ) of the coefficients of the same regularized solution spanned by B-splines. This fact is not completely surprising because the interpolation in the sampling points by splines of order , for converges to the interpolation in the same points by sinc functions (Schoenberg 1973).