Linear prediction

Linear prediction is a mathematical operation where future values of a discrete-time signal are estimated as a linear function of previous samples.

In digital signal processing, linear prediction is often called linear predictive coding (LPC) and can thus be viewed as a subset of filter theory. In system analysis (a subfield of mathematics), linear prediction can be viewed as a part of mathematical modelling or optimization.

The prediction model

The most common representation is

$\widehat{x}(n) = \sum_{i=1}^p a_i x(n-i)\,$

where $\widehat{x}(n)$ is the predicted signal value, $x(n-i)$ the previous observed values, and $a_i$ the predictor coefficients. The error generated by this estimate is

$e(n) = x(n) - \widehat{x}(n)\,$

where $x(n)$ is the true signal value.

These equations are valid for all types of (one-dimensional) linear prediction. The differences are found in the way the parameters $a_i$ are chosen.

For multi-dimensional signals the error metric is often defined as

$e(n) = \|x(n) - \widehat{x}(n)\|\,$

where $\|\cdot\|$ is a suitable chosen vector norm.

Estimating the parameters

The most common choice in optimization of parameters $a_i$ is the root mean square criterion which is also called the autocorrelation criterion. In this method we minimize the expected value of the squared error E[e²(n)], which yields the equation

$\sum_{i=1}^p a_i R(j-i) = -R(j),$

for 1 ≤ j ≤ p, where R is the autocorrelation of signal x_n, defined as

$\ R(i) = E\{x(n)x(n-i)\}\,$,

and E is the expected value. In the multi-dimensional case this corresponds to minimizing the L₂ norm.

The above equations are called the normal equations or Yule-Walker equations. In matrix form the equations can be equivalently written as

$Ra = -r,\,$

where the autocorrelation matrix R is a symmetric, p×p Toeplitz matrix with elements r_i,j = R(i − j), 0≤i,j<p, the vector r is the autocorrelation vector r_j = R(j), 0<j≤p, and the vector a is the parameter vector.

Another, more general, approach is to minimize the sum of squares of the errors defined in the form

$e(n) = x(n) - \widehat{x}(n) = x(n) - \sum_{i=1}^p a_i x(n-i) = - \sum_{i=0}^p a_i x(n-i)$

where the optimisation problem searching over all $a_i$ must now be constrained with $a_0=-1$. This constraint yields the same predictor as above but the normal equations are then

$\ Ra = [1, 0, ... , 0]^{\mathrm{T}}$

where the index i ranges from 0 to p, and R is a (p + 1) × (p + 1) matrix.

Specification of the parameters of the linear predictor is a wide topic and a large number of other approaches have been proposed.^{[citation needed]} Still, the autocorrelation method is the most common and it is used, for example, for speech coding in the GSM standard.

Solution of the matrix equation Ra = r is computationally a relatively expensive process. The Gauss algorithm for matrix inversion is probably the oldest solution but this approach does not efficiently use the symmetry of R and r. A faster algorithm is the Levinson recursion proposed by Norman Levinson in 1947, which recursively calculates the solution.^{[citation needed]} Later, Delsarte et al. proposed an improvement to this algorithm called the split Levinson recursion which requires about half the number of multiplications and divisions.^{[citation needed]} It uses a special symmetrical property of parameter vectors on subsequent recursion levels. That is, calculations for the optimal predictor containing p terms make use of similar calculations for the optimal predictor containing p − 1 terms.

See also

• Autoregressive model
• Prediction interval

References

Original

• G. U. Yule. "On a method of investigating periodicities in disturbed series, with special reference to wolfer’s sunspot numbers". Phil. Trans. Roy. Soc., 226-A:267–298, 1927.
• N. Levinson, “The Wiener RMS (root mean square) error criterion in filter design and prediction,” Journal of Mathematics and Physics, vol. 25, no. 4, pp. 261–278, January 1947.

Overview

• J. Makhoul. "Linear prediction: A tutorial review". Proceedings of the IEEE, 63 (5):561–580, April 1975.
• M. H. Hayes. Statistical Digital Signal Processing and Modeling. J. Wiley & Sons, Inc., New York, 1996.

External links

• PLP and RASTA (and MFCC, and inversion) in Matlab