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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\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, with $p\leq n$, and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{i}} the predictor coefficients. The error generated by this estimate is

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e(n)=x(n)-{\widehat {x}}(n)\,}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 predictor coefficients Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{i}} are chosen.

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e(n)=\|x(n)-{\widehat {x}}(n)\|\,}

where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|\cdot \|} is a suitable chosen vector norm. Predictions such as Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle {\widehat {x}}(n)} are routinely used within Kalman filters and smoothers to estimate current and past signal values, respectively, from noisy measurements.

Estimating the parameters

The most common choice in optimization of parameters Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E[e^{2}(n)]} , which yields the equation

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ 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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf {RA} =\mathbf {r} }

where the autocorrelation matrix Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf {R} } is a symmetric, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p\times p} Toeplitz matrix with elements Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{ij}=R(i-j),0\leq i,j<p} , the vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf {r} } is the autocorrelation vector Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r_{j}=R(j),0<j\leq p} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf {A} =[a_{1},a_{2},\,\cdots \,,a_{p-1},a_{p}]} , the parameter vector.

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

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{i}} must now be constrained with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{0}=-1} .

On the other hand, if the mean square prediction error is constrained to be unity and the prediction error equation is included on top of the normal equations, the augmented set of equations is obtained as

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ \mathbf {RA} =[1,0,...,0]^{\mathrm {T} }}

where the index Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle i} ranges from 0 to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf {R} } is a Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p+1)\times (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. In fact, 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf {RA} =\mathbf {r} } is computationally a relatively expensive process. The Gaussian elimination for matrix inversion is probably the oldest solution but this approach does not efficiently use the symmetry of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf {R} } . A faster algorithm is the Levinson recursion proposed by Norman Levinson in 1947, which recursively calculates the solution, running in O(n²) time (vs O(n³) for Gaussian elimination). In particular, the autocorrelation equations above may be more efficiently solved by the Durbin algorithm.

In 1986, Philippe Delsarte and Y.V. Genin 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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} terms make use of similar calculations for the optimal predictor containing Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p-1} terms.

Another way of identifying model parameters is to iteratively calculate state estimates using Kalman filters and obtaining maximum likelihood estimates within expectation–maximization algorithms.

For equally-spaced values, a polynomial interpolation is a linear combination of the known values. If the discrete time signal is estimated to obey a polynomial of degree Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle p-1,} then the predictor coefficients Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{i}} are given by the corresponding row of the triangle of binomial transform coefficients. This estimate might be suitable for a slowly varying signal with low noise. The predictions for the first few values of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} are

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\begin{array}{lcl}p=1&:&{\widehat {x}}(n)=1x(n-1)\\p=2&:&{\widehat {x}}(n)=2x(n-1)-1x(n-2)\\p=3&:&{\widehat {x}}(n)=3x(n-1)-3x(n-2)+1x(n-3)\\p=4&:&{\widehat {x}}(n)=4x(n-1)-6x(n-2)+4x(n-3)-1x(n-4)\\\end{array}}}

See also

• Autoregressive model
• Linear predictive analysis
• Minimum mean square error
• Prediction interval
• Rasta filtering

Further reading

• Hayes, M. H. (1996). Statistical Digital Signal Processing and Modeling. New York: J. Wiley & Sons. ISBN 978-0471594314.
• Levinson, N. (1947). "The Wiener RMS (root mean square) error criterion in filter design and prediction". Journal of Mathematics and Physics. 25 (4): 261–278. doi:10.1002/sapm1946251261.
• Makhoul, J. (1975). "Linear prediction: A tutorial review". Proceedings of the IEEE. 63 (5): 561–580. doi:10.1109/PROC.1975.9792.
• Yule, G. U. (1927). "On a Method of Investigating Periodicities in Disturbed Series, with Special Reference to Wolfer's Sunspot Numbers". Phil. Trans. Roy. Soc. A. 226 (636–646): 267–298. Bibcode:1927RSPTA.226..267Y. doi:10.1098/rsta.1927.0007. JSTOR 91170.

External links

• PLP and RASTA (and MFCC, and inversion) in Matlab Archived 2016-11-22 at the Wayback Machine