Frequency estimation using Fourier coefficients from multiple series

Hi all,

I am working on a problem which requires us to very accurately estimate 
the frequencies of a number of coarsely-spaced sinusoids buried in noise.

A few co-workers initiated work on this problem using methods based on a 
single series.  As the need for accuracy increased, the sequence length 
has also increased.  As with most processors, efficiency of performing 
FFTs falls off as the sequence length grows. This has led me to look at 
the method outlined in section 6.3 of Quinn and Hannan, which uses more 
than one series.  The goal being to achieve performance close to a 
length-RT series but using R sets of length-T series.

I have looked at the material in 6.3 but am having trouble understanding 
how to implement it.  Before I spend more time on this I just want to 
find out if it is worth it.

Has anybody attempted to implement this technique?  If so, can you 
comment on the performance?  Did results obtained using the R sets of 
length T approach that of using a length RT series?  Can you also please 
comment on how easy or hard this was to implement in terms of processing 
throughput required?

Thanks in advance,

Ken Prager

Ken Prager wrote:

> Hi all,
> 
> I am working on a problem which requires us to very accurately estimate 
> the frequencies of a number of coarsely-spaced sinusoids buried in noise.

[...]

This looks like the classic application for Prony method. Why can't you 
use it?


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

 Vladimir Vassilevsky wrote:

> Ken Prager wrote:
> 
> > Hi all,
> > 
> > I am working on a problem which requires us to very accurately estimate 
> > the frequencies of a number of coarsely-spaced sinusoids buried in noise.
> 
> [...]
> 
> This looks like the classic application for Prony method. Why can't you 
> use it?


In my research into this problem I hadn't really looked to closely at 
techniques based on Prony's method, which, from what I can tell, fall 
under the general category of noise subspace techniques.

I'll go back and take a closer look at those.

Thanks for the tip.

Ken Prager

In article <6ay3l.6567$8_3.2220@flpi147.ffdc.sbc.com>,
 Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote:

> Ken Prager wrote:
> 
> > Hi all,
> > 
> > I am working on a problem which requires us to very accurately estimate 
> > the frequencies of a number of coarsely-spaced sinusoids buried in noise.
> 
> [...]
> 
> This looks like the classic application for Prony method. Why can't you 
> use it?


One other question:

One of the reasons that a method based on Fourier coefficients is 
attractive is that we have to estimate up to 25 frequencies per data 
sequence.  I had looked at ARMA-based techniques (eg., Quinn-Fernandes), 
which worked very well. However, they require O(N) operation per 
frequency to be estimated.  Thus, a method based on Fourier coefficients 
is more efficient if log2(N) < 25, which it is in our case.

A quick survey reveals that techniques based on Prony's method are also 
O(N).  Do these techniques require O(N) per frequency to be estimated or 
can the algorithm be modified to solve for all frequencies of interest 
simultaneously?

Thanks,

Ken Prager

Ken Prager wrote:

> In article <6ay3l.6567$8_3.2220@flpi147.ffdc.sbc.com>,
>  Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote:
> 
> 
>>Ken Prager wrote:
>>
>>>I am working on a problem which requires us to very accurately estimate 
>>>the frequencies of a number of coarsely-spaced sinusoids buried in noise.
>>
>>This looks like the classic application for Prony method. Why can't you 
>>use it?
> 
> One other question:
> 
> One of the reasons that a method based on Fourier coefficients is 
> attractive is that we have to estimate up to 25 frequencies per data 
> sequence.  I had looked at ARMA-based techniques (eg., Quinn-Fernandes), 
> which worked very well. However, they require O(N) operation per 
> frequency to be estimated.  Thus, a method based on Fourier coefficients 
> is more efficient if log2(N) < 25, which it is in our case.
> 
> A quick survey reveals that techniques based on Prony's method are also 
> O(N).  Do these techniques require O(N) per frequency to be estimated or 
> can the algorithm be modified to solve for all frequencies of interest 
> simultaneously?

