Volume 2, pp. 44-56, 1994.

Displacement preconditioner for Toeplitz least squares iterations

Raymond H. Chan, James G. Nagy, and Robert J. Plemmons

Abstract

We consider the solution of least squares problems $min||b-Ax|{|}_2$ by the preconditioned conjugate gradient (PCG) method, for $m\times n$ complex Toeplitz matrices $A$ of rank $n$. A circulant preconditioner $C$ is derived using the T. Chan optimal preconditioner for $n\times n$ matrices using the displacement representation of $A^{\ast }A$. This allows the fast Fourier transform (FFT) to be used throughout the computations, for high numerical efficiency. Of course $A^{\ast }A$ need never be formed explicitly. Displacement–based preconditioners have also been shown to be very effective in linear estimation and adaptive filtering. For Toeplitz matrices $A$ that are generated by $2\pi$-periodic continuous complex-valued functions without any zeros, we prove that the singular values of the preconditioned matrix $A{C}^{-1}$ are clustered around 1, for sufficiently large $n$. We show that if the condition number of $A$ is of $O(n^{\alpha })$, $\alpha >0$, then the least squares conjugate gradient method converges in at most $O(\alpha \log n+1)$ steps. Since each iteration requires only $O(m\log n)$ operations using the FFT, it follows that the total complexity of the algorithm is then only $O(\alpha m{\log }^{2}n+m\log n)$. Conditions for superlinear convergence are given and numerical examples are provided illustrating the effectiveness of our methods.

Full Text (PDF) [198 KB], BibTeX

Key words

circulant preconditioner, conjugate gradient,displacement representation, fast Fourier transform (FFT), Toeplitz operator.

AMS subject classifications

65F10, 65F15.