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, farsi, arabic, bulgarian, ukrainian, russian, french, basque, germa n, ngerman, german-x-2008-06-18, ngerman-x-2008-06-18, polish, 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/ucs/utf8x.def)) (/usr/share/texmf-texlive/tex/latex/ucs/ucs.sty (/usr/share/texmf-texlive/tex/latex/ucs/data/uni-global.def)) (/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.

scikits.talkbox.levinson(r, order, axis=-1)

Levinson-Durbin recursion, to efficiently solve symmetric linear systems with toeplitz structure.

Parameters :

r : array-like

input array to invert (since the matrix is symmetric Toeplitz, the corresponding pxp matrix is defined by p items only). Generally the autocorrelation of the signal for linear prediction coefficients estimation. The first item must be a non zero real, and corresponds to the autocorelation at lag 0 for linear prediction.

order : int

order of the recursion. For order p, you will get p+1 coefficients.

axis : int, optional

axis over which the algorithm is applied. -1 by default.

Returns :

a : array-like

the solution of the inversion (see notes).

e : array-like

the prediction error.

k : array-like

reflection coefficients.

Notes

Levinson is a well-known algorithm to solve the Hermitian toeplitz equation:

               _          _
-R[1] = R[0]   R[1]   ... R[p-1]    a[1]
 :      :      :          :         :
 :      :      :          _      *  :
-R[p] = R[p-1] R[p-2] ... R[0]      a[p]

with respect to a. Using the special symmetry in the matrix, the inversion can be done in O(p^2) instead of O(p^3).

Only double argument are supported: float and long double are internally converted to double, and complex input are not supported at all.

Linear prediction coding

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

scikits.talkbox.lpc(signal, order, axis=-1)

Compute the Linear Prediction Coefficients.

Return the order + 1 LPC coefficients for the signal. c = lpc(x, k) will find the k+1 coefficients of a k order linear filter:

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

Such as the sum of the squared-error e[i] = xp[i] - x[i] is minimized.

Parameters :

signal: array_like :

input signal

order : int

LPC order (the output will have order + 1 items)

Returns :

a : array-like

the solution of the inversion.

e : array-like

the prediction error.

k : array-like

reflection coefficients.

Notes

This uses Levinson-Durbin recursion for the autocorrelation matrix inversion, and fft for the autocorrelation computation.

For small order, particularly if order << signal size, direct computation of the autocorrelation is faster: use levinson and correlate in this case.

Table Of Contents

Previous topic

Spectral analysis

This Page