Linear prediction
Encyclopedia
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 model
ling or optimization
.
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
.
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[e2(n)], which yields the equation
for 1 ≤ j ≤ p, where R is the autocorrelation
of signal xn, defined as
,
and E is the expected value
. In the multi-dimensional case this corresponds to minimizing the L2 norm
.
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
with elements ri,j = R(i − j), 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
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. 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.
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 iswhere
is the predicted signal value, the previous observed values, and the predictor coefficients. The error generated by this estimate iswhere
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 normNorm (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 squareRoot 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 ≤ j ≤ p, 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(i − j), 0≤i,j
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 thenwhere 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.
See also
- Autoregressive modelAutoregressive modelIn 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 intervalPrediction intervalIn 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.