COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

Yule-Walker and Levinson-Durbin Algorithm

• Follow

```Hello,
Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
Any comment is appreciatted
```
 0

```On 19 apr, 09:16, "Rogelio" <rogelio.a.mancisi...@student.bi.no>
wrote:
> Hello,
> Does any body know how to open the m.file containing the Levinson-Durbin =
algorithm? The point is that if I used the fucntion aryule to estimate ar c=
oefficients I get some estimates that are far away from the theoretical one=
s (based on my example). I beleive that the problem can be done by the way =
the autovariance/crosscovariance is calculated and might be the Levinson-Du=
rbin Algorithm as well.

Code what you think is the correct algorithm up yourself.
Compare with the various variants available with matlab
and see if any of them match your results. If 'no' find out
where your code is wrong. If 'yes' check the docs fro the
matlab functions and see how the algorithms differ. Then
code whatever algorithm is used for the method that didn't
match your own results. If all the algorithms match, the
discrepancies are due to different algorithms. If so, contemplate
the algorithms and find out why and how the results differ.

Rune
```
 0

```"Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqgvvl\$7ge\$1@fred.mathworks.com>...
> Hello,
> Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
> Any comment is appreciatted

To open a function, type:
edit functionname,

most of the theory on this algorithm uses more of autocorrelation,and cross correlation
```
 0

```"Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqgvvl\$7ge\$1@fred.mathworks.com>...
> Hello,
> Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
> Any comment is appreciatted

Hi Rogelio, levinson is a MEX file so you won't be able to see the actual code. Why don't you create realizations of an AR(p) process with known coefficients and see how close your coding is to that returned by aryule()?

For example:

reset(RandStream.getDefaultStream);
Arcoeffs = [1.0000   -0.9    0.3];
x = filter(1,Arcoeffs,randn(1000,1));
ArEst = aryule(x,2);
% compare ArEst and Arcoeffs
% ArEst returns 1.0000   -0.9491    0.3358

That is pretty close!
Wayne
```
 0

```"ade77 " <ade100a@gmail.com> wrote in message <hqi055\$gn1\$1@fred.mathworks.com>...
> "Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqgvvl\$7ge\$1@fred.mathworks.com>...
> > Hello,
> > Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
> > Any comment is appreciatted
>
> To open a function, type:
> edit functionname,
>
> most of the theory on this algorithm uses more of autocorrelation,and cross correlation

The levinson algorithm is a .mex file, so I cannot open. I am pretty sure that the difference is in the way the autocorrelation and/or crosscorrelation is computed. Moreover, aryule funtion doesnt provide the covariance matrix for the coefficientes and this can be easily modifed in the levinson algorithm or computed beside the algorihm. However, this is a flaw in the algorithm.
```
 0

```"Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqi4fo\$50v\$1@fred.mathworks.com>...
> > "Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqgvvl\$7ge\$1@fred.mathworks.com>...
> > > Hello,
> > > Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
> > > Any comment is appreciatted
> >
> > To open a function, type:
> > edit functionname,
> >
> > most of the theory on this algorithm uses more of autocorrelation,and cross correlation
>
>
> The levinson algorithm is a .mex file, so I cannot open. I am pretty sure that the difference is in the way the autocorrelation and/or crosscorrelation is computed. Moreover, aryule funtion doesnt provide the covariance matrix for the coefficientes and this can be easily modifed in the levinson algorithm or computed beside the algorihm. However, this is a flaw in the algorithm.

The main difference is the variance estimate. This is more or less fixed by using the autocovariance function insted of the autocorrelation (in the aryule algorithm). This two alternatives are, mathematically, identical. Does any one can tell me what I am missing??
```
 0

```"Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqi4fo\$50v\$1@fred.mathworks.com>...
> > "Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqgvvl\$7ge\$1@fred.mathworks.com>...
> > > Hello,
> > > Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
> > > Any comment is appreciatted
> >
> > To open a function, type:
> > edit functionname,
> >
> > most of the theory on this algorithm uses more of autocorrelation,and cross correlation
>
>
> The levinson algorithm is a .mex file, so I cannot open. I am pretty sure that the difference is in the way the autocorrelation and/or crosscorrelation is computed. Moreover, aryule funtion doesnt provide the covariance matrix for the coefficientes and this can be easily modifed in the levinson algorithm or computed beside the algorihm. However, this is a flaw in the algorithm.

Rogelio, see my post in the thread. From what I see aryule() gets very close when you feed it realizations of an AR(p) process generated with known coefficients. Can you provide an example of where it does not?

Wayne

Wayne
```
 0

```"Wayne King" <wmkingty@gmail.com> wrote in message <hqi585\$j1t\$1@fred.mathworks.com>...
> "Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqi4fo\$50v\$1@fred.mathworks.com>...
> > > "Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqgvvl\$7ge\$1@fred.mathworks.com>...
> > > > Hello,
> > > > Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
> > > > Any comment is appreciatted
> > >
> > > To open a function, type:
> > > edit functionname,
> > >
> > > most of the theory on this algorithm uses more of autocorrelation,and cross correlation
> >
> >
> > The levinson algorithm is a .mex file, so I cannot open. I am pretty sure that the difference is in the way the autocorrelation and/or crosscorrelation is computed. Moreover, aryule funtion doesnt provide the covariance matrix for the coefficientes and this can be easily modifed in the levinson algorithm or computed beside the algorihm. However, this is a flaw in the algorithm.
>
> Rogelio, see my post in the thread. From what I see aryule() gets very close when you feed it realizations of an AR(p) process generated with known coefficients. Can you provide an example of where it does not?
>
> Wayne
>
> Wayne

I had simulated an AR(p) process and I saw what you pointed, however for real data there is a significant discrepancy. Let me tell you my example from a book. At http://stat.pitt.edu/stoffer/tsa2/ under CHAPTER1 theres is a data set called recruit.dat. Then try this for an AR(2):
%first OLS to estimate parameters
y=importdata('recruit.dat');
xx=lagmatrix(A,1:2);
X=[ones(453,1) xx];
[b bint r rint stat]=regress(A,X);
varhat=stat(4);
%now the Yule-Walker
[a e]=aryule(A,2);

If you compare the variance estimate in the OLS and in the Yule-Walker the difference is 18.8338, while the coefficients are closer. Now if I modified the aryule function in the line 37 and instead of xcorr I use xcov (in both I used the biased form) the difference in the variance estimate is now 3.85 and the coefficients are even closer to OLS.
Now, while wirtting this post I realized that the difference in the variance estimates is due to the fact that regress uses the unbiased formula, while I was using the biased formula for both xcov and xcorr. However, the difference in the variance estimate for xcorr vs OLS is higher than xcov VS OLS. It seems that the Yule-Walker algorithm is better behaved  for autocovariances than autocorrelations for nonsimulated data. Eventhoug both formulations, autocovariance and autocorrelation, are mathematically equivalent.
We would need to see the levinson algorithim to see whats going on.
```
 0

```"Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqia82\$krc\$1@fred.mathworks.com>...
> "Wayne King" <wmkingty@gmail.com> wrote in message <hqi585\$j1t\$1@fred.mathworks.com>...
> > "Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqi4fo\$50v\$1@fred.mathworks.com>...
> > > > "Rogelio" <rogelio.a.mancisidor@student.bi.no> wrote in message <hqgvvl\$7ge\$1@fred.mathworks.com>...
> > > > > Hello,
> > > > > Does any body know how to open the m.file containing the Levinson-Durbin algorithm? The point is that if I used the fucntion aryule to estimate ar coefficients I get some estimates that are far away from the theoretical ones (based on my example). I beleive that the problem can be done by the way the autovariance/crosscovariance is calculated and might be the Levinson-Durbin Algorithm as well.
> > > > > Any comment is appreciatted
> > > >
> > > > To open a function, type:
> > > > edit functionname,
> > > >
> > > > most of the theory on this algorithm uses more of autocorrelation,and cross correlation
> > >
> > >
> > > The levinson algorithm is a .mex file, so I cannot open. I am pretty sure that the difference is in the way the autocorrelation and/or crosscorrelation is computed. Moreover, aryule funtion doesnt provide the covariance matrix for the coefficientes and this can be easily modifed in the levinson algorithm or computed beside the algorihm. However, this is a flaw in the algorithm.
> >
> > Rogelio, see my post in the thread. From what I see aryule() gets very close when you feed it realizations of an AR(p) process generated with known coefficients. Can you provide an example of where it does not?
> >
> > Wayne
> >
> > Wayne
>
> I had simulated an AR(p) process and I saw what you pointed, however for real data there is a significant discrepancy. Let me tell you my example from a book. At http://stat.pitt.edu/stoffer/tsa2/ under CHAPTER1 theres is a data set called recruit.dat. Then try this for an AR(2):
> %first OLS to estimate parameters
> y=importdata('recruit.dat');
> xx=lagmatrix(A,1:2);
> X=[ones(453,1) xx];
> [b bint r rint stat]=regress(A,X);
> varhat=stat(4);
> %now the Yule-Walker
> [a e]=aryule(A,2);
>
> If you compare the variance estimate in the OLS and in the Yule-Walker the difference is 18.8338, while the coefficients are closer. Now if I modified the aryule function in the line 37 and instead of xcorr I use xcov (in both I used the biased form) the difference in the variance estimate is now 3.85 and the coefficients are even closer to OLS.
> Now, while wirtting this post I realized that the difference in the variance estimates is due to the fact that regress uses the unbiased formula, while I was using the biased formula for both xcov and xcorr. However, the difference in the variance estimate for xcorr vs OLS is higher than xcov VS OLS. It seems that the Yule-Walker algorithm is better behaved  for autocovariances than autocorrelations for nonsimulated data. Eventhoug both formulations, autocovariance and autocorrelation, are mathematically equivalent.
> We would need to see the levinson algorithim to see whats going on.

The autocorrelation function, by definition, is given by the autocovariance function normalized by the autovariance at lag 0. The sample autocovariance function substracts the average from each series, i.e. x_i - X; where X is the average. Now, in matlab the autocorrelation or cross correlation assumes an average value of 0. Hence if I compute ans=xcorr(x,2); ans./ans(3) is not equal to ans=xcov(x,2); ans./ans(3). These two should be equal if the autocorrelation has no normalizing factor. If we substract the average value to the series x, then matlab computes the same value for the above calculations.
```
 0

```On 20 apr, 09:56, "Rogelio" <rogelio.a.mancisi...@student.bi.no>
wrote:

>  Now, in matlab the autocorrelation or cross correlation assumes an average value of 0.

There are several different possible definitions of the terms
involved here, depending on what literature you are used to
read. Some people say that 'correlation' is the 'raw', non-normalized
version of the correlation, while 'covariance' is the same sequence
normalized to the range [-1,1].

Others define the cross correlation as the straight inner
product between the two sequences, mean left in, and the cross
covariance as the inner product with the mean subtracted.

As a further complication, a lot of literature on signal processing
assumes that the data have zero mean, in which case readers might be
tempted into thinking that there is no difference between correlation
and covariance, and that the two are interchangeable.

You can check the conventions used in your functions quite
easily:

1) Compute the AR model with both methods from the same data.
If the normalization convention is used in matlab, one set
of AR parameters will be a scaled version of the other, and
the zeros of the AR polynomials will be in the same locations.

2) Compute the AR parameters with with both methods, with the
mean subtracted from the data. If the difference between
correlation and covariance is in the mean, the results should
be more or less identical.

Rune
```
 0

9 Replies
706 Views

Similiar Articles:

7/23/2012 9:26:37 AM