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 most common representation is
\widehat{x}(n)=
p | |
\sum | |
i=1 |
aix(n-i)
where
\widehat{x}(n)
x(n-i)
p\leqn
ai
e(n)=x(n)-\widehat{x}(n)
where
x(n)
These equations are valid for all types of (one-dimensional) linear prediction. The differences are found in the way the predictor coefficients
ai
For multi-dimensional signals the error metric is often defined as
e(n)=\|x(n)-\widehat{x}(n)\|
where
\| ⋅ \|
\widehat{x}(n)
The most common choice in optimization of parameters
ai
E[e2(n)]
p | |
\sum | |
i=1 |
aiR(j-i)=R(j),
for 1 ≤ j ≤ p, where R is the autocorrelation of signal xn, defined as
R(i)=E\{x(n)x(n-i)\}
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
RA=r
where the autocorrelation matrix
R
p x p
rij=R(i-j),0\leqi,j<p
r
rj=R(j),0<j\leqp
A=[a1,a2, … ,ap-1,ap]
Another, more general, approach is to minimize the sum of squares of the errors defined in the form
e(n)=x(n)-\widehat{x}(n)=x(n)-
p | |
\sum | |
i=1 |
aix(n-i)=-
p | |
\sum | |
i=0 |
aix(n-i)
where the optimisation problem searching over all
ai
a0=-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
RA=[1,0,...,0]T
where the index
i
p
R
(p+1) x (p+1)
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[2] and it is used, for example, for speech coding in the GSM standard.
Solution of the matrix equation
RA=r
R
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.[4] It uses a special symmetrical property of parameter vectors on subsequent recursion levels. That is, calculations for the optimal predictor containing
p
p-1
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
p-1,
ai
p
\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}