AR Algorithms

Autoregressive estimation algorithms are used in:

· AR (AutoRegressive) Spectrum (Spectral menu)

· AR Spectrum with Order Exploration (Spectral menu)

· AR Spectrum with Algorithm Comparison (Spectral menu)

· Parametric Interpolation and Prediction (Process menu)

An AR spectrum is also available in the Eigendecomposition Filtering and Reconstruction procedure in the Process menu.

The AR coefficients can be computed in a variety of ways. The coefficients can be computed from autocorrelation estimates, from partial autocorrelation (reflection) coefficients, and from least-squares matrix procedures. Further, an AR model using the autocorrelation method will depend on the truncation threshold (maximum lag) used to compute the correlations. The partial autocorrelation method will depend on the specific definition for the reflection coefficient. The least-squares methods will also yield results that are a function of how data are treated at the bounds (matrix size) as well as whether the data matrix or normal equations are fitted.

Excellent coverage of AR spectral algorithms can be found in the following references:

· S. Lawrence Marple, Jr., "Digital Spectral Analysis with Applications", Prentice-Hall, 1987, p.172-284.

· Steven M. Kay, "Modern Spectral Estimation", Prentice Hall, 1988, p.153-270.

Also of interest may be the Burg algorithm information in:

· W. H. Press, et. al, "Numerical Recipes in C", Cambridge University Press, 1992, p.564-575.

Autocorrelation Method

The single autocorrelation based algorithm, AutoCorr, offers the least resolution. Endpoint effects arise from the lag-truncated autocorrelation sequence estimate (the infinite ACS is approximated by a finite subset). This is the AR algorithm found in many time-series and statistics packages. It is sometimes known as the Yule-Walker method. The biased algorithm used here always results in a stable AR filter (roots are all within the unit circle). Since a recursion is used, the coefficients for all lower orders are also computed.

Versions of the Autocorrelation AR procedure can be found in the STARPAC public domain time series package, and also in the Marple (p.239) and Kay (p. 260) references. AutoSignal's AutoCorr procedure follows the STARPAC implementation.

Maximum Entropy Method

The Burg algorithm is probably the most widely known AR procedure. Because of its derivation in the context of maximum entropy methods, the algorithm is sometimes designated "MEM". The procedure computes the AR coefficients directly from the data by estimating the reflection coefficients (partial autocorrelations) at successive orders. Since the computed coefficients are the harmonic mean between the forward and backward partial autocorrelation estimates, the Burg procedure is also known as the "Harmonic" algorithm. The algorithm will exhibit some bias in estimating the central frequencies of sine components, and higher order fits are notorious for "splitting", a phenomenon where multiple spectral peaks are generated where only a single feature is present. The Burg method also produces stable AR coefficients with roots inside or on the unit circle. It is recursive as well, and computes the coefficients for lesser orders en route to the solution.

Versions of the Burg procedure can be found in the CMLIB public domain time series package, and also in the Marple (p.240) and Kay (p. 265) references. A version of the Burg procedure can be found in the Press reference. AutoSignal's Burg procedure follows the CMLIB algorithm.

Least-Squares Algorithms

The remaining methods involve simultaneous least-squares estimates of all AR coefficients in the model. The Nrml models implement the normal equations used in typical least-squares estimations. Square matrices are formed using sums of forward or backward data elements.

The Nrml Fwd, Nrml Bwd, and Nrml FB are the forward prediction, backward prediction, and forward-backward prediction variants of the least-squares normal equations approach. The sums incur a loss of precision that can result in reduced resolution (compared to direct data methods) and lessened stability of the coefficients. When some noise is present, however, the normal equations generally yield viable results. These algorithms compute the coefficients only for the order specified.

The Data models implement the "covariance" or "modified covariance" methods of linear prediction. The covariance in this context has nothing to do with fitting a covariance matrix. Rather the full data or trajectory matrix, usually rectangular, is fitted directly to the vector of data elements. This approach incurs no loss of precision, but can involve lengthy fits with large data sets.

The Data Fwd, Data Bwd, and Data FB use fast algorithms that exploit the symmetry of the data matrix. These algorithms will produce optimum least-squares AR fits without the precision losses characteristic of the normal equations approach. Further, the algorithms also compute the coefficients for all lesser model orders. For the basic AR methods, the Data FB algorithm is likely to be the most accurate frequency estimator for undamped sinusoids (Data Fwd for damped sinusoids).

Versions of the "covariance" method can be found in the Marple (p.258) and Kay (p. 262) books; versions of the "modified covariance" method can also be found in Marple (p.248) and Kay (p. 262). AutoSignal's Data procedures follow the Marple algorithms. The normal equation procedures are original algorithms authored for AutoSignal.

SVD Based Least-Squares Algorithms

Within AutoSignal’s AR procedures, there is no count or threshold selection of peaks. The power spectrum for an AR model is an all-pole polynomial. Peaks will occur exactly at frequencies corresponding to roots in the polynomial.

AutoSignal’s AR procedures have been designed to facilitate the use of the SVD (singular value decomposition) routines. For non-SVD algorithms, all of the poles are treated as relevant peaks and analyzed accordingly in the linear least-squares component fitting in the Numeric Summary. This full count is also the default in the Non-Linear Optimization procedure. To pare the spectrum to only the signal components of interest, an SVD algorithm must be used.

For each of the least-squares procedures, there is an SVD version. Apart from longer processing times, there are no disadvantages to using an SVD procedure, and the advantages are numerous when extracting harmonics is the primary aim of the modeling. A full signal space SVD fit, one where the signal space equals the model order, produces the same results as the non-SVD algorithms.

The Graphically Select Signal and Noise Subspaces option is available only to SVD procedures.

For sinusoidal retrieval, the Data Svd FB is a superb algorithm. It is similar to the Principal Component AR (PCAR) procedure. The forward prediction version is the Data Svd Fwd and the backward prediction version is the Data Svd Bwd. For large data sets, the Data Svd procedures can be quite slow. If there is noise present (which is why SVD is used in the first place), the normal equations equivalents Nrml Svd FB, Nrml Svd Fwd, Nrml Svd Bwd, will produce similar results far more swiftly.

Most of the AR algorithms in AutoSignal are least-squares procedures since these produce the best spectral estimates. Least-squares methods that offer in-situ separation of signal and noise through singular value decomposition (SVD) are the most robust of AutoSignal’s AR methods. These algorithms are built-into the AR procedures (there is, for example, no separate Principal Component AutoRegressive or PCAR option).

All of the SVD-based procedures are original algorithms authored for AutoSignal.

AR Filter

When AutoSignal computes the statistics for any AR model fit, a consistent filter is used. This enables all algorithms to be compared using a common reference. The filter is not strictly forward, backward, or forward-backward prediction. Instead it is a forward prediction with a partial backward component. The AR filter is defined using backward prediction from the model order down to the initial data element, and forward prediction from the model order up to the final data element. Using this filter, a single estimate is thus made for each of the input data elements. There is no gap at one end of the data stream as is true of a forward or backward filter, nor are there two estimates for the data elements away from the bounds as is true for a forward-backward prediction.

This filter simplifes the goodness of fit statistics since the degree of freedom is preserved (the data length minus the AR coefficient count). The statistics in the AR algorithms throughout AutoSignal reflect this approach, although none of the linear AR algorithms specifically optimizes this particular merit function. Only a non-linear ARMA fit, with the MA order set to 0, will directly optimize this particular AR filter. This means that the ARMA procedure’s results for an AR-only fit will in general show a slightly better goodness of fit than all of the AR linear fits, but only due to how this merit function is defined.