Note 71. Fitting All-Pole Models to Deterministic Signals: Covariance Method

This note describes the covariance method for finding the parameters needed to fit an all-pole model to a finite sequence of samples obtained from a deterministic signal.

The covariance method is a technique for fitting an all-pole model to a deterministic signal that is assumed to be auto regressive, but where knowledge about the signal is limited to a sequence of N samples, x[0] through x[N –1]. This method is an alternative to the autocorrelation method described in Note 70. Rather than optimizing the total error over all non-negative n and assuming that x[n] = 0 for n outside the interval [0, n –1], as the autocorrelation method does, the covariance method is based on minimizing the error over only those values of n for which the error can be evaluated from the known data sequence x[0], x[1], . . ., x[N –1]. Under these constraints, the matrix appearing in the normal equations is not Toeplitz, and consequently the Levinson-Durbin recursion cannot be used to solve for the coefficients, a_p[k].

71.1. Background

In the autocorrelation method discussed in Note 70, the error to be minimized is

71.1

where

71.2

Ouitside of the range, 0 ≤ n ≤ N –1, the value for x[n] is assumed to be zero. The covariance method minimizes the error only over the range of indices for which the necessary values of x[n] are available. Computing e[n] for values of n less than p requires values of x[n] for n less than zero; therefore the lower limit on the summation in Eq. (71.1) must be changed to p. Similarly, computing e[n] for n > N –1 requires values of x[n] for n > N –1, so the upper limit on the summation must be changed to N –1. Under these constraints, the error to be minimized becomes

71.3

Using this criterion results in the normal equations

71.4

where

and

71.5

The matrix in Eq. (71.4) has the properties of a covariance matrix, but it is not really a covariance matrix according to the usual definition. Nevertheless, in most of the literature concerning linear prediction and speech processing, this matrix is referred to as a covariance matrix, and hence the method using this matrix is called the covariance method. The matrix is not Toeplitz, and therefore the Levinson-Durbin recursion cannot be used to solve for the coefficients a_p[k]. However, the matrix is Hermitian (conjugate symmetric), so Eq. (71.4) can be solved using Cholesky decomposition, which imposes a computational burden that is about half that of Gaussian elimination.

71.3. Notes Regarding Recipe 71.1

Morf, et al. [2] have shown that the form of the R matrix in Eq. (71.4) is the product of two non-square Toeplitz matrices, and that this fact can be exploited to devise an inversion algorithm that is not as efficient as the Levinson-Durbin recursion, but is more efficient than Cholesky decomposition.

Alternative derivations of similar algorithms are provided by McClellan in [3] and by Marple in [4] and [5]. The phrase “FIR System Identification” might make the title of Marple’s paper [4] seem unrelated to the problem of estimating coefficients for an IIR filter in an AR model. However, as discussed in Note 70, there is an equivalence between an FIR filter used for linear prediction and an IIR filter used for autoregressive modeling.

References

1. M. H. Hayes, Statistical Digital Signal Processing and Modeling, Wiley, 1996.

2. M. Morf, B. Dickinson, T. Kailath, and A. Viera, “Efficient Solution of Covariance Equations for Linear Prediction,” IEEE Trans. ASSP, vol. 25, no. 5, Oct. 1977, pp. 429–433.

3. J. H. McClellan, “Parametric Signal Modeling,” Chapter 1 in Advanced Topics in Signal Processing, J. S. Lim and A. V. Oppenheim, eds., Prentice Hall, 1988.

4. S. L. Marple, “Efficient Least Squares FIR System Identification,” IEEE Trans. ASSP, vol. 29, Feb. 1981, pp. 62–73.

5. S. L. Marple, Digital Spectral Analysis with Applications, Prentice Hall, 1987.