A generalized Levinson algorithm for covariance extension with application to multiscale autoregressive modeling
Austin B. Frakt, H. Lev-Ari, Alan S. Willsky · IEEE Transactions on Information Theory · 2003
Efficient computation of extensions of banded, partially known covariance matrices is provided by the classical Levinson algorithm. One contribution of this paper is the introduction of a generalization of this algorithm that is applicable to a substantially broader class of extension problems. This generalized algorithm can compute unknown covariance elements in any order that satisfies certain graph-theoretic properties, which we describe. This flexibility, which is not provided by the classical Levinson algorithm, is then harnessed in a second contribution of this paper, the identification of a multiscale autoregressive (MAR) model for the maximum-entropy (ME) extension of a banded, partially known covariance matrix. The computational complexity of MAR model identification is an order of magnitude below that of explicitly computing a full covariance extension and is comparable to that required to build a standard autoregressive (AR) model using the classical Levinson algorithm.