Inverse Toeplitz Preconditioners for Ill-Posed Problems

M. Hanke and J. Nagy

It has been shown recently that iterative regularization using conjugate gradient type methods for image restoration problems can be effectively preconditioned with circulant approximations. Here it is shown that the theoretical properties of this approach are not restricted to circulant matrices. Specifically, a Toeplitz approximate inverse preconditioning scheme for discrete ill-posed problems is considered. It is proved that the preconditioned system approximates the prolate matrix, and that this property implies that fast convergence of conjugate gradient type methods can be expected. In addition, it is shown that these results can be generalized to two-dimensional problems. An image restoration application is used to demonstrate the properties of the preconditioner.