Rune Alnor is the comp.dsp regular who is specializing in the methods 
and problems like mentioned above. He can give you the professional 
advice about the strong an the weak points of the ARMA vs Fourier.

If Prony's method is employed, then the 25 frequencies require the 
factoring of the polynomial of the 50th or higher order, which can be a 
nasty numeric problem.


Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On 22 Des, 16:07, Ken Prager <pra...@ieee.org> wrote:
> &#4294967295;Vladimir Vassilevsky wrote:
> > Ken Prager wrote:
>
> > > Hi all,
>
> > > I am working on a problem which requires us to very accurately estimate
> > > the frequencies of a number of coarsely-spaced sinusoids buried in noise.
>
> > [...]
>
> > This looks like the classic application for Prony method. Why can't you
> > use it?
>
> In my research into this problem I hadn't really looked to closely at
> techniques based on Prony's method, which, from what I can tell, fall
> under the general category of noise subspace techniques.
>
> I'll go back and take a closer look at those.

Prony's method can indeed be viewed as a subspace method.
When it works it gives far more accurate frequency estimates
than the DFT, but it comes with its own cans of worms as it is
very awkward to use in practical situations.

The first attempt I would try - given that you say that the
line spectrum is 'coarse' - is the DFT-based high resolution
DoA estimators. Some DoA estimators (which basically
are frequency estimators) do some tricks to the spectrum
to track a zero-crossing in a quasi spectrum as opposed to
a peak in the main lobe.

I don't know this method in any detail (and I can't come
up with references off the top of my head - I'll look the method
up once I'm back home) but there is a chance this might
work with the data you have. If it does, it will probably be
more operational and computationally robust (although
possibly less accurate) than Prony's method.

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote:
> On 22 Des, 16:07, Ken Prager <pra...@ieee.org> wrote:
> > &#4294967295;Vladimir Vassilevsky wrote:
> > > Ken Prager wrote:
> >
> > > > Hi all,
> >
> > > > I am working on a problem which requires us to very accurately estimate
> > > > the frequencies of a number of coarsely-spaced sinusoids buried in 
> > > > noise.
> >
> > > [...]
> >
> > > This looks like the classic application for Prony method. Why can't you
> > > use it?
> >
> > In my research into this problem I hadn't really looked to closely at
> > techniques based on Prony's method, which, from what I can tell, fall
> > under the general category of noise subspace techniques.
> >
> > I'll go back and take a closer look at those.
> 
> Prony's method can indeed be viewed as a subspace method.
> When it works it gives far more accurate frequency estimates
> than the DFT, but it comes with its own cans of worms as it is
> very awkward to use in practical situations.
> 
> The first attempt I would try - given that you say that the
> line spectrum is 'coarse' - is the DFT-based high resolution
> DoA estimators. Some DoA estimators (which basically
> are frequency estimators) do some tricks to the spectrum
> to track a zero-crossing in a quasi spectrum as opposed to
> a peak in the main lobe.
> 
> I don't know this method in any detail (and I can't come
> up with references off the top of my head - I'll look the method
> up once I'm back home) but there is a chance this might
> work with the data you have. If it does, it will probably be
> more operational and computationally robust (although
> possibly less accurate) than Prony's method.

A reference or two would be much appreciated.

Also, can I expect that a method based on DoA estimators to be more 
accurate than one based on three Fourier coefficients?

Thanks,

Ken Prager

On 27 Des, 19:02, Ken Prager <pra...@ieee.org> wrote:
> Rune Allnor <all...@tele.ntnu.no> wrote:
> > On 22 Des, 16:07, Ken Prager <pra...@ieee.org> wrote:
> > > &#4294967295;Vladimir Vassilevsky wrote:
> > > > Ken Prager wrote:
>
> > > > > Hi all,
>
> > > > > I am working on a problem which requires us to very accurately estimate
> > > > > the frequencies of a number of coarsely-spaced sinusoids buried in
> > > > > noise.
>
> > > > [...]
>
> > > > This looks like the classic application for Prony method. Why can't you
> > > > use it?
>
> > > In my research into this problem I hadn't really looked to closely at
> > > techniques based on Prony's method, which, from what I can tell, fall
> > > under the general category of noise subspace techniques.
>
> > > I'll go back and take a closer look at those.
>
> > Prony's method can indeed be viewed as a subspace method.
> > When it works it gives far more accurate frequency estimates
> > than the DFT, but it comes with its own cans of worms as it is
> > very awkward to use in practical situations.
>
> > The first attempt I would try - given that you say that the
> > line spectrum is 'coarse' - is the DFT-based high resolution
> > DoA estimators. Some DoA estimators (which basically
> > are frequency estimators) do some tricks to the spectrum
> > to track a zero-crossing in a quasi spectrum as opposed to
> > a peak in the main lobe.
>
> > I don't know this method in any detail (and I can't come
> > up with references off the top of my head - I'll look the method
> > up once I'm back home) but there is a chance this might
> > work with the data you have. If it does, it will probably be
> > more operational and computationally robust (although
> > possibly less accurate) than Prony's method.
>
> A reference or two would be much appreciated.

What is the application? Why do you need accurate frequency
estimates?

> Also, can I expect that a method based on DoA estimators to be more
> accurate

Not more accurate then frequency estimators. People who work
with different applications some times use almost the same
methods to solve their problems under slightly different
constraints. So a method developed fro DoA estimation might
be useful for frequency estimation, and vice versa. The
maths is the same, but the terminology might be different.

Rune

On Dec 27, 10:49�am, Rune Allnor  wrote:
> On 27 Des, 19:02, Ken Prager wrote:
> > Rune Allnor  wrote:
> > >
> > > <snip>
> > >
> > > I don't know this method in any detail (and I can't come
> > > up with references off the top of my head - I'll look the method
> > > up once I'm back home) but there is a chance this might
> > > work with the data you have. If it does, it will probably be
> > > more operational and computationally robust (although
> > > possibly less accurate) than Prony's method.
>
> > A reference or two would be much appreciated.
>
> What is the application? Why do you need accurate frequency
> estimates?

The application is laser vibrometry.  A single sequence contains
vibration data from a number of points of the object being viewed.
Frequency shifts  represent deformation of the object.

Because we need to estimate multiple frequencies per sequence, we were
using a DFT-based method which worked fairly well.  However, due to
noise, we were having to use sequence lengths longer than can be
optimally implemented in our processor (due to cache size, etc.).  My
original post on this subject asked if anyone had any experience
combining the results using multiple sequences, as outlined in Quinn
and Hannan, chapter 6.3.  The claim there is that performance
approaching the CRLB can be achieved but I was having trouble
implementing the method.  I wanted to gather some feedback on other
people's real-world experience with the method before taking the time
to complete my implementation.  Any other comments or suggestions are
also appreciated.


Thanks,

Ken P.

On 29 Des, 17:29, KP <ken.pra...@gmail.com> wrote:
> On Dec 27, 10:49&#4294967295;am, Rune Allnor &#4294967295;wrote:

> Because we need to estimate multiple frequencies per sequence, we were
> using a DFT-based method which worked fairly well. &#4294967295;However, due to
> noise, we were having to use sequence lengths longer than can be
> optimally implemented in our processor (due to cache size, etc.).

There is a significant difference between 'we can not get this to
work' and 'we can not get this to work optimally'.

If you can get the methods you already tested to work at all,
even suboptimally, use them. If the operational constraints
pose problems, these can be solved by means of faster, larger
computers. Of course, that might take $$$ which might seem like
a big hurdle up front, but on the other hand it *only* takes
$$$ to get a larger faster computer. You don't risk aything
in terms of operational feasability or robustness.

If you can get the method to work, use it. If it works too
slow for your application, document this fact and apply for
the funding necessary to get more CPU power.

Rune