| Home > Publications > Reports > Numerical Analysis and Applied Mathematics (TW) |
TW 493
Nicola Mastronardi, Marc Van Barel, Raf Vandebril
A fast algorithm for computing the smallest eigenvalue of a symmetric positve definite Toeplitz matrix
Abstract
Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive definite Toeplitz matrix. Several algorithms have been proposed in the literature. Many of them compute the smallest eigenvalue in an iterative fashion, relying on the Levinson-Durbin solution of sequences of Yule-Walker systems. Exploiting the properties of two algorithms recently developed for estimating a lower and an upper bound of the smallest singular value of upper triangular matrices, respectively, an algorithm for computing bounds to the smallest eigenvalue of a symmetric positive definite Toeplitz matrix has been recently derived. The algorithm relies on the computation of the R factor of the QR-factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R-1 is efficiently accomplished by the generalized Schur algorithm. Unfortunately, due to the weak stability of the generalized Schur algorithm, only a rough approximation of the smallest eigenvalue can be computed. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of symmetric positive definite Toeplitz matrices in an accurate way is proposed.
report.pdf (311K) / mailto: M. Van Barel