Linear prediction

Linear prediction

Discussion

Encyclopedia
Linear prediction is a mathematical operation where future values of a discrete-time
Discrete time
Discrete time is the discontinuity of a function's time domain that results from sampling a variable at a finite interval. For example, consider a newspaper that reports the price of crude oil once every day at 6:00AM. The newspaper is described as sampling the cost at a frequency of once per 24...

signal
Signal processing
Signal processing is an area of systems engineering, electrical engineering and applied mathematics that deals with operations on or analysis of signals, in either discrete or continuous time...

are estimated as a linear function
Linear transformation
In mathematics, a linear map, linear mapping, linear transformation, or linear operator is a function between two vector spaces that preserves the operations of vector addition and scalar multiplication. As a result, it always maps straight lines to straight lines or 0...

of previous samples.

In digital signal processing
Digital signal processing
Digital signal processing is concerned with the representation of discrete time signals by a sequence of numbers or symbols and the processing of these signals. Digital signal processing and analog signal processing are subfields of signal processing...

, linear prediction is often called linear predictive coding
Linear predictive coding
Linear predictive coding is a tool used mostly in audio signal processing and speech processing for representing the spectral envelope of a digital signal of speech in compressed form, using the information of a linear predictive model...

(LPC) and can thus be viewed as a subset of filter theory. In system analysis
System analysis
System analysis in the field of electrical engineering characterizes electrical systems and their properties. System Analysis can be used to represent almost anything from population growth to audio speakers, electrical engineers often use it because of its direct relevance to many areas of their...

(a subfield of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

), linear prediction can be viewed as a part of mathematical model
Mathematical model
A mathematical model is a description of a system using mathematical concepts and language. The process of developing a mathematical model is termed mathematical modeling. Mathematical models are used not only in the natural sciences and engineering disciplines A mathematical model is a...

ling or optimization
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....

.

The prediction model

The most common representation is

where is the predicted signal value, the previous observed values, and the predictor coefficients. The error generated by this estimate is

where 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 are chosen.

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

where is a suitable chosen vector norm
Norm (mathematics)
In linear algebra, functional analysis and related areas of mathematics, a norm is a function that assigns a strictly positive length or size to all vectors in a vector space, other than the zero vector...

.

Estimating the parameters

The most common choice in optimization of parameters is the root mean square
Root mean square
In mathematics, the root mean square , also known as the quadratic mean, is a statistical measure of the magnitude of a varying quantity. It is especially useful when variates are positive and negative, e.g., sinusoids...

criterion which is also called the autocorrelation
Autocorrelation
Autocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...

criterion. In this method we minimize the expected value of the squared error E[e2(n)], which yields the equation

for 1 ≤ jp, where R is the autocorrelation
Autocorrelation
Autocorrelation is the cross-correlation of a signal with itself. Informally, it is the similarity between observations as a function of the time separation between them...

of signal xn, defined as
,

and E is the expected value
Expected value
In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

. In the multi-dimensional case this corresponds to minimizing the L2 norm
Lp space
In mathematics, the Lp spaces are function spaces defined using a natural generalization of the p-norm for finite-dimensional vector spaces...

.

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

where the autocorrelation matrix R is a symmetric, p×p Toeplitz matrix
Toeplitz matrix
In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant...

with elements ri,j = R(ij), 0≤i,jr is the autocorrelation vector rj = R(j), 0a is the parameter vector.

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

where the optimisation problem searching over all must now be constrained with . 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.

Specification of the parameters of the linear predictor 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
Speech coding
Speech coding is the application of data compression of digital audio signals containing speech. Speech coding uses speech-specific parameter estimation using audio signal processing techniques to model the speech signal, combined with generic data compression algorithms to represent the resulting...

in the GSM
Global System for Mobile Communications
GSM , is a standard set developed by the European Telecommunications Standards Institute to describe technologies for second generation digital cellular networks...

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
Levinson recursion
Levinson recursion or Levinson-Durbin recursion is a procedure in linear algebra to recursively calculate the solution to an equation involving a Toeplitz matrix...

proposed by Norman Levinson
Norman Levinson
Norman Levinson was an American mathematician. Some of his major contributions were in the study of Fourier transforms, complex analysis, non-linear differential equations, number theory, and signal processing. He worked closely with Norbert Wiener in his early career...

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. That is, calculations for the optimal predictor containing p terms make use of similar calculations for the optimal predictor containing p − 1 terms.

• Autoregressive model
Autoregressive model
In statistics and signal processing, an autoregressive model is a type of random process which is often used to model and predict various types of natural phenomena...

• Prediction interval
Prediction interval
In statistical inference, specifically predictive inference, a prediction interval is an estimate of an interval in which future observations will fall, with a certain probability, given what has already been observed...

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.