Solution of Toeplitz normal equations by sine transform based preconditioning (Q1124782)

The normal equations constructed by a Toeplitz matrix are studied and a suitable preconditioner related to the discrete sine transform is found. New results about the structure of the product of two Toeplitz matrices are given. This allows the conjugate gradient method applied to the normal equations to achieve a superlinear rate of convergence. The proposed preconditioner outperforms the circulant one for the iterative solution of Toeplitz least squares problems. Such a strategy can also be applied to linear systems with nonsymmetric coefficient matrices. The block generalization of the algorithm is discussed which make the new technique applicable to some problems in multichannel signal processing and two-dimensional image restoration. Results and discussion from numerical experiments using MATLAB are given.