Toeplitz matrices are of interest and practical importance in many areas of signal processing. In particular, adaptive algorithms repetitively solve a set of time varying normal equations which have a coefficient matrix which is Toeplitz or a product of Toeplitz. These algorithms normally exploit the Toeplitz structure to achieve high speeds with a reasonable amount of hardware.
The aim and purpose of this dissertation is to examine the structure and properties of the Toeplitz matrix by examining the properties of member matrices in additive Toeplitz decompositions. New and novel decompositions are generated using projection techniques onto class space with and without constraint. The decompositions are then studied to determine which ones yield member matrices with useful structures and properties.
A very useful decomposition results from projecting a Toeplitz matrix onto right circulant class space with a normality constraint placed on the residue matrix. One member matrix is thereby constrained to be right circulant and the other member is contained in a new class of matrices denoted as the sign skew right circulant class.
The eigenvectors and eigenvalues of both classes are studied and shown to be closely related and also have associated fast algorithms for their computation. The fast algorithms associated with the sign skew right circulant are based on a new "time to frequency" transformation which is denoted as the DFT'. The DFT' is shown to be closely related to the DFT (Discrete Fourier Transform) and, therefore, can be computed efficiently using the FFT (Fast Fourier Transform).
The decomposition is directly beneficial where sums and products of the two classes are required, as for example when determining the product of two Toeplitz matrices. Some adaptive iterative algorithms require such products in which case the time per iteration can be substantially reduced. A simulation of an iterative least mean squares adaptive algorithm with an update time of order (log N) is demonstrated. Once tracking is accomplished, accurate updates are achieved in (2 log N) multiplication times using an FFT implementation for the matrix-vector products.