Displacement Preconditioner For Toeplitz Least Squares Iterations

Hon Fu Raymond CHAN, James G. NAGY, Robert J. PLEMMONS

Research output: Journal PublicationsJournal Article (refereed)peer-review


We consider the solution of least squares problems min||b−Ax||2 by the preconditioned conjugate gradient (PCG) method, for m × n complex Toeplitz matrices A of rank n. A circulant preconditioner C is derived using the T. Chan optimal preconditioner for n × 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π-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α), α > 0, then the least squares conjugate gradient method converges in at most O(α 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(αm log2 n + m log n). Conditions for superlinear convergence are given and numerical examples are provided illustrating the effectiveness of our methods.
Original languageEnglish
Pages (from-to)44-56
Number of pages13
JournalElectronic Transactions on Numerical Analysis
Publication statusPublished - Mar 1994
Externally publishedYes


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


Dive into the research topics of 'Displacement Preconditioner For Toeplitz Least Squares Iterations'. Together they form a unique fingerprint.

Cite this