spectral estimation question

Randy Yates skrev:
> OK, here's one of those "This should be simple..." questions.
>
> We know that many (all?) methods of spectral estimation of
> discrete-time data rely fundamentally on the DFT (the N-point DFT).
>
> However, the output of a specific bin of the DFT can be viewed as a
> bandpass filter. This DFT bandpass filter is not particularly "good,"
> i.e., it has high side lobes and poor stop-band rejection.
>
> So, how do we ever get a good spectral estimate using such inherently
> poor filters?
>
> Now I'm pretty sure someone's going to bring up windowing, but in my
> view windowing is a technique to tradeoff resolution and out-of-band
> rejection due to the finite-extent of the data. The problem with DFT
> lobes is separate. I think...

The windowing techniques enter the picture, but as far as I am
concerned, they do so in a roundabout way.

I agree with your suggestion that the starting point is the
periodogram. As you undoubtly know, the variance of the
k'th coefficient, P[k], in the N-point periodogram is

Var{P[k]} = P[k]^2

Two observations: The variance is large, and it does not depend
on the number of data, N, that was used to generate the periodogram.

So there are two possible strategies to reduce the variance of the
periodogram coefficients, based on N available samples:

1) We can compute a number of shorter periodograms and
compute the average of those periodograms. The variance
of the resulting periodogram will be smaller, and we may
even be able to estimate some sort of confidence intervals.
The price to be paid is that we get fewer coefficients in the
power spectrum.

2) Instead of averaging periodograms, we might average
nearby bins in the periodogram. This is basically the same
as a convolution by a moving average filter applied in the
spectrum domain, which corresponds to a windowing in time
domain.

Both strategies (as well as the combination of the two, like
in Welch's method) result in the familiar window function
analysis. 

Rune

Jerry Avins skrev:
> Fred Marshall wrote:
>
>    ...
>
> > The main lobe width is inversely proportional to N and that's all there is
> > to it.
>
> Ah: but IF enough is known about the signal /a priori/ and IF what is
> known is sufficiently auspicious -- in other words if you already know
> [most of] the result you're looking for -- then you can trade what you
> know for smaller N. Aren't you as sick of hearing that as I am?

I am sick of it. If you know everything about the signal (or at least
the interesting parts) there is no need to make a measurement
in the first place. Everything you see in the data will cement your
prior "knowledge".

Rune

Randy Yates skrev:
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes:
>
> > "Randy Yates" <yates@ieee.org> wrote in message
> > news:m3fykvom5y.fsf@ieee.org...
> >> OK, here's one of those "This should be simple..." questions.
> >>
> >> We know that many (all?) methods of spectral estimation of
> >> discrete-time data rely fundamentally on the DFT (the N-point DFT).
> >>
> >> However, the output of a specific bin of the DFT can be viewed as a
> >> bandpass filter. This DFT bandpass filter is not particularly "good,"
> >> i.e., it has high side lobes and poor stop-band rejection.
> >>
> >> So, how do we ever get a good spectral estimate using such inherently
> >> poor filters?
> >>
> >> Now I'm pretty sure someone's going to bring up windowing, but in my
> >> view windowing is a technique to tradeoff resolution and out-of-band
> >> rejection due to the finite-extent of the data. The problem with DFT
> >> lobes is separate. I think...
> >
> > Randy,
> >
> > Not different.
>
> I think it is.
>
> Try this gedanken: We have a length of 1024 points of data that
> represent an entire, complete signal. That is, those 1024 points don't
> need to be windowed. We can even assume that several samples near the
> endpoints are already zero, and that this is part of the original data
> and not any result of windowing.

I don't follow your premise.

The signal you describe is a deterministic, finite-length signal.
The spectrum estimation techniques that are based on the
periodogram are derived under the assumption that the
data form a finite subset of a possibly infinite stochastic
process.

I find it hard to accept your stated case as being relevant
in the context of spectrum estimation.

> OK, now say we had a magic spectrum analyzer that gave us an EXACT
> spectrum of the signal,

For the finite-length discrete-time case, the DFT will do nicely.
No need for magic.

> and assume that this exact spectrum has
> a spike at \pi/20 rad/s and another at \pi/5 rad/s.
>
> If we run this signal through a 1024-point FFT, then, due to those
> blasted lousy bandpass filters, not only does the spike at \pi/5 rad/s
> show up in (I'll just pick a bin) bin 500, but also a little bit of
> the energy from the spike at \pi/20.
>
> So the FFT's spectrum result at bin 500 has an error in it that isn't
> a result of windowing but rather of the FFT's poor bandpass filters.
>
> Now instead of FFT bins, imagine we input the signal into 1024
> bandpass filters with REALLY good stop-band characteristics. Now
> the 500th filter shows (practically) only the energy from the
> spike at \pi/5 and none of that from the spike at \pi/20.
>
> Where is my error (if there is one)?
 
You are comparing apples and oranges.

Rune

Jerry Avins wrote:
> Randy Yates wrote:
> > "Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes:
> >
> >
> >>"Randy Yates" <yates@ieee.org> wrote in message
> >>news:m3fykvom5y.fsf@ieee.org...
> >>
> >>>OK, here's one of those "This should be simple..." questions.
> >>>
> >>>We know that many (all?) methods of spectral estimation of
> >>>discrete-time data rely fundamentally on the DFT (the N-point DFT).
> >>>
> >>>However, the output of a specific bin of the DFT can be viewed as a
> >>>bandpass filter. This DFT bandpass filter is not particularly "good,"
> >>>i.e., it has high side lobes and poor stop-band rejection.
> >>>
> >>>So, how do we ever get a good spectral estimate using such inherently
> >>>poor filters?
> >>>
> >>>Now I'm pretty sure someone's going to bring up windowing, but in my
> >>>view windowing is a technique to tradeoff resolution and out-of-band
> >>>rejection due to the finite-extent of the data. The problem with DFT
> >>>lobes is separate. I think...
> >>
> >>Randy,
> >>
> >>Not different.
> >
> >
> > I think it is.
> >
> > Try this gedanken: We have a length of 1024 points of data that
> > represent an entire, complete signal. That is, those 1024 points don't
> > need to be windowed. We can even assume that several samples near the
> > endpoints are already zero, and that this is part of the original data
> > and not any result of windowing.
> >
> > OK, now say we had a magic spectrum analyzer that gave us an EXACT
> > spectrum of the signal, and assume that this exact spectrum has
> > a spike at \pi/20 rad/s and another at \pi/5 rad/s.
> >
> > If we run this signal through a 1024-point FFT, then, due to those
> > blasted lousy bandpass filters, not only does the spike at \pi/5 rad/s
> > show up in (I'll just pick a bin) bin 500, but also a little bit of
> > the energy from the spike at \pi/20.
> >
> > So the FFT's spectrum result at bin 500 has an error in it that isn't
> > a result of windowing but rather of the FFT's poor bandpass filters.
> >
> > Now instead of FFT bins, imagine we input the signal into 1024
> > bandpass filters with REALLY good stop-band characteristics. Now
> > the 500th filter shows (practically) only the energy from the
> > spike at \pi/5 and none of that from the spike at \pi/20.
> >
> > Where is my error (if there is one)?
>
> I think that the assumptions
> A) the complete signal has a duration 1024 samples, and
> B) its frequencies are representable by isolated spikes
> are mutually exclusive, so that the conditions for your gedanken
> experiment can't be realized.

The problem here is the confusion of two different ideas which
just happen to be described by one word.  In common practical
science and engineering usage, signals can have both a finite
duration and a single frequency.  The purest oscillator will
shut off when you pull the power plug (or an elementary particle
decays or is absorbed).  However, the sampling theorem requires
bandlimited signals which cannot have a limited non-zero time
extent (e.g. stuff that doesn't exist except as an abstraction).
So the word frequency in this realm means something slightly
different, and perhaps not as intuitive depending on the audience.
I think that it might be clearer if these mathematical abstract
periodicities due to use of various sampling and DFT theorems
were called something different, maybe theoretical or abstract
frequencies.  It seems perfectly reasonable to call the single
frequency, by inspection, of a time limited non-periodic signal
as simply its frequency.


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

Randy Yates wrote:
> "HelpmaBoab" <FU2@yahoo.co.zpc> writes:
>
> > "Randy Yates" <yates@ieee.org> wrote in message
> > news:m3fykvom5y.fsf@ieee.org...
> >> OK, here's one of those "This should be simple..." questions.
> >>
> >> We know that many (all?) methods of spectral estimation of
> >> discrete-time data rely fundamentally on the DFT (the N-point DFT).
> >>
> >> However, the output of a specific bin of the DFT can be viewed as a
> >> bandpass filter. This DFT bandpass filter is not particularly "good,"
> >> i.e., it has high side lobes and poor stop-band rejection.
> >>
> >> So, how do we ever get a good spectral estimate using such inherently
> >> poor filters?
> >>
> >> Now I'm pretty sure someone's going to bring up windowing, but in my
> >> view windowing is a technique to tradeoff resolution and out-of-band
> >> rejection due to the finite-extent of the data. The problem with DFT
> >> lobes is separate. I think...
> >>
> > You can use parameter estimation methods to get smoother results eg RLS,Burg
> > method etc etc
>
> Hi Tam,
>
> Well, thanks!? I didn't really mean for anyone to answer that question
> directly. I meant to ask for verification that using the DFT does
> indeed produce the problem I'm thinking it does in my head.

An FFT/DFT is a transform to another basis.  When you change the
"angle" you look at a vector, some things become clearer, and
some things are become more obscure.  One of the things obscured
is the frequency of signals between the bins.  The obscuration can
often be cleared up, either by going back to the time domain, by
using more than one filter bin (interpolation), or by adding to
the set of DFT basis functions (even though this may overdetermine
the result vector).  Phase-vocoder-like methods add filters offset
in time.  Time frequency reassignments adds basis functions at
the same frequency, but with different window weightings.


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

Randy Yates wrote:
> "HelpmaBoab" <FU2@yahoo.co.zpc> writes:
>
> > "Randy Yates" <yates@ieee.org> wrote in message
> > news:m3fykvom5y.fsf@ieee.org...
> >> OK, here's one of those "This should be simple..." questions.
> >>
> >> We know that many (all?) methods of spectral estimation of
> >> discrete-time data rely fundamentally on the DFT (the N-point DFT).
> >>
> >> However, the output of a specific bin of the DFT can be viewed as a
> >> bandpass filter. This DFT bandpass filter is not particularly "good,"
> >> i.e., it has high side lobes and poor stop-band rejection.
> >>
> >> So, how do we ever get a good spectral estimate using such inherently
> >> poor filters?
> >>
> >> Now I'm pretty sure someone's going to bring up windowing, but in my
> >> view windowing is a technique to tradeoff resolution and out-of-band
> >> rejection due to the finite-extent of the data. The problem with DFT
> >> lobes is separate. I think...
> >>
> > You can use parameter estimation methods to get smoother results eg RLS,Burg
> > method etc etc
>
> Hi Tam,
>
> Well, thanks!? I didn't really mean for anyone to answer that question
> directly. I meant to ask for verification that using the DFT does
> indeed produce the problem I'm thinking it does in my head.

An FFT/DFT is a transform to another basis.  When you change the
"angle" you look at a vector, some things become clearer, and
some things are become more obscure.  One of the things obscured
is the frequency of a signal between the bins.  The obscuration can
often be cleared up, either by going back to the time domain,
using more than one filter bin (interpolation), or by adding to
the set of DFT basis functions (even though this may overdetermine
the result vector).  Phase-vocoder-like methods add filters offset
in time.  Time frequency reassignments adds basis functions at
the same frequency, but with different window weightings.


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

"Jerry Avins" <jya@ieee.org> wrote in message 
news:68udnR9Zq5B8463ZnZ2dnUVZ_tidnZ2d@rcn.net...
> Fred Marshall wrote:
>
>   ...
>
>> The main lobe width is inversely proportional to N and that's all there 
>> is to it.
>
> Ah: but IF enough is known about the signal /a priori/ and IF what is 
> known is sufficiently auspicious -- in other words if you already know 
> [most of] the result you're looking for -- then you can trade what you 
> know for smaller N. Aren't you as sick of hearing that as I am?

YES!!! 

"Ron N." <rhnlogic@yahoo.com> wrote in message 
news:1144102071.366368.279290@e56g2000cwe.googlegroups.com...
> Jerry Avins wrote:
>> Randy Yates wrote:
>> > "Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes:
>> >
>> >
>> >>"Randy Yates" <yates@ieee.org> wrote in message
>> >>news:m3fykvom5y.fsf@ieee.org...
>> >>
>> >>>OK, here's one of those "This should be simple..." questions.
>> >>>
>> >>>We know that many (all?) methods of spectral estimation of
>> >>>discrete-time data rely fundamentally on the DFT (the N-point DFT).
>> >>>
>> >>>However, the output of a specific bin of the DFT can be viewed as a
>> >>>bandpass filter. This DFT bandpass filter is not particularly "good,"
>> >>>i.e., it has high side lobes and poor stop-band rejection.
>> >>>
>> >>>So, how do we ever get a good spectral estimate using such inherently
>> >>>poor filters?
>> >>>
>> >>>Now I'm pretty sure someone's going to bring up windowing, but in my
>> >>>view windowing is a technique to tradeoff resolution and out-of-band
>> >>>rejection due to the finite-extent of the data. The problem with DFT
>> >>>lobes is separate. I think...
>> >>
>> >>Randy,
>> >>
>> >>Not different.
>> >
>> >
>> > I think it is.
>> >
>> > Try this gedanken: We have a length of 1024 points of data that
>> > represent an entire, complete signal. That is, those 1024 points don't
>> > need to be windowed. We can even assume that several samples near the
>> > endpoints are already zero, and that this is part of the original data
>> > and not any result of windowing.
>> >
>> > OK, now say we had a magic spectrum analyzer that gave us an EXACT
>> > spectrum of the signal, and assume that this exact spectrum has
>> > a spike at \pi/20 rad/s and another at \pi/5 rad/s.
>> >
>> > If we run this signal through a 1024-point FFT, then, due to those
>> > blasted lousy bandpass filters, not only does the spike at \pi/5 rad/s
>> > show up in (I'll just pick a bin) bin 500, but also a little bit of
>> > the energy from the spike at \pi/20.
>> >
>> > So the FFT's spectrum result at bin 500 has an error in it that isn't
>> > a result of windowing but rather of the FFT's poor bandpass filters.
>> >
>> > Now instead of FFT bins, imagine we input the signal into 1024
>> > bandpass filters with REALLY good stop-band characteristics. Now
>> > the 500th filter shows (practically) only the energy from the
>> > spike at \pi/5 and none of that from the spike at \pi/20.
>> >
>> > Where is my error (if there is one)?
>>
>> I think that the assumptions
>> A) the complete signal has a duration 1024 samples, and
>> B) its frequencies are representable by isolated spikes
>> are mutually exclusive, so that the conditions for your gedanken
>> experiment can't be realized.
>
> The problem here is the confusion of two different ideas which
> just happen to be described by one word.  In common practical
> science and engineering usage, signals can have both a finite
> duration and a single frequency.  The purest oscillator will
> shut off when you pull the power plug (or an elementary particle
> decays or is absorbed).  However, the sampling theorem requires
> bandlimited signals which cannot have a limited non-zero time
> extent (e.g. stuff that doesn't exist except as an abstraction).
> So the word frequency in this realm means something slightly
> different, and perhaps not as intuitive depending on the audience.
> I think that it might be clearer if these mathematical abstract
> periodicities due to use of various sampling and DFT theorems
> were called something different, maybe theoretical or abstract
> frequencies.  It seems perfectly reasonable to call the single
> frequency, by inspection, of a time limited non-periodic signal
> as simply its frequency.

Long ago I made the suggestion that folks should be clear whether the 
discussion was theoretical or pratical.......  We continue to mix the two 
and cause these "discussions"... 

Randy Yates wrote:
> OK, here's one of those "This should be simple..." questions.
>
> We know that many (all?) methods of spectral estimation of
> discrete-time data rely fundamentally on the DFT (the N-point DFT).
>
> However, the output of a specific bin of the DFT can be viewed as a
> bandpass filter. This DFT bandpass filter is not particularly "good,"
> i.e., it has high side lobes and poor stop-band rejection.
>
> So, how do we ever get a good spectral estimate using such inherently
> poor filters?

Note that some of the better methods of spectral estimation do not
use a single poor quality bandpass filter (one DFT or FFT bin), but
several of them together (say 3 adjacent bins for some interpolation
scheme, parabolic, triangular, inverse sinc, etc.)  The frequency
information content of multiple bin filters can be interpreted as an
intermediate stage of a filter with better bandpass characteristics.
With all N bins, the information is complete and the data can be
reconstructed for use inside any filter.  Less than N bins and the
spectral information is "concentrated" by the basis transform so
that most of some frequency component is in a lesser number of bins
than the total number of samples.


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

"Randy Yates" <yates@ieee.org> wrote in message 
news:m3wte7l7at.fsf@ieee.org...
> "Fred Marshall" <fmarshallx@remove_the_x.acm.org> writes:
>
>> "Randy Yates" <yates@ieee.org> wrote in message
>> news:m3fykvom5y.fsf@ieee.org...
>>> OK, here's one of those "This should be simple..." questions.
>>>
>>> We know that many (all?) methods of spectral estimation of
>>> discrete-time data rely fundamentally on the DFT (the N-point DFT).
>>>
>>> However, the output of a specific bin of the DFT can be viewed as a
>>> bandpass filter. This DFT bandpass filter is not particularly "good,"
>>> i.e., it has high side lobes and poor stop-band rejection.
>>>
>>> So, how do we ever get a good spectral estimate using such inherently
>>> poor filters?
>>>
>>> Now I'm pretty sure someone's going to bring up windowing, but in my
>>> view windowing is a technique to tradeoff resolution and out-of-band
>>> rejection due to the finite-extent of the data. The problem with DFT
>>> lobes is separate. I think...
>>
>> Randy,
>>
>> Not different.
>
> I think it is.
>
> Try this gedanken: We have a length of 1024 points of data that
> represent an entire, complete signal. That is, those 1024 points don't
> need to be windowed. We can even assume that several samples near the
> endpoints are already zero, and that this is part of the original data
> and not any result of windowing.

***Well, OK but we have to assume one of two things:
1) The "complete signal" is periodic and these samples represent one or more 
integral periods.
OR
2) The "complete signal" before sampling had periodic zeros at the sampling 
interval - thus all those zero samples at the ends.   This is the case 
because the signal has to be bandlimited, thus be of infinite duration, 
before sampling.

All that is theoretical (and useful) of course.

>
> OK, now say we had a magic spectrum analyzer that gave us an EXACT
> spectrum of the signal, and assume that this exact spectrum has
> a spike at \pi/20 rad/s and another at \pi/5 rad/s.

OK, well is this a continuous spectrum analyzer or a discrete spectrum 
analyzer?
I will assume continous for now....
And, I will assume that there are corresponding spikes at negative 
frequencies just to keep things simple and the time domain function real.
In that case, the signal can't have the spectrum you describe because there 
will be nonzero samples outside the 1024 samples.
If you insist that the signal is limited to the time epoch spanned by the 
eventual 1024 samples one would take then that window imposes the frequency 
leakage - before any FFT or analysis or ....

>
> If we run this signal through a 1024-point FFT, then, due to those
> blasted lousy bandpass filters, not only does the spike at \pi/5 rad/s
> show up in (I'll just pick a bin) bin 500, but also a little bit of
> the energy from the spike at \pi/20.

***What signal?  The so-called "complete signal" of 1024 samples?
That ain't the same thing as what the magic spectrum analyzer looked at.
As above.

>
> So the FFT's spectrum result at bin 500 has an error in it that isn't
> a result of windowing but rather of the FFT's poor bandpass filters.

***Nope.  It's the result of the window.

>
> Now instead of FFT bins, imagine we input the signal into 1024
> bandpass filters with REALLY good stop-band characteristics. Now
> the 500th filter shows (practically) only the energy from the
> spike at \pi/5 and none of that from the spike at \pi/20.

***Such filters will have an impulse response that's likely longer than the 
1024 samples and 1024 samples will never get the filter to steady state. 
But you said "practically"....

***Let's talk about discrete signals and spectra and examine the length of 
those really good filters:
Take a sequence of 1024 samples and zero pad both ends so there are a total 
of 4,096 samples.
We make no statement about the content of the 1024 samples other than the 
Nyquist criterion was met.

***Now we build those pretty good filters which have a bandpass of 
4,096/1024 = 4 samples in frequency.  Hmmmm.   That's not going to be a very 
good filter because its transition width on each side is 1/4 its bandwidth 
and there's very little ability to control the stopband.    These are 
filters of length 4,096.  One might be motivated to make them longer to make 
them "better".  But, even with 4096, the sequence of 1024 samples will never 
reach steady state.  This is a practical result that says the signal and the 
filter don't work together as we'd like.

One might think that in order to make the filters better one has to at least 
window their temporal response.  BUT windowing the temporal response does 
little good because of all those zeros in the sequence we intend to filter - 
because the signal is truncated in time.

Fred