New fast preconditioners for Toeplitz-like linear systems

Toeplitz-like matrices are matrices that are Toeplitz, block Toeplitz with Toeplitz blocks, and mosaic Toeplitz (Toeplitz blocks of different sizes). Toeplitz-like systems of equations arise in 2-D interpolation, 2-D linear prediction, and 2-D least-squares deconvolution. In this paper, we use the Woodbury formula to reformulate a Toeplitz-like system of equations into a circulant-plus-diagonal system, and use the discrete Fourier transform to transform this into a banded system which can be solved quickly and which requires little storage. We propose the use of this as a preconditioner for Toeplitz-like systems, as an alternative to the circulant-block-circulant preconditioner commonly used for Toeplitz-block-Toeplitz systems. Using condition number as a figure-of-merit, this preconditioner seems to work much better for Toeplitz matrices than the usual circulant preconditioner.