Resolving frequencies in an oversampled spectrum

Thank you all,
I greatly appreciate the input.  Unfortunately the e-book mentioned is
not part of the collection at the library I have access to.  Does
anybody know of suitable web-links for either ESPRIT or for the
suitable Prony (Proni?) method?


Thanks,
Dan


cf wrote:
> Vladimir Vassilevsky wrote:
> >
> >
> > Dan K wrote:
> >
> >> I have a time series which is highly oversampled.  After low pass
> >> filtering, I have about 17,000 data points.  In that span I have a very
> >> low frequency signal (about 1/50th of a period), two more moderate
> >> frequency signals (can be between 1 and 8 periods) and the sum of those
> >> two signals.  From sweep to sweep the two signals will both move
> >> together in frequency space (by very small amounts) and their relative
> >> intensities can change dramatically.  What I need is a high accuracy
> >> method of determining the frequency of these two signals.
> >
> > If you can describe your signals as the models with the unknown
> > parameters, you can apply the Proni algorithm or some other method of
> > the parametric estimation.
> >
> > For example, if your signal is described by a model Y = A sin(Wt + Fi)
> > with A, W, Fi as the unknown parameters, you can solve for the values
> > which provide the best fit with your data.
> >
> > This is a very accurate method although it takes a lot of computation.
> >
> >
> > Vladimir Vassilevsky
> >
> > DSP and Mixed Signal Design Consultant
> >
> > http://www.abvolt.com
>
> Hi Dan,
>
> I agree with Vladimir.  If your signal model is sinusoidal, you can
> probably try using a high resolution parameteric estimation method like
> ESPRIT (Estimation of Signal Parameters via Rotational Invariance
> Technique) where the parameters you are trying to estimate are the
> different frequencies.  It basically involves partitioning your data
> into two overlap sets, e.g. x0 - x10000 and x9000 - x17000.  Then you
> will see that the second set of data is just a phase shifted version of
> the first set.  From this relationship, you can obtain a general eigen
> equation such that the frequency estimates are contained inside the
> eigenvalue matrix.  I found that this technique works reasonably well
> (measure by the variance of the estimates) starting at about SNR = 15 dB
> and improve as the SNR increases.  For detail, I suggest you look at
> some advanced DSP book like:
>
> Manolakis, Ingle, Kogon, "Statistical and adaptive signal processing :
> spectral estimation, signal modeling, adaptive filtering, and array
> processing", 2005.
>
> This is an e-book so you should be able to view it from an university's
> library website.
> 
> Hope this helps,
> 
> cf

Jeff,
Thank you for the hint.  Could you post (or email me) a citation on
this article that you mentioned?  Also, is this a plausibly
implementable approach?  What I mean is that while my processing speeds
are reasonably flexible, some of the brute force methods are too slow
(e.g. a massive genetic algorithm for fitting, etc).  I would need to
be able to complete the process on a spectrum in something less than
say 5 seconds.  Thanks,
Dan



Jeff Caunter wrote:
> >I would really, really appreciate any help on this one. I am by no
> >means an expert in dsp (I'm learning as I go), but if you can give me
> >even a hint, I can try to work from there.
>
> So here's a hint - very accurate estimates of frequency can be made by
> observing the spectral phase change in a target bin between two (or more)
> adjacent (or overlapping) FFTs. The point-sizes of the FFTs will depend on
> the spectral resolution required to resolve your two frequencies into
> separate bins (preferably more than two bins apart). Note that this is
> quite different from choosing a resolution to match the frequency accuracy
> you require - the FFTs can therefore be quite modest in size in many
> instances.
>
> Using this technique I have measured frequencies to an accuracy of better
> than 0.0001% using FFTs wih point-sizes as small as 32. I wrote a paper on
> this some years ago which detailed how the phase differences need to be
> interpreted for varying overlap factors, and which highlighted the
> difference in behaviour between odd and even bins. I do not have this
> paper to hand right now - maybe I should resurrect it and publish it on
> the web if it is of any general interest. I do seem to remember that the
> principles and necessary correction factors were quite simple, and easy to
> apply 'blind' to the spectrum - resulting in a modified 'spectrum' which
> now held accurate frequency values rather than spectrum magnitudes.
> 
> Jeff

"Dan K" <dkominsky@primephotonics.com> writes:

> Thank you all,
> I greatly appreciate the input.  Unfortunately the e-book mentioned is
> not part of the collection at the library I have access to.  Does
> anybody know of suitable web-links for either ESPRIT or for the
> suitable Prony (Proni?) method?

Dan,

I haven't been following, but you might try Peter K's frequency
estimation page for resources:

  http://home.comcast.net/~kootsoop/freqalgs.htm

Best of luck!

--Randy

>
>
> Thanks,
> Dan
>
>
> cf wrote:
>> Vladimir Vassilevsky wrote:
>> >
>> >
>> > Dan K wrote:
>> >
>> >> I have a time series which is highly oversampled.  After low pass
>> >> filtering, I have about 17,000 data points.  In that span I have a very
>> >> low frequency signal (about 1/50th of a period), two more moderate
>> >> frequency signals (can be between 1 and 8 periods) and the sum of those
>> >> two signals.  From sweep to sweep the two signals will both move
>> >> together in frequency space (by very small amounts) and their relative
>> >> intensities can change dramatically.  What I need is a high accuracy
>> >> method of determining the frequency of these two signals.
>> >
>> > If you can describe your signals as the models with the unknown
>> > parameters, you can apply the Proni algorithm or some other method of
>> > the parametric estimation.
>> >
>> > For example, if your signal is described by a model Y = A sin(Wt + Fi)
>> > with A, W, Fi as the unknown parameters, you can solve for the values
>> > which provide the best fit with your data.
>> >
>> > This is a very accurate method although it takes a lot of computation.
>> >
>> >
>> > Vladimir Vassilevsky
>> >
>> > DSP and Mixed Signal Design Consultant
>> >
>> > http://www.abvolt.com
>>
>> Hi Dan,
>>
>> I agree with Vladimir.  If your signal model is sinusoidal, you can
>> probably try using a high resolution parameteric estimation method like
>> ESPRIT (Estimation of Signal Parameters via Rotational Invariance
>> Technique) where the parameters you are trying to estimate are the
>> different frequencies.  It basically involves partitioning your data
>> into two overlap sets, e.g. x0 - x10000 and x9000 - x17000.  Then you
>> will see that the second set of data is just a phase shifted version of
>> the first set.  From this relationship, you can obtain a general eigen
>> equation such that the frequency estimates are contained inside the
>> eigenvalue matrix.  I found that this technique works reasonably well
>> (measure by the variance of the estimates) starting at about SNR = 15 dB
>> and improve as the SNR increases.  For detail, I suggest you look at
>> some advanced DSP book like:
>>
>> Manolakis, Ingle, Kogon, "Statistical and adaptive signal processing :
>> spectral estimation, signal modeling, adaptive filtering, and array
>> processing", 2005.
>>
>> This is an e-book so you should be able to view it from an university's
>> library website.
>> 
>> Hope this helps,
>> 
>> cf
>

-- 
%  Randy Yates                  % "...the answer lies within your soul
%% Fuquay-Varina, NC            %       'cause no one knows which side
%%% 919-577-9882                %                   the coin will fall."
%%%% <yates@ieee.org>           %  'Big Wheels', *Out of the Blue*, ELO
http://home.earthlink.net/~yatescr

Dan, is your problem one of resolving two frequencies
that are very close together? If so, then there are
"zoom" fft methods that allow you to get a close-up
look at one narrow slice of the spectrum.

Olin Perry Norton

Yes, this is precisely my problem.  I've tried the chirp z transform,
which I thought would do it, but it looked just like the fft of a zero
padded signal (i.e. smooth curves for each frequency, but my
frequencies are close enough together that they are still in one
"hump".  Have I missed something?  Is there a different transform that
I should have looked at?  Or do I just not understand how to
use/interpret the results I have?  Thanks.



Olin Perry Norton wrote:
> Dan, is your problem one of resolving two frequencies
> that are very close together? If so, then there are
> "zoom" fft methods that allow you to get a close-up
> look at one narrow slice of the spectrum.
> 
> Olin Perry Norton

If the two frequencies are so close together that they cannot be separately
resolved by Fourier Transforms, then the hint I suggested has no chance of
working.

Can you give more details - Sample rate, range of frequency over which the
two signals span, and an indication of the frequency difference between the
two signals?

Jeff

"Dan K" <dkominsky@primephotonics.com> writes:

> Thank you all,
> I greatly appreciate the input.  Unfortunately the e-book mentioned is
> not part of the collection at the library I have access to.  Does
> anybody know of suitable web-links for either ESPRIT or for the
> suitable Prony (Proni?) method?

Hey Dan,

Idea: If you know a-priori that the two frequencies are very close,
and you have some idea where, then why not bandpass-filter and
then decimate? Then the signals in the result should not be "close"
together anymore.

--Randy

>
>
> Thanks,
> Dan
>
>
> cf wrote:
>> Vladimir Vassilevsky wrote:
>> >
>> >
>> > Dan K wrote:
>> >
>> >> I have a time series which is highly oversampled.  After low pass
>> >> filtering, I have about 17,000 data points.  In that span I have a very
>> >> low frequency signal (about 1/50th of a period), two more moderate
>> >> frequency signals (can be between 1 and 8 periods) and the sum of those
>> >> two signals.  From sweep to sweep the two signals will both move
>> >> together in frequency space (by very small amounts) and their relative
>> >> intensities can change dramatically.  What I need is a high accuracy
>> >> method of determining the frequency of these two signals.
>> >
>> > If you can describe your signals as the models with the unknown
>> > parameters, you can apply the Proni algorithm or some other method of
>> > the parametric estimation.
>> >
>> > For example, if your signal is described by a model Y = A sin(Wt + Fi)
>> > with A, W, Fi as the unknown parameters, you can solve for the values
>> > which provide the best fit with your data.
>> >
>> > This is a very accurate method although it takes a lot of computation.
>> >
>> >
>> > Vladimir Vassilevsky
>> >
>> > DSP and Mixed Signal Design Consultant
>> >
>> > http://www.abvolt.com
>>
>> Hi Dan,
>>
>> I agree with Vladimir.  If your signal model is sinusoidal, you can
>> probably try using a high resolution parameteric estimation method like
>> ESPRIT (Estimation of Signal Parameters via Rotational Invariance
>> Technique) where the parameters you are trying to estimate are the
>> different frequencies.  It basically involves partitioning your data
>> into two overlap sets, e.g. x0 - x10000 and x9000 - x17000.  Then you
>> will see that the second set of data is just a phase shifted version of
>> the first set.  From this relationship, you can obtain a general eigen
>> equation such that the frequency estimates are contained inside the
>> eigenvalue matrix.  I found that this technique works reasonably well
>> (measure by the variance of the estimates) starting at about SNR = 15 dB
>> and improve as the SNR increases.  For detail, I suggest you look at
>> some advanced DSP book like:
>>
>> Manolakis, Ingle, Kogon, "Statistical and adaptive signal processing :
>> spectral estimation, signal modeling, adaptive filtering, and array
>> processing", 2005.
>>
>> This is an e-book so you should be able to view it from an university's
>> library website.
>> 
>> Hope this helps,
>> 
>> cf
>

-- 
%  Randy Yates                  % "Ticket to the moon, flight leaves here today 
%% Fuquay-Varina, NC            %  from Satellite 2"
%%% 919-577-9882                % 'Ticket To The Moon' 
%%%% <yates@ieee.org>           % *Time*, Electric Light Orchestra
http://home.earthlink.net/~yatescr

On Oct 13, 11:53 am, "Dan K" <dkomin...@primephotonics.com> wrote:
> Help please:
>
> I have a time series which is highly oversampled.  After low pass
> filtering, I have about 17,000 data points.  In that span I have a very
> low frequency signal (about 1/50th of a period), two more moderate
> frequency signals (can be between 1 and 8 periods) and the sum of those
> two signals.  From sweep to sweep the two signals will both move
> together in frequency space (by very small amounts) and their relative
> intensities can change dramatically.

One possibility is not to look for the two frequencies
directly, but look for the small changes from sweep to sweep.
That could cut down the search space by quite a bit, especially
if you know how well the signals track and the max frequency
deltas.

> What I need is a high accuracy
> method of determining the frequency of these two signals.  The near DC
> component and the sum frequency are pretty much irrelevent to me (as
> both are typically low amplitude, anyhow).
>
> What I have done so far:
> average subtract the raw data
> Low pass filter the result (there is high frequency noise on it)
> chop the zones which are in the filter's group delay zone
> Apply a raised cosine window

Note that the window will fatten up the main lobe in exchange
for  dropping the "noise" floor of the skirts.  If your two
signals are less than a few periods apart, then you don't want
to fatten up the main lobes, since that would tend to hide
your second signal, and you don't care about the skirts because
your signals aren't there (assuming a low enough noise level).
Also if the lowest frequency is near one period, then a one
period window could well alias or cancel a big portion of
your signal.  So I would consider dropping the cosine window
if the previous sweep so indicates.

> zero pad (or not)
> dft....

Note that if your noise level is zero (or close enough) you
are really only looking for 6 unknowns (2 frequencies, 2
amplitudes, and 2 phases),  so solving (or approximating)
requires only 6 data points.  In the complex domain, you are
looking for the position, tilt, and height of 2 sinc functions
(still only 6 unknowns) but you now only need 3 data points
(perhaps the centroid and a couple of the neighbors).

So I would start by looking in the complex fft results at the
centroid hump, its position, width, angular twist and
skewness; and see how those changed from the previous
sweep(s).


IMHO. YMMV.
-- 
Ron N.
http://www.nicholson.com/rhn

Dan wrote:
> Yes, this is precisely my problem.  I've tried the chirp z transform,
> which I thought would do it, but it looked just like the fft of a zero
> padded signal (i.e. smooth curves for each frequency, but my
> frequencies are close enough together that they are still in one
> "hump".

If your two frequencies are that close together, then you
might be able to use some amplitude envelope measurements
to look at the beat frequency produced by the two.  The modulation
frequency and the depth of the modulation should give you a
difference frequency and an amplitude ratio, which you should
then be able to combine with the fft "hump" centroid and skew
direction to give you an estimate of your two frequencies.


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

Rune Allnor wrote:
> I'd go with Prony's method. Certain variations of the algorithm are
> very
> tolerant for noise. Don't worry about the computational load; with some
> skill in setting up the problem, it will not be a problem.

I've had a lot of success with the filter-diagonalization method (which
unlike Prony's method gives you amplitudes in addition to the [complex]
frequencies), which was originally developed for problems in NMR
spectroscopy.  I've posted a free implementation of the method at
ab-initio.mit.edu/harminv in case it is helpful.

Regards,
Steven G. Johnson