Efficient computation of tr{TR-1} for Toeplitz matrices

Author

Dias, José M B ; Leitão, José M N

Author_Institution

Instituto de Telecomunicacoes, Instituto Superior Tecnico, Lisbon, Portugal

Volume

9

Issue

2

fYear

2002

Firstpage

54

Lastpage

56

Abstract

An efficient algorithm for the computation of tr{TR/sup -1/}, where T and R are Toeplitz matrices and R is also symmetric positive definite, is presented. The method exploits the fact that the trace of TR/sup -1/ depends only on the sum of the diagonals of R/sup -1/, and not on the whole matrix R/sup -1/. To obtain this sum, a fast efficient technique, built upon the Trench (1964) algorithm for computing the inverse of a Toeplitz matrix, is developed. The complexity of the algorithm depends on the generation function of matrix R and is O(N ln N) for generic functions and O(p ln p) for AR(p) functions.

Keywords

Toeplitz matrices; communication complexity; matrix inversion; signal processing; Toeplitz matrices; Trench algorithm; algorithm complexity; autoregressive processes; diagonal sum; efficient computation; generic functions; inverse Toeplitz matrix; signal processing; symmetric positive definite matrix; Channel estimation; Covariance matrix; Fast Fourier transforms; Gaussian processes; Information analysis; Polynomials; Signal processing algorithms; Symmetric matrices; Telecommunications;

fLanguage

English

Journal_Title

Signal Processing Letters, IEEE

Publisher

ieee

ISSN

1070-9908

Type

jour

DOI

10.1109/97.991137

Filename

991137