A fast algorithm for Toeplitz-block-Toeplitz linear systems

A Toeplitz-block-Toeplitz (TBT) matrix is block Toeplitz with Toeplitz blocks. TBT systems of equations arise in 2D interpolation, 2D linear prediction and 2D least-squares deconvolution problems. Although the doubly Toeplitz structure should be exploitable in a fast algorithm, existing fast algorithms only exploit the block Toeplitz structure, not the Toeplitz structure of the blocks. Iterative algorithms can employ the 2D FFT (fast Fourier transform), but usually take thousands of iterations to converge. We develop a new fast algorithm that assumes a smoothness constraint on the matrix entries. For an M²×M² TBT matrix with M M×M Toeplitz blocks along each edge, the algorithm requires only O(6M³) operations to solve an M²×M² linear system of equations; parallel computing on 2M processors can be performed on the algorithm as given. Two examples show the operation and performance of the algorithm