2.6 Linear prediction

Recall that for the all-pole design problem, we had the overdetermined set of linear equations: $$\begin{pmatrix}{h}_d(0) & 0 & \mathrm{...} & 0\\ h_d(1) & h_d(0) & \mathrm{...} & 0\\ & & & \\ h_d(N-1) & h_d(N-2) & \mathrm{...} & h_d(N-M)\\ \end{pmatrix}\left(\begin{array}{c}{a}_1\\ a_2\\ \\ a_M\end{array}\right)\approx -\left(\begin{array}{c}{h}_d(1)\\ h_d(2)\\ \\ h_d(N)\end{array}\right)$$ with solution $a=((H_d)H_d)^{-1}(H_d)h_d$

Let's look more closely at $(H_d)H_d=R$ . $r_{ij}$ is related to the correlation of $h_d$ with itself: $$r_{ij}=\sum_{k=0}^{N-\max\{i , j\}} h_d(k)h_d(k+\left|i-j\right|)$$ Note also that: $$(H_d)h_d=\left(\begin{array}{c}{r}_d(1)\\ r_d(2)\\ r_d(3)\\ \\ r_d(M)\end{array}\right)()$$ where $$r_d(i)=\sum_{n=0}^{N-i} h_d(n)h_d(n+i)$$ so this takes the form $a_{\mathrm{opt}}=-((R)r_d)$ , or $Ra=-r$ , where $R$ is $M\times M$ , $a$ is $M\times 1$ , and $r$ is also $M\times 1$ .

Except for the changing endpoints of the sum, $r_{ij}\approx r(i-j)=r(j-i)$ . If we tweak the problem slightly to make $r_{ij}=r(i-j)$ , we get: $$\begin{pmatrix}r(0) & r(1) & r(2) & \mathrm{...} & r(M-1)\\ r(1) & r(0) & r(1) & \mathrm{...} & \\ r(2) & r(1) & r(0) & \mathrm{...} & \\ & & & & \\ r(M-1) & \mathrm{...} & \mathrm{...} & \mathrm{...} & r(0)\\ \end{pmatrix}\left(\begin{array}{c}{a}_1\\ a_2\\ a_3\\ \\ a_M\end{array}\right)=-\left(\begin{array}{c}r(1)\\ r(2)\\ r(3)\\ \\ r(M)\end{array}\right)$$ The matrix $R$ is Toeplitz (diagonal elements equal), and $a$ can be solved for with $O(M^2)$ computations using Levinson's recursion.

Statistical linear prediction

Used very often for forecasting ( e.g. stock market).

Given a time-series $y(n)$ , assumed to be produced by an auto-regressive (AR) (all-pole) system: $$y(n)=-\sum_{k=1}^M a_{k}y(n-k)+u(n)$$ where $u(n)$ is a white Gaussian noise sequence which is stationary and has zero mean.

To determine the model parameters $\{a_k\}$ minimizing the variance of the prediction error, we seek