Displacement Preconditioner For Toeplitz Least Squares Iterations

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.