Generalization of Strang's Preconditioner with Applications to Toeplitz Least Squares Problems

✍ Scribed by Raymond H. Chan; Michael K. Ng; Robert J. Plemmons

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 969 KB
• Volume: 3
• Category: Article
• ISSN: 1070-5325
• DOI: 10.1002/(sici)1099-1506(199601/02)3:1<45::aid-nla70>3.0.co;2-t

✦ Synopsis

In this paper, we propose a method to generalize Strang's circulant preconditioner for arbitrary n-by-n matrices A,,. The 181th column of our circulant preconditioner S,, is equal to the 151 th column of the given matrix A,,. Thus if A,, is a square Toeplitz matrix, then S,, is just the Strang circulant preconditioner. When S,, is not Hermitian, our circulant preconditioner can be defined as (S,*Sn)'/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 , has decayingcoefficients away from the main diagonal, then (S,*S,,)'/2 is a good preconditioner for A,, . Comparisons of our preconditioner with other circulant-based preconditioners are carried out for some 1-D Toeplitz least squares problems: min 11 b -Ax 112.

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.