CIRCULANT PRECONDITIONED TOEPLITZ LEAST-SQUARES ITERATIONS

The authors consider the solution of least squares problems min parallel to b - Tx parallel to(2) by the preconditioned conjugate gradient method, for m-by-n complex Toeplitz matrices T of rank n. A circulant preconditioner C is derived using the T. Chan optimal preconditioner on n-by-n Toeplitz row blocks of T. For Toeplitz T that are generated by a 2 pi-periodic continuous complex-valued functions without any zeros, the authors prove that the singular values of the preconditioned matrix TC-1 are clustered around 1, for sufficiently large n. The paper shows that if the condition number of T is of O(n(alpha)), alpha > 0, then the least squares conjugate gradient method converges in at most O(cd alpha log n+1) steps. Since each iteration requires only O(m log n) operations using the Fast Fourier Transform, it follows that the total complexity of the algorithm is then only O(alpha m log(2) n+m log n). Conditions for superlinear convergence are given and regularization techniques leading to superlinear convergence for least squares computations with ill-conditioned Toeplitz matrices arising from inverse problems are derived. Numerical examples ace provided illustrating the effectiveness of the authors' methods.