AR Extrapolation

Hi Cris,

> I am doing some research regarding the High-Resolution methods, for
> applications in Automotive Radar, and before I compose my own C codes I am
> playing with the Matlab intrinsic functions. 

That's a very wise way of working. Be aware, though, that some neat 
functionality you probably would want in your own code, like order 
estimation, usually lacks in the matlab codes.

> One of these functions is
> arburg (pburg) and I was curious how good are the AR coefficients estimated.
> So, I build a short example, I took a short data sequence (one cycle
> (period) for better analysis) of length = 64 samples 

So you have 64 samples and one sinusoid with period n/64 for some 
integer n? Do you include damping in your sinusoid? Or do you use 
a completely different type of data?

> added with some noise
> (from a longer generated sequence), 

The same goes for the noise. Exactly how did you generate it? 
Not that it would matter very much in this particular case  
but such details are of immense help when you ask questions 
here. There could be a problem with the way you generate the 
noise. Even if it isn't, people would like to have this type 
of information just to rule that out.

> and I applied pburg. The spectrum looks
> okay, I mean the estimated frequency is at the right bin. With the same
> short sequence I estimated the coefficients using arburg, and then having
> these coefficients and the original sequence of data I tried to estimate
> (through extrapolation) the following cycle, which it should look maybe not
> like a twin brother of the main cycle but close to it.
> 
> I used the following eq. for extrapolation:
> 
>              p
> 
> x[n] = -sum a[k]x[n-k]
> 
>             k=1
> 
> 
> 
> for my surprise I did not become the expected sequence of estimated data
> values. Is my thought not logical? Am I missing something?
> 
> (Parameters: 64 data samples x[0:n-1], 16 estimated coefficients a[1:p] and
> then try to estimate the next 64 samples x[n:2n-1])

Well, you use the method out of scope. As a basic premise, assume that 
the data you look at are *not* from an AR(p) stochastic process. This 
happens either because ther is observation noise added to your data, 
or because the AR(p) model is an arbitrary chosen model (usually because
of both these reasons).

So the regression equation becomes

                    P
   x'[n] + e[n] = -sum a[k]x[n-k]                           [1]
                   k=1
 
Look carefully at equation [1]. The 'x' here is not an arbitrary 
data sample, it's a data sample that belongs to an ordered N-dimensional 
random variable that was drawn from a stochastic process (N being the 
number of data samples available, in your case N = 64). 

Equation [1] says that given P ordered samples in this random variable, 
it is possible to predict the next sample better than by just guessing 
wild. There will be made an error, but it can be shown that equation [1]
is optimal both with respect to minimizing the noise energy (as is 
shown through the derivation of the Yule-Walker equations), and it 
is also optimal with respect to maximizing the entropy of the error 
sequence (Burg's derivation of 1968).

Now, what happens if you extrapolate the sequence x? I'll demonstrate 
by using equation [1] on the data sequence {x[0], x[1],..., x[p-1]} 
and extrapolate first to find x[p] and then x[p+1]. 

First, estimate x[p] based on the samples {x[0],...,x[p-1]}:

              p
   x"[p] = - sum a[k]x[p-k] = e[p]                           [2] 
             k=1           
  
where x"[n] is the estimate of x[n] by extrapolation.

Why no x'[p] in equation [2]? Because sample x[p] does not exist
in the data stream. Because of that, is not possible for the 
prediction operator to correct the prediction error, as is readily 
seen in the next step:

               p
   x"[p+1]= - sum a[k]x[p-k] + a[1]e[p] = e[p+2]             [3]
              k=2

The difference between equation [3] and equation [1] is that there 
is a data sample x[p] where the e[p] step occurs in equation [3].
The occurance of this new data sample means that any error introduced
in equation [2] when *predicting* sample x[p], is *not* carried 
on in the prediction of sample x[p+1]. 

Since there comes no new sample x[p] from the data source between 
steps [2] and [3], it is not longer possible for the predictor to 
correct for the error made in step [2]. So the extrapolation problem
is ill-posed. After p steps, extrapolation is probably no better than 
wild guessing.

So in summary, your problems are caused by the fact that you 
are trying to use the methods out of scope. "Prediction" and 
"extrapolation" are two very different things.

Rune

"Rune Allnor" <allnor@tele.ntnu.no> wrote in message
news:f56893ae.0412082358.1c1b5519@posting.google.com...
> Hi Cris,
>
> > I am doing some research regarding the High-Resolution methods, for
> > applications in Automotive Radar, and before I compose my own C codes I
am
> > playing with the Matlab intrinsic functions.
>
> That's a very wise way of working. Be aware, though, that some neat
> functionality you probably would want in your own code, like order
> estimation, usually lacks in the matlab codes.
>
> > One of these functions is
> > arburg (pburg) and I was curious how good are the AR coefficients
estimated.
> > So, I build a short example, I took a short data sequence (one cycle
> > (period) for better analysis) of length = 64 samples
>
> So you have 64 samples and one sinusoid with period n/64 for some
> integer n? Do you include damping in your sinusoid? Or do you use
> a completely different type of data?
>
> > added with some noise
> > (from a longer generated sequence),
>
> The same goes for the noise. Exactly how did you generate it?
> Not that it would matter very much in this particular case
> but such details are of immense help when you ask questions
> here. There could be a problem with the way you generate the
> noise. Even if it isn't, people would like to have this type
> of information just to rule that out.
>
> > and I applied pburg. The spectrum looks
> > okay, I mean the estimated frequency is at the right bin. With the same
> > short sequence I estimated the coefficients using arburg, and then
having
> > these coefficients and the original sequence of data I tried to estimate
> > (through extrapolation) the following cycle, which it should look maybe
not
> > like a twin brother of the main cycle but close to it.
> >
> > I used the following eq. for extrapolation:
> >
> >              p
> >
> > x[n] = -sum a[k]x[n-k]
> >
> >             k=1
> >
> >
> >
> > for my surprise I did not become the expected sequence of estimated data
> > values. Is my thought not logical? Am I missing something?
> >
> > (Parameters: 64 data samples x[0:n-1], 16 estimated coefficients a[1:p]
and
> > then try to estimate the next 64 samples x[n:2n-1])
>
> Well, you use the method out of scope. As a basic premise, assume that
> the data you look at are *not* from an AR(p) stochastic process. This
> happens either because ther is observation noise added to your data,
> or because the AR(p) model is an arbitrary chosen model (usually because
> of both these reasons).
>
> So the regression equation becomes
>
>                     P
>    x'[n] + e[n] = -sum a[k]x[n-k]                           [1]
>                    k=1
>
> Look carefully at equation [1]. The 'x' here is not an arbitrary
> data sample, it's a data sample that belongs to an ordered N-dimensional
> random variable that was drawn from a stochastic process (N being the
> number of data samples available, in your case N = 64).
>
> Equation [1] says that given P ordered samples in this random variable,
> it is possible to predict the next sample better than by just guessing
> wild. There will be made an error, but it can be shown that equation [1]
> is optimal both with respect to minimizing the noise energy (as is
> shown through the derivation of the Yule-Walker equations), and it
> is also optimal with respect to maximizing the entropy of the error
> sequence (Burg's derivation of 1968).
>
> Now, what happens if you extrapolate the sequence x? I'll demonstrate
> by using equation [1] on the data sequence {x[0], x[1],..., x[p-1]}
> and extrapolate first to find x[p] and then x[p+1].
>
> First, estimate x[p] based on the samples {x[0],...,x[p-1]}:
>
>               p
>    x"[p] = - sum a[k]x[p-k] = e[p]                           [2]
>              k=1
>
> where x"[n] is the estimate of x[n] by extrapolation.
>
> Why no x'[p] in equation [2]? Because sample x[p] does not exist
> in the data stream. Because of that, is not possible for the
> prediction operator to correct the prediction error, as is readily
> seen in the next step:
>
>                p
>    x"[p+1]= - sum a[k]x[p-k] + a[1]e[p] = e[p+2]             [3]
>               k=2
>
> The difference between equation [3] and equation [1] is that there
> is a data sample x[p] where the e[p] step occurs in equation [3].
> The occurance of this new data sample means that any error introduced
> in equation [2] when *predicting* sample x[p], is *not* carried
> on in the prediction of sample x[p+1].
>
> Since there comes no new sample x[p] from the data source between
> steps [2] and [3], it is not longer possible for the predictor to
> correct for the error made in step [2]. So the extrapolation problem
> is ill-posed. After p steps, extrapolation is probably no better than
> wild guessing.
>
> So in summary, your problems are caused by the fact that you
> are trying to use the methods out of scope. "Prediction" and
> "extrapolation" are two very different things.
>
> Rune
Thank you for your response Rune.

I'll try to give some more precise information about what I am doing.

It seems that I complicated my life without intention, I was just curious to
see if the theory is so simple to apply, and is not. Definitely the
prediction is not the same thing with extrapolation and now I am 'happy'
that I tried this example because in this way I am improving my knowledge
regarding this side of the AR models.

So, maybe is better to put some small code for a better view,



n=255;

fs=256;

t = (0:n)/fs;

ampn = .05;

x_original_signal = sin(2*pi*t*4) + ampn*randn(size(t));



I am taking one cycle,

x_period = [x_original_signal(1:64) x_original_signal(1)]; - I put it like
this just to show that I consider it as being a time continuous signal
period, of course in discrete time representation it will be characterised
only by 64 sample values.



and then apply to x_period(1:64) the arburg intrinsic function for
estimating the AR coefficients.

The model order I selected it was p=16.

So this sequence of data is not coming from an AR stochastic process. I
consider my data as a deterministic signal added with Gaussian distributed
noise. Also the model is chosen arbitrarily.

It seems that this error correction is doing the whole mess in the
extrapolation chain, and I will try to solve it because now really bothers
me the idea that I didn't really get it from the first time. Now it just
came into my mind this question, is AR extrapolation of use anyway?



Regards



Cris