Levinson-Durbin Adaptive Filter....How?

Started by Vicki May 18, 2005
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