Generalization of Strang's preconditioner with applications to Toeplitz least squares problems

In this paper, we propose a method to generalize Strang's circulant preconditioner for arbitrary n-by-n matrices A_n. The [n/2] th column of our circulant preconditioned S_n is equal to the [n/2 ]th column of the given matrix A_n. Thus if A_n is a square Toeplitz matrix, then S_n is just the Strang circulant preconditioner. When S_n is not Hermitian, our circulant preconditioner can be defined as (S_n*S_n) ^1/2. This construction is similar to the forward-backward projection method used in constructing preconditioners for tomographic inversion problems in medical imaging. We show that if the matrix A_n has decaying coefficients away from the main diagonal, then (S_n*S_n) ^1/2 is a good preconditioner for A_n. Comparisons of our preconditioner with other circulant-based preconditioners are carried out for some 1-D Toeplitz least squares problems: min ||b - Ax ||₂ . Preliminary numerical results show that our preconditioner performs quite well, in comparison to other circulant preconditioners. Promising test results are also reported for a 2-D deconvolution problem arising in ground-based atmospheric imaging.