Linear prediction is a mathematical operation where future values of a discrete-time signal are estimated as a linear function of previous samples. Discrete time is non-continuous time. ... Signal processing is the processing, amplification and interpretation of signals, and deals with the analysis and manipulation of signals. ... In mathematics, a linear transformation (also called linear map or linear operator) is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. ...

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. Digital signal processing (DSP) is the study of signals in a digital representation and the processing methods of these signals. ... It has been suggested that this article or section be merged with Code Excited Linear Prediction. ... An FIR filter In electronics, a digital filter is an electronic filter (usually linear), in discrete time, that is implemented through digital electronic computation of digital signals. ... System analysis is the branch of electrical engineering that characterizes electrical systems and their properties. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... A mathematical model is an abstract model that uses mathematical language to describe the behaviour of a system. ... In mathematics, the term optimization, or mathematical programming, refers to the study of problems in which one seeks to minimize or maximize a real function by systematically choosing the values of real or integer variables from within an allowed set. ...

The prediction model

The most common representation is

where 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

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

where | | . | | is a suitable chosen vector [[norm (mathematics)|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 In mathematics, the root mean square or rms is a statistical measure of the magnitude of a varying quantity. ... A plot showing 100 random numbers with a hidden sine function, and an autocorrelation of the series on the bottom. ...

for 1 ≤ j ≤ p, where R is the autocorrelation of signal x_n, defined as A plot showing 100 random numbers with a hidden sine function, and an autocorrelation of the series on the bottom. ...

where E is the expected value. In the multi-dimensional case this corresponds to minimizing the L₂ norm. In probability theory the expected value (or mathematical expectation) of a random variable is the sum of the probability of each possible outcome of the experiment multiplied by its payoff (value). Thus, it represents the average amount one expects as the outcome of the random trial when identical odds are... In mathematics, the Lp and spaces are spaces of p-power integrable functions, and corresponding sequence spaces. ...

The above equations are called the normal equations or Yule-Walker equations. In matrix form the equations can be equivalently written as Linear least squares is a mathematical optimization technique to find an approximate solution for a system of linear equations that has no exact solution. ...

where the autocorrelation matrix R is a symmetric, circulant matrix with elements r_i,j = R(i − j), vector r is the autocorrelation vector r_j = R(j), and vector a is the parameter vector. In linear algebra, a circulant matrix is a special kind of Toeplitz matrix where each row vector is shifted one element to the right relative to the preceding row vector. ...

Another, more general, approach is to minimize

where we usually constrain the parameters a_i with a₀ = 1 to avoid the trivial solution. This constraint yields the same predictor as above but the normal equations are then

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

Optimisation of the parameters is a wide topic and a large number of other approaches have been proposed.

Still, the autocorrelation method is the most common and it is used, for example, for speech coding in the GSM standard. Speech coding is the compression of speech (into a code) for transmission with speech codecs that use audio signal processing and speech processing techniques. ... The Global System for Mobile communications (GSM: originally from Groupe Spécial Mobile) is the most popular standard for mobile phones in the world. ...

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. 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. It uses a special symmetrical property of parameter vectors on subsequent recursion levels. In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ... Levinson recursion is a mathematical procedure which recursively calculates the solution to a Toeplitz matrix. ... Norman Levinson (August 11, 1912 - October 10, 1975) was an American mathematician. ...

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.

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

See also

• Forecasting
• Prediction interval
• Deconvolution