#### 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^*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