- Linear prediction
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
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.
Estimating the parameters
The most common choice in optimization of parameters is the
root mean squarecriterion which is also called the autocorrelationcriterion. 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
autocorrelationof signal "x""n", defined as
where "E" is the
expected value. In the multi-dimensional case this corresponds to minimizing the L2 norm.
The above equations are called the
normal equationsor Yule-Walker equations. In matrix form the equations can be equivalently written as
where the autocorrelation matrix "R" is a symmetric,
Toeplitz matrixwith elements "r""i","j" = "R"("i" − "j"), vector "r" is the autocorrelation vector "r""j" = "R"("j"), and vector "a" is the parameter vector.
Another, more general, approach is to minimize
where we usually constrain the parameters with 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 codingin the GSM standard.
Solution of the matrix equation "Ra" = "r" is computationally a relatively expensive process. The
Gauss algorithmfor 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 recursionproposed by Norman Levinsonin 1947, which recursively calculates the solution. Later, Delsarte et al. proposed an improvement to this algorithm called the split Levinson recursionwhich requires about half the number of multiplications and divisions. It uses a special symmetrical property of parameter vectors on subsequent recursion levels.
* 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.
* 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.
* [http://labrosa.ee.columbia.edu/matlab/rastamat/ PLP and RASTA (and MFCC, and inversion) in Matlab]
Wikimedia Foundation. 2010.