Editing Linear prediction (section)

=== Estimating the parameters ===
The most common choice in optimization of parameters <math>a_i</math> 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 <math> E[e^2(n)]</math>, which yields the equation

:<math>\sum_{i=1}^p a_i R(j-i) = R(j),</math>

for 1 ≤ ''j'' &le; ''p'', where ''R'' is the [[autocorrelation]] of signal ''x''<sub>''n''</sub>, defined as

:<math>\ R(i) = E\{x(n)x(n-i)\}\,</math>,

and ''E'' is the [[expected value]].  In the multi-dimensional case this corresponds to minimizing the [[Lp space|L<sub>2</sub> norm]].

The above equations are called the [[normal equations]] or [[Autoregressive model#Yule–Walker equations|Yule-Walker equations]]. In matrix form the equations can be equivalently written as

:<math>\mathbf{R A} = \mathbf{r}</math>

where the autocorrelation matrix <math>\mathbf{R}</math> is a symmetric, <math>p \times p</math> [[Toeplitz matrix]] with elements <math> r_{ij} = R(i-j), 0 \leq i, j<p </math>, the vector <math>\mathbf{r}</math> is the autocorrelation vector <math> r_j = R(j), 0<j \leq p</math>, and <math>\mathbf{A} = [a_1, a_2, \,\cdots\, , a_{p-1}, a_p]</math>, the parameter vector.

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

:<math>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)</math>

where the optimisation problem searching over all <math>a_i</math> must now be constrained with <math>a_0=-1</math>.

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

:<math>\ \mathbf{R A} = [1, 0, ... , 0]^{\mathrm{T}}</math>

where the index <math>i</math> ranges from 0 to <math>p</math>, and <math>\mathbf{R}</math> is a <math>(p+1)\times(p+1)</math> 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<ref>{{Cite web |title=Linear Prediction - an overview {{!}} ScienceDirect Topics |url=https://www.sciencedirect.com/topics/mathematics/linear-prediction |access-date=2022-06-24 |website=www.sciencedirect.com}}</ref> and it is used, for example, for [[speech coding]] in the [[Global System for Mobile Communications|GSM]] standard.

Solution of the matrix equation <math>\mathbf{R A} = \mathbf{r}</math> 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 <math>\mathbf{R}</math>. A faster algorithm is the [[Levinson recursion]] proposed by [[Norman Levinson]] in 1947, which recursively calculates the solution.{{Citation needed|date=October 2010}} In particular, the autocorrelation equations above may be more efficiently solved by the Durbin algorithm.<ref>{{cite journal | last1 = Ramirez | first1 = M. A. | year = 2008 | title = A Levinson Algorithm Based on an Isometric Transformation of Durbin's | doi = 10.1109/LSP.2007.910319 | journal = IEEE Signal Processing Letters | volume = 15 | pages = 99–102 | bibcode = 2008ISPL...15...99R | s2cid = 18906207 |url=http://www.producao.usp.br/bitstream/handle/BDPI/18665/lts2r1f.pdf}}</ref>

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.<ref>Delsarte, P. and Genin, Y. V. (1986), ''The split Levinson algorithm'', ''IEEE Transactions on Acoustics, Speech, and Signal Processing'', v. ASSP-34(3), pp.&nbsp;470–478</ref> It uses a special symmetrical property of parameter vectors on subsequent recursion levels. That is, calculations for the optimal predictor containing <math>p</math> terms make use of similar calculations for the optimal predictor containing <math>p-1</math> terms.

Another way of identifying model parameters is to iteratively calculate state estimates using [[Kalman filter]]s and obtaining [[maximum likelihood estimation|maximum likelihood]] estimates within [[expectation–maximization algorithm]]s.

For equally-spaced values, a polynomial interpolation is a [[Polynomial interpolation#Linear combination of the given values|linear combination of the known values.]] If the discrete time signal is estimated to obey a polynomial of degree <math>p-1,</math> then the predictor coefficients <math>a_i</math> are given by the corresponding row of the [[Pascal's triangle#The Triangle of Binomial Transform Coefficients is like Pascal's Triangle.|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 <math>p</math> are

: <math>\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}
 </math>