Cauchy-like preconditioners for two-dimensional ill-posed problems

Ill-conditioned matrices with block Toeplitz, Toeplitz block (BTTB) structu re arise from the discretization of certain ill-posed problems in signal an d image processing. We use a preconditioned conjugate gradient algorithm to compute a regularized solution to this linear system given noisy data. Our preconditioner is a Cauchy-like block diagonal approximation to a unitary transformation of the BTTB matrix. We show that the preconditioner has desi rable properties when the kernel of the ill-posed problem is smooth: the la rgest singular values of the preconditioned matrix are clustered around one , the smallest singular values remain small, and the subspaces correspondin g to the largest and smallest singular values, respectively, remain unmixed . For a system involving np variables, the preconditioned algorithm costs o nly O(np(lg n + lg p)) operations per iteration. We demonstrate the effecti veness of the preconditioner on three examples.