Circulant Preconditioned Toeplitz Least Squares Iterations

The authors consider the solution of least squares problems min ‖b - Tx‖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. Chars optimal preconditioner on n-by-n Toeplitz row blocks of T. For Toeplitz T that are generated by 2π-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α), α > 0, then the least squares conjugate gradient method converges in at most O(cdα 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(αm log2 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 are provided illustrating the effectiveness of the authors’ methods.