Preconditioners Based on Fit Techniques for the Iterative Regularization in the Image Deconvolution Problem

For large-scale image deconvolution problems, the iterative regularization methods can be favorable alternatives to the direct methods. We analyze preconditioners for regularizing gradient-type iterations applied to problems with 2D band Toeplitz coefficient matrix. For problems having separable and positive definite matrices, the fit preconditioner we have introduced in a previous paper has been shown to be effective in conjunction with CG. The cost of this preconditioner is of O(n²) operations per iteration, where n² is the pixels number of the image, whereas the cost of the circulant preconditioners commonly used for this type of problems is of O(n² log n) operations per iteration. In this paper the extension of the fit preconditioner to more general cases is proposed: namely the nonseparable positive definite case and the symmetric indefinite case. The major difficulty encountered in this extension concerns the factorization phase, where a further approximation is required. Three approximate factorizations are proposed. The preconditioners thus obtained have still a cost of O(n²) operations per iteration. A numerical experimentation shows that the fit preconditioners are competitive with the regularizing Chan preconditioner, both in the regularizing efficiency and the computational cost. AMS subject classification (2000) 65F10, 65F22.Received October 2003. Accepted December 2004. Communicated by Lars Eldén.