Levinson durban recursion

Hi,
I am trying to get forward/backward predictor coefficients from the
ladder relection coefficients using the following recursion. (From
haykins book)

a_m(n) = [a_{m-1}(n) 0] + k_{f, m} [0 c_{m-1}(n-1)] --------- (1)

c_m(n) = [0 c_{m-1}(n-1) + k_{b, m} [a_{m-1}(n) 0] --------- (2)

where a_m and c_m correspond to forward/backward predictor
coefficients in this manner.

a_m = [1 -w_f], w_f are the forward predictor coefficients
c_m = [-w_b 1], w_b are the backward predictor coefficients

I think the complexity of doing (1) and (2) is order of N^3, where N is
the number of coefficients. Am I right? Does anyone know how to do it
in N^2

Reason,

If i want to know the relection coefficients at n, i need to know
c_{m-1}(n-1), which is at n-1 th instance. Also i know that c_{0}(k-1)
at any k is 1 and so is a_{0}(k), therefore if N is the total
coefficients i start at n = n-N, with these inital coefficients and
finally i get correct values of the coefficients. 

Regards

mobi skrev:
> Hi,
> I am trying to get forward/backward predictor coefficients from the
> ladder relection coefficients using the following recursion. (From
> haykins book)
>
> a_m(n) = [a_{m-1}(n) 0] + k_{f, m} [0 c_{m-1}(n-1)] --------- (1)
>
> c_m(n) = [0 c_{m-1}(n-1) + k_{b, m} [a_{m-1}(n) 0] --------- (2)
>
> where a_m and c_m correspond to forward/backward predictor
> coefficients in this manner.
>
> a_m = [1 -w_f], w_f are the forward predictor coefficients
> c_m = [-w_b 1], w_b are the backward predictor coefficients
>
> I think the complexity of doing (1) and (2) is order of N^3, where N is
> the number of coefficients. Am I right? Does anyone know how to do it
> in N^2

Wrong. The order update in the Levinson Durbin recursion is
O(N), which makes the recursion itself O(N^2).

> Reason,
>
> If i want to know the relection coefficients at n, i need to know
> c_{m-1}(n-1), which is at n-1 th instance. Also i know that c_{0}(k-1)
> at any k is 1 and so is a_{0}(k), therefore if N is the total
> coefficients i start at n = n-N, with these inital coefficients and
> finally i get correct values of the coefficients.

You start with initalized variables, a_0, b_0 and so on. Then you
use th erecursion formula to compute a_1,b_1 and so on. Then
you use *those* to compute a_2,b_2... You continue this way
until you decide to stop. Use an order estimator (e.g. AIC) or
decide in advance what order to compute.

Rune

Thankx for the reply. You are right the recursion itself is O(N), but i
think that the total process is O(N^3) like this. Correct me please

so here is how our recursion should go
step r1 will give a_0, b_0
r2: a_1, b_1 and so on...

     r1         r2        r3 .      ...      rN
0    1          1         1                  1
1                2         2
2                          3
3
.
.
.
N                                              N

right!!!

We can write it down as

   sum_{i=1}^{N} i(i+1)/2
= sum_{i=1}^{N} i^2/2 + sum_{i=1}^{N} i/2
= N(N+1)(2N+1)/12 + N(N+1)/2 <-------- (O(N^3))

Regards

Rune Allnor wrote:
> mobi skrev:
> > Hi,
> > I am trying to get forward/backward predictor coefficients from the
> > ladder relection coefficients using the following recursion. (From
> > haykins book)
> >
> > a_m(n) = [a_{m-1}(n) 0] + k_{f, m} [0 c_{m-1}(n-1)] --------- (1)
> >
> > c_m(n) = [0 c_{m-1}(n-1) + k_{b, m} [a_{m-1}(n) 0] --------- (2)
> >
> > where a_m and c_m correspond to forward/backward predictor
> > coefficients in this manner.
> >
> > a_m = [1 -w_f], w_f are the forward predictor coefficients
> > c_m = [-w_b 1], w_b are the backward predictor coefficients
> >
> > I think the complexity of doing (1) and (2) is order of N^3, where N is
> > the number of coefficients. Am I right? Does anyone know how to do it
> > in N^2
>
> Wrong. The order update in the Levinson Durbin recursion is
> O(N), which makes the recursion itself O(N^2).
>
> > Reason,
> >
> > If i want to know the relection coefficients at n, i need to know
> > c_{m-1}(n-1), which is at n-1 th instance. Also i know that c_{0}(k-1)
> > at any k is 1 and so is a_{0}(k), therefore if N is the total
> > coefficients i start at n = n-N, with these inital coefficients and
> > finally i get correct values of the coefficients.
>
> You start with initalized variables, a_0, b_0 and so on. Then you
> use th erecursion formula to compute a_1,b_1 and so on. Then
> you use *those* to compute a_2,b_2... You continue this way
> until you decide to stop. Use an order estimator (e.g. AIC) or
> decide in advance what order to compute.
> 
> Rune

mobi skrev:
> Thankx for the reply. You are right the recursion itself is O(N), but i
> think that the total process is O(N^3) like this. Correct me please
>
> so here is how our recursion should go
> step r1 will give a_0, b_0
> r2: a_1, b_1 and so on...
>
>      r1         r2        r3 .      ...      rN
> 0    1          1         1                  1
> 1                2         2
> 2                          3
> 3
> .
> .
> .
> N                                              N
>
> right!!!
>
> We can write it down as
>
>    sum_{i=1}^{N} i(i+1)/2


The above is N^2...

> = sum_{i=1}^{N} i^2/2 + sum_{i=1}^{N} i/2

..and so is this...

> = N(N+1)(2N+1)/12 + N(N+1)/2 <-------- (O(N^3))

...so how did you get this to become N^3?

Anyway, you should work through the details of the Levinson
recursion and see how it evolves, before you go on with the
analysis. 

Rune

Rune Allnor skrev:
> mobi skrev:
> > Thankx for the reply. You are right the recursion itself is O(N), but i
> > think that the total process is O(N^3) like this. Correct me please
> >
> > so here is how our recursion should go
> > step r1 will give a_0, b_0
> > r2: a_1, b_1 and so on...
> >
> >      r1         r2        r3 .      ...      rN
> > 0    1          1         1                  1
> > 1                2         2
> > 2                          3
> > 3
> > .
> > .
> > .
> > N                                              N
> >
> > right!!!
> >
> > We can write it down as
> >
> >    sum_{i=1}^{N} i(i+1)/2
>
>
> The above is N^2...

No, it's not. Your sum is N^3. But it's wrong.

> Anyway, you should work through the details of the Levinson
> recursion and see how it evolves, before you go on with the
> analysis.

As I said in my first post, the key to get the Levinson recursion
to work, is to exploit what you alreadt computed for order n-1
when you compute the parameters for order n. You only compute
those parameters that are new for order n. If you look closely at
the matrix above, you see that the numbers don't change once
they are in there . 

Rune