Displacement preconditioner for Toeplitz least squares iterations

Chan, Raymond H. ; Nagy, James G. ; Plemmons, Robert J.

Electronic transactions on numerical analysis, Tome 2 (1994), pp. 44-56

Résumé

We consider the solution of least squares problems min ||b - Ax||2 by the preconditioned conjugate gradient (PCG) method, for m $\times n$ complex Toeplitz matrices A of rank n. A circulant preconditioner C is derived using the T. Chan optimal preconditioner for n $\times n$ matrices using the displacement representation of A$\ast A$. This allows the fast Fourier transform (FFT) to be used throughout the computations, for high numerical efficiency. Of course A$\ast 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\pi $-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\alpha ), \alpha > 0$, then the least squares conjugate gradient method converges in at most $O(\alpha \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(\alpha m log2 n + m \log n)$.

Détail

Classification : 65F10, 65F15
Keywords: circulant preconditioner, conjugate gradient, displacement representation, fast Fourier transform (FFT), Toeplitz operator