On the regularizing power of multigrid-type algorithms

We consider the deblurring problem of noisy and blurred images in
the case of known space invariant point spread functions with four
choices of boundary conditions. We combine an algebraic multigrid
previously defined ad hoc for structured matrices related to space
invariant operators (Toeplitz, circulants, trigonometric matrix
algebras, etc.) and the classical geometric multigrid studied in
the partial differential equations context. The resulting
technique is parameterized in order to have more degrees of
freedom: a simple choice of the parameters allows us to devise a
quite powerful regularizing method. It defines an iterative
regularizing method where the smoother itself has to be an
iterative regularizing method (e.g., conjugate gradient, Landweber,
conjugate gradient for normal equations, etc.).
More precisely, with respect to the smoother, the regularization
properties are improved and the total complexity is lower.
Furthermore, in several cases, when it is directly applied to the
system $A{\bf f}={\bf g}$, the quality of the restored image is
comparable with that of all the best known techniques for the
normal equations $A^TA{\bf f}=A^T{\bf g}$, but the related
convergence is substantially faster. Finally, the associated
curves of the relative errors versus the iteration numbers are
``flatter'' with respect to the smoother
(the estimation of the stop iteration is less crucial).
Therefore, we
can choose multigrid procedures which are much more efficient than
classical techniques without losing accuracy in the restored image
(as often occurs when using preconditioning). Several numerical
experiments show the effectiveness of our proposals.