DISPLACEMENT PRECONDITIONER FOR TOEPLITZ LEAST SQUARES ITERATIONS
Raymond Hon-Fu Chan, James G. Nagy, Robert J. Plemmons · 1994
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 su#ciently 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. Si...