Levinson-Type Extensions for Non-Toeplitz Systems

Abstract

We show that Levinson's basic principle for the solution of normal equations which are of Toeplitz form may he extended to the case where these equations do not possess this specific symmetry. The use of Levinson's principle allows us to obtain a compact (2 x 2) form to express a system of equations of arbitrary order. This compact form is the key expression in the development of recursive algorithms and allows a compact representation of the most important Levinsontype algorithms which are used in the analysis of seismic and time series data in general. In the case when the coefficient matrix does not possess any type of special structure, the number of multiplications and divisions required in the inversion is n3 - 2n2 + 4n. We illustrate the described method by application to various examples which we have chosen so that the coefficient matrix possesses various symmetries. Specifically, we first consider the solution of the normal equations when the associated matrix is the doubly symmetric non-Toeplitz covariance matrix. Second, we obtain the solution of extended Yule-Walker equations where the coefficient matrix is Toeplitz but nonsymmetric. Finally, we briefly illustrate the approach by considering the determination of the prediction error operator when the NE are in fact of symmetric Toeplitz form.