Volume 2, pp. 44-56, 1994.

Displacement preconditioner for Toeplitz least squares iterations

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


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^*A$. This allows the fast Fourier transform (FFT) to be used throughout the computations, for high numerical efficiency. Of course $A^*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 $AC^{-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^2n + 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]

Key words

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

AMS subject classifications

65F10, 65F15.

< Back