LEVINSON RECURSION

The Levinson recursion is a simplified method for solving normal equations. It may be shown to be equivalent to a recurrence relation in orthogonal polynomial theory. The simplification is Levinson's method is possible because the matrix $\cal R$ has actually only N different elements when a general matrix could have N² different elements.

Levinson developed his recursion with single time series in mind (the basic idea was presented in Section 3.3). It is very little extra trouble to do the recursion for multiple time series. Let us begin with the prediction-error normal equation. With multiple time series, unlike single time series, the prediction problem is changed if time is reversed. We may write both the forward and the backward prediction-error normal equations as one equation in the form of (36).

Since end effects play an important role, we will show how, when given the solution for 3-term filters, $\cal A$ and $\cal B$  

$$\left[ \begin{array} {lll} {\bf R}_0 & {\bf R}_{-1} & {\bf ... ...}\\ {\bf 0}& {\bf 0}\\ {\bf 0}& {\bf V}_B \end{array} \right]$$ (36)

to find the solution $\cal A'$ and $\cal B'$four-term filters to  

$$\left[ \begin{array} {llll} {\bf R}_0 & {\bf R}_{-1} & {\bf... ...\ {\bf 0}& {\bf 0}\\ {\bf 0}& {\bf V}_B \end{array} \right] '$$ (37)

by forming a linear combination of $\cal A$ and $\cal B$. This can be done by choosing constant matrices ${\bf \alpha}$ and ${\bf \beta}$ in  

$$\left[ \begin{array} {llll} {\bf R}_0 & {\bf R}_{-1} & {\bf... ...f 0}\\ {\bf 0}\\ {\bf V}_B \end{array} \right] \; {\bf \beta}$$ (38)

Make $\cal A$ by choosing ${\bf \alpha}$ and ${\bf \beta}$ so that the bottom element on the right-hand side of (38) vanishes. That is, ${\bf \alpha} = {\bf I}, {\bf \beta} + - {\bf V}^{-1}_B {\bf E}_A$.Make $\cal B$ by choosing ${\bf \alpha}$ and ${\bf \beta}$ so that the top element on the right-hand side vanishes. That is, ${\bf \beta} ={\bf I}, {\bf \alpha} = - {\bf V}^{-1}_A {\bf E}_B$.

Of course, one will want to solve more than just the prediction-error problem. We will also want to go from 3 x 3 to 4 x 4 in the solution of the filter problem with arbitrary right-hand side $\cal G$.This is accomplished by choosing $\gamma$in the following construction (39) so that ${\bf E}_f + {\bf V}_{B \gamma} = {\bf G}_3$ 

$$\left[ \begin{array} {llll} {\bf R}_0 & {\bf R}_{-1} & {\bf... ...} 0 \\ 0 \\ 0 \\ {\bf V}\end{array} \right] \gamma \right\}$$ (39)