A fast algorithm for Toeplitz-block-Toeplitz linear systems
Author:
- 13 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3, 1929-1932
Abstract
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/sup 2//spl times/M/sup 2/ TBT matrix with M M/spl times/M Toeplitz blocks along each edge, the algorithm requires only O(6M/sup 3/) operations to solve an M/sup 2//spl times/M/sup 2/ 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.Keywords
This publication has 3 references indexed in Scilit:
- An explicit closed-form solution to the limited-angle discrete tomography problem for finite-support objectsInternational Journal of Imaging Systems and Technology, 1998
- A fast algorithm for extrapolation of discrete-time periodic band-limited signalsSignal Processing, 1993
- Efficient inversion of Toeplitz-block Toeplitz matrixIEEE Transactions on Acoustics, Speech, and Signal Processing, 1983