Preconditioners based on fit techniques for the iterative regularization in the image deconvolution problem

For large-scale image reconstruction problems, the iterative regular- ization methods can be favorable alternatives to the direct methods. We analyze preconditioners for regularizinggradient-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 conjunc- tion with CG. The cost of this preconditioner is of O(n2 ) operations per iteration, where n2 is the pixels number of the image, whereas the cost of the circulant preconditioners commonly used for this type of problems is of O(n2 log n) operations per iteration. In this paper the extension of the fit preconditioner to more general cases is proposed: namely the nonsepa- rable positive definite case and the symmetric indefinite case. The ma jor difficulty encountered in this extension concerns the factorization phase, where a further approximation is required. Three approximate factoriza- tions are proposed. The preconditioners thus obtained have still a cost of O(n2 ) 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.