Donatelli, Marco; Serra-Capizzano, Stefano On the regularizing power of multigrid-type algorithms. (English) Zbl 1103.65043 SIAM J. Sci. Comput. 27, No. 6, 2053-2076 (2006). Summary: 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{\mathbf f}={\mathbf g}\), the quality of the restored image is comparable with that of all the best known techniques for the normal equations \(A^TA{\mathbf f}=A^T{\mathbf 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. Cited in 1 ReviewCited in 13 Documents MSC: 65F22 Ill-posedness and regularization problems in numerical linear algebra 65F10 Iterative numerical methods for linear systems 94A08 Image processing (compression, reconstruction, etc.) in information and communication theory Keywords:image restoration; iterative regularization methods; algebraic multigrid; geometric multigrid; numerical experiments PDFBibTeX XMLCite \textit{M. Donatelli} and \textit{S. Serra-Capizzano}, SIAM J. Sci. Comput. 27, No. 6, 2053--2076 (2006; Zbl 1103.65043) Full Text: DOI Link