Linear Prediction

The goal of linear-prediction is to model a signal as a linear combination of its past/future.

Yule-Walker equations

For a discrete-time signal x, we want to approximate the sample x[n] as a linear combination xp[n] of the k preceding samples:

xp[n] = -c[1] * x[n-2] - ... - c[k-1] * x[n-k-1]

The best approximation in the mean-square sense is a tuple(c[1], ..., c[k]) such as the squared error:

e = xp - x

Is minimal. Noting p(x) = xp, and x^{-k} the signal x^{-k}[n] = x[n-k], since p is a linear combination of the (x^-1, ..., x^-k), we know that the error p(x) - x is minimal for p the orthogonal project of x on the vector space V spanned by the x^-1, ..., x^-k. In particular, the error e is then orthogonal to any vector in V:

TODO: decent blob for above

System Message: WARNING/2 (\begin{pmatrix} -R[1] \\ -R[2] \\ \vdots \\ -R[p] \end{pmatrix} = \begin{pmatrix} R[0] & \overline{R}[1] & \dots & \overline{R}[p-1] \\ R[1] & R[0] & \ddots & \vdots \\ \vdots & \ddots & \ddots & \overline{R}[1]\\ R[p-1] & \dots & R[1] & R[0] \end{pmatrix} \begin{pmatrix} a[1] \\ \vdots \\ \vdots \\ a[p] \end{pmatrix})

latex exited with error: [stderr] [stdout] This is pdfTeXk, Version 3.1415926-1.40.9 (Web2C 7.5.7) %&-line parsing enabled. entering extended mode (./math.tex LaTeX2e <2005/12/01> Babel <v3.8l> and hyphenation patterns for english, usenglishmax, dumylang, noh yphenation, loaded. (/usr/share/texmf-texlive/tex/latex/base/article.cls Document Class: article 2005/09/16 v1.4f Standard LaTeX document class (/usr/share/texmf-texlive/tex/latex/base/size12.clo)) (/usr/share/texmf-texlive/tex/latex/base/inputenc.sty (/usr/share/texmf-texlive/tex/latex/base/utf8.def (/usr/share/texmf-texlive/tex/latex/base/t1enc.dfu) (/usr/share/texmf-texlive/tex/latex/base/ot1enc.dfu) (/usr/share/texmf-texlive/tex/latex/base/omsenc.dfu))) (/usr/share/texmf-texlive/tex/latex/amsmath/amsmath.sty For additional information on amsmath, use the `?’ option. (/usr/share/texmf-texlive/tex/latex/amsmath/amstext.sty (/usr/share/texmf-texlive/tex/latex/amsmath/amsgen.sty)) (/usr/share/texmf-texlive/tex/latex/amsmath/amsbsy.sty) (/usr/share/texmf-texlive/tex/latex/amsmath/amsopn.sty)) (/usr/share/texmf-texlive/tex/latex/amscls/amsthm.sty) (/usr/share/texmf-texlive/tex/latex/amsfonts/amssymb.sty (/usr/share/texmf-texlive/tex/latex/amsfonts/amsfonts.sty)) (/usr/share/texmf-texlive/tex/latex/tools/bm.sty) ! LaTeX Error: File `preview.sty’ not found. Type X to quit or <RETURN> to proceed, or enter new name. (Default extension: sty) Enter file name: ! Emergency stop. <read *> l.12 \begin {document}^^M No pages of output. Transcript written on math.log.

Levinson-Durbin recursion

Levinson-Durbin recursion is a recursive algorithm to solve the Yule-Walker equations in O(p^2) instead of O(p^3) usually necessary to inverse a matrix. It uses the Hermitian-Toeplitz structure of the correlation matrix.

Linear prediction coding

Solve the Yule-Walker equation for a signal x, using the autocorelation method and Levinson-Durbin for the Yule-Walker inversion.

Table Of Contents

Previous topic

Spectral analysis

This Page