Fast positive definite linear system solvers

Author

Tewfik, A.H. ; Kim, M.

Author_Institution

Dept. of Electr. Eng., Minnesota Univ., Minneapolis, MN, USA

Volume

42

Issue

3

fYear

1994

fDate

3/1/1994 12:00:00 AM

Firstpage

572

Lastpage

585

Abstract

The authors show that the M-band wavelet transforms of a wide class of covariance matrices consist of subblocks that are essentially banded. Furthermore, they prove that the Cholesky factors of the transformed covariance matrices also consist of subblocks that are essentially banded. They combine these two observations to construct a fast O(N²) algorithm for solving the N×N linear positive definite systems of equations that arise in statistical signal processing. Finally, they provide an error analysis of the proposed linear positive definite system solver

Keywords

error analysis; filtering and prediction theory; linear systems; matrix algebra; signal processing; statistical analysis; wavelet transforms; Cholesky factors; M-band wavelet transforms; covariance matrices; equations; error analysis; fast algorithm; linear positive definite system solver; perfect reconstruction filter banks; statistical signal processing; subblocks; transformed covariance matrices; Covariance matrix; Equations; Filter bank; Frequency; Karhunen-Loeve transforms; Linear systems; Signal processing; Signal processing algorithms; Sparse matrices; Stochastic processes;

fLanguage

English

Journal_Title

Signal Processing, IEEE Transactions on

Publisher

ieee

ISSN

1053-587X

Type

jour

DOI

10.1109/78.277849

Filename

277849