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\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...