Levinson-Durbin Adaptive Filter....How?

Hi All,
I'm just confusing myself with predictors and the Levinson-Durbin
algorithm.  I've got Haykin's book.  So... near the start of the book
there are diagrams of the different adaptive filter models.  I am
familar with the identification model and LMStype algorthims.  But I'm
trying to understand the predictor and Levinson-Durbin algorthim.  Do
these two go together?!

In the predictor model there is the error signal (d(n)-y(n)) which is
then feed back into the filter.  If I use the L-D algorthim is this
error feed back into the algorthim?  I don't see an error term in the
algorthim.....

I'm using matlab, well simulink really.  There is a Levinson-Durbin
block which has one input, and outputs can be the solutions to the L-D,
and/or reflection coefficients (?) and/or also the output prediction
error.  I think that if I put my input signal through the block that it
is the first output that I want to look at??  Not sure what the others
are!

Any help on this would be very much appreciated.  I'm feeling quite
stupid about all this right now:-( 

Many thanks

Vicki wrote:
> Hi All,
> I'm just confusing myself with predictors and the Levinson-Durbin
> algorithm.  I've got Haykin's book.  So... near the start of the book
> there are diagrams of the different adaptive filter models.  I am
> familar with the identification model and LMStype algorthims.  But I'm
> trying to understand the predictor and Levinson-Durbin algorthim.  Do
> these two go together?!

I sure don't think of Levinson-Durbin as adaptive.  It takes 
a pair of time domain sequences and finds a linear transform 
(of a specified length) that takes one to the other with LMS 
error but it is a deterministic calculation without the kind 
of iterative improvement step that characterizes adaptive 
systems.


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein

Vicki wrote:
> Hi All,
> I'm just confusing myself with predictors and the Levinson-Durbin
> algorithm.  I've got Haykin's book.  So... near the start of the book
> there are diagrams of the different adaptive filter models.  I am
> familar with the identification model and LMStype algorthims.  But
I'm
> trying to understand the predictor and Levinson-Durbin algorthim.  Do
> these two go together?!

The LD is "semi-adaptive" in that it uses the data to find
a set of filter coefficients, but when these coefficents have
been found, they are never updated. The data used to determine
the coefficients are "typical" for the data the filter will
operate on.

> In the predictor model there is the error signal (d(n)-y(n)) which is
> then feed back into the filter.  If I use the L-D algorthim is this
> error feed back into the algorthim?  I don't see an error term in the
> algorthim.....

Well, it's there during the design stages. The equations used
to compute the coefficients were derived in a way that minimizes
the error term. The reflection coefficient you mention below, says
something about how much the error term decreases from one filter
order to the next.

> I'm using matlab, well simulink really.  There is a Levinson-Durbin
> block which has one input, and outputs can be the solutions to the
L-D,
> and/or reflection coefficients (?) and/or also the output prediction
> error.  I think that if I put my input signal through the block that
it
> is the first output that I want to look at??  Not sure what the
others
> are!

The filter coefficients and reflection coefficients are two
different but equivalent ways of representing the filter.
The prediction error is very useful in signal compression
applications.

Rune

Rune Allnor wrote:

>Vicki wrote:
>  
>
>>Hi All,
>>I'm just confusing myself with predictors and the Levinson-Durbin
>>algorithm.  I've got Haykin's book.  So... near the start of the book
>>there are diagrams of the different adaptive filter models.  I am
>>familar with the identification model and LMStype algorthims.  But
>>    
>>
>I'm
>  
>
>>trying to understand the predictor and Levinson-Durbin algorthim.  Do
>>these two go together?!
>>    
>>
>
>The LD is "semi-adaptive" in that it uses the data to find
>a set of filter coefficients, but when these coefficents have
>been found, they are never updated. The data used to determine
>the coefficients are "typical" for the data the filter will
>operate on.
>  
>
Why only semi adaptive? You present data to the Levinson-Durbin 
algorithm (or the Schurr one for that matter). It recursively tunes a 
set of filter parameters to match the data as best it can. To me that 
sounds as adaptive as something like LMS.

Regards,
Steve

Steve Underwood wrote:
> Rune Allnor wrote:
>
> >Vicki wrote:
> >
> >
> >>Hi All,
> >>I'm just confusing myself with predictors and the Levinson-Durbin
> >>algorithm.  I've got Haykin's book.  So... near the start of the
book
> >>there are diagrams of the different adaptive filter models.  I am
> >>familar with the identification model and LMStype algorthims.  But
> >>
> >>
> >I'm
> >
> >
> >>trying to understand the predictor and Levinson-Durbin algorthim.
Do
> >>these two go together?!
> >>
> >>
> >
> >The LD is "semi-adaptive" in that it uses the data to find
> >a set of filter coefficients, but when these coefficents have
> >been found, they are never updated. The data used to determine
> >the coefficients are "typical" for the data the filter will
> >operate on.
> >
> >
> Why only semi adaptive? You present data to the Levinson-Durbin
> algorithm (or the Schurr one for that matter). It recursively tunes a

> set of filter parameters to match the data as best it can. To me that

> sounds as adaptive as something like LMS.

Well, I have never dealed with "fully adaptive" stuff, i.e. systems
that adjust to the data "on the fly". Unlike LMS, to the diminishing
degree I know LMS, the Levinson algorithm solves for the filter
coefficients once and for all, once the training data are available.
The Levionson recursion requires all measured data to be available
(implicitly, as estimates of the autocorrelation sequence).
As far as I know, it's not possible for the Levinson recursion
to take advantage of more available data without starting over,
at the initialization stage.

As far as I know, the LMS algorithms starts out somewhere and
"tunes in" on the processed data, and improves as more data are
available.

Perhaps the difference is insignificant, but I interpret the two
approaches differently: The Levinson recursion uses a separate
training set, while the LMS tunes in to the data to be processed
as they become avaliable.

Rune

Bob Cain wrote:
> Vicki wrote:
> > Hi All,
> > I'm just confusing myself with predictors and the Levinson-Durbin
> > algorithm.  I've got Haykin's book.  So... near the start of the
book
> > there are diagrams of the different adaptive filter models.  I am
> > familar with the identification model and LMStype algorthims.  But
I'm
> > trying to understand the predictor and Levinson-Durbin algorthim.
Do
> > these two go together?!
>
> I sure don't think of Levinson-Durbin as adaptive.  It takes
> a pair of time domain sequences and finds a linear transform
> (of a specified length) that takes one to the other with LMS
> error but it is a deterministic calculation without the kind
> of iterative improvement step that characterizes adaptive
> systems.

Heh, you really live up to your signature by phrasing in so few
words what I tried (and failed) to put down if at least four
times as many.

> "Things should be described as simply as possible, but no
> simpler."

Rune

Thanks for the replies.

So all I need to do then is to put my signal through the
Levinson-Durbin block in matlab and look at the outputs from that, yes?

Next questions is then:  Does using the L-D algorithm pre-whiten my
signal?  (eventually, want to prewhiten then do some blind convolution
on it).

I'm not really sure why I'm wanting to use predictors or the L-D
algorthim but as someone has suggested I do it, and I have no better
ideas and need to move forward I want to try this and see whether it
gives me anything useful!

Vicki wrote:
> Hi All,
> I'm just confusing myself with predictors and the Levinson-Durbin
> algorithm.  I've got Haykin's book.  So... near the start of the book
> there are diagrams of the different adaptive filter models.  I am
> familar with the identification model and LMStype algorthims.  But I'm
> trying to understand the predictor and Levinson-Durbin algorthim.  Do
> these two go together?!
> 
> In the predictor model there is the error signal (d(n)-y(n)) which is
> then feed back into the filter.  If I use the L-D algorthim is this
> error feed back into the algorthim?  I don't see an error term in the
> algorthim.....
> 
> I'm using matlab, well simulink really.  There is a Levinson-Durbin
> block which has one input, and outputs can be the solutions to the L-D,
> and/or reflection coefficients (?) and/or also the output prediction
> error.  I think that if I put my input signal through the block that it
> is the first output that I want to look at??  Not sure what the others
> are!
> 
> Any help on this would be very much appreciated.  I'm feeling quite
> stupid about all this right now:-( 
> 
> Many thanks
> 

The niceset derivation of Levinson Durbin, IMHO is in Golub and Van 
Loan's "Matrix Computations" books.

Vicki wrote:
> Thanks for the replies.
>
> So all I need to do then is to put my signal through the
> Levinson-Durbin block in matlab and look at the outputs from that,
yes?

I'm not sure it will be that easy with matlab. Pre-whitening the
signal would involve finding an inverse filter and apply that to
your data. It's not difficult, but you need to know what to do.
If you typed wrong and meant simulink instead of matlab, it might
be that easy, yes. I don't know simulink well enough to comment
on that.

> Next questions is then:  Does using the L-D algorithm pre-whiten my
> signal?  (eventually, want to prewhiten then do some blind
convolution
> on it).

The error signal that comes out of your simulink block is the
pre-whitened signal.

> I'm not really sure why I'm wanting to use predictors or the L-D
> algorthim but as someone has suggested I do it, and I have no better
> ideas and need to move forward I want to try this and see whether it
> gives me anything useful!

What's the application? There is something called "predictive
deconvolution" that is used in the seismics industry. While it is
widely used, I don't know much about it except it is based on
the Levinson recursion and the theory behind AR models. The
techniques were developed in the 1970ies, and implemented in
processing packages in the 80ies, but no theory appears to be
available in the literature. There was a book by Treitel and
Robinson issued in 1980, but I have looked for a copy for ten
years whitout finding one. These days every processing package
contains a Predicive Decon operator. Since everybody knows what
it does and know how to use it, no one seem to care how it works.

So again, depending on the application, you might very well be on
a useful track.

Rune

Rune Allnor wrote:
> Bob Cain wrote:

>>I sure don't think of Levinson-Durbin as adaptive.  It takes
>>a pair of time domain sequences and finds a linear transform
>>(of a specified length) that takes one to the other with LMS
>>error but it is a deterministic calculation without the kind
>>of iterative improvement step that characterizes adaptive
>>systems.
> 
> 
> Heh, you really live up to your signature by phrasing in so few
> words what I tried (and failed) to put down if at least four
> times as many.

Thanks.  I'm used to hearing the exact opposite, but mainly 
from people who don't generally understand "necessasary and 
sufficient."  :-)


Bob
-- 

"Things should be described as simply as possible, but no 
simpler."

                                              A. Einstein