Path: utzoo!attcan!uunet!zephyr.ens.tek.com!tekcrl!tekfdi!videovax!bart
From: bart@videovax.tv.tek.com (Bart Massey)
Newsgroups: comp.dsp
Subject: Re: FFTs of Low Frequency Signals (really: decimation)
Message-ID: <5630@videovax.tv.tek.com>
Date: 16 Nov 89 23:41:40 GMT
References: <5619@videovax.tv.tek.com> <10208@cadnetix.COM> <2586@irit.oakhill.UUCP> <5305@orca.WV.TEK.COM> <5622@videovax.tv.tek.com> <98204@ti-csl.csc.ti.com>
Reply-To: bart@videovax.tv.tek.com (Bart Massey)
Organization: Tektronix TV Measurement Systems, Beaverton OR
Lines: 58

In article <98204@ti-csl.csc.ti.com> oh@m2.UUCP (Stephen Oh) writes:
> I agree with Bart that ARMA estimators are better than FFTs. However, I don't
> see any reason (expect one, I will discuss about this later) why we should use
> ARMA estimators instead of AR estimators. If you want to pick sinusoids out of
> white noise with moderate computations,  you should use AR estimators.

No.  If there's significant noise, you want to use ARMA estimators -- the MA
process zeros are necessary for accurately representing the white noise
itself.  See, e.g., Steven M. Kay, Modern Spectral Estimation, ISBN
0-13-598582-X, p. 131 -- he suggests using an ARMA(2,2) model to estimate
the spectra of a sinusoid (actually an AR(2) process) in white noise.

> One more comment: 
>       In order to improve the statistical stability of FFTs,
>       it is very common to use psuedo ensemble average by segments of data.
>       This causes the reduction of resolutions of PSD.
>       So if you want to increase the resolution as well as to improve the
>       stability, you need *lots* of computations. Because of this fact, I
>       don't think that AR estimators are computationally more expensive
>       than FFTs.

No.  Note that ARMA models are no more "statistically stable" than DFTs --
small variations in the input data may have large effects on the model
parameters.  See Kay p. 331, Figure 10.6(b) for an example.  The reason that
the FFT is done in segments usually has to do with available input storage
or desired output resolution, and the reason that the segments are
overlapped somewhat ("pseudo ensemble averaging") is often to avoid inducing
artificial "end effects" in the data rather than for statistical stability.
If you have an ARMA model, you should certainly run it over all the data you
can accumulate, or until you're certain that its parameters are sufficiently
stable, and the same is true for a DFT.

The other important thing to note is that (at least as I understand it) ARMA
estimators are roughly O(N^2) ops per data point, whereas the FFT is
O(N lg N).  This means that the overlap isn't very expensive compared to the
ARMA model.  In fact, you can do O(N/lg N) FFTs on N points in the same
amount of time it takes to run an ARMA model of equivalent resolving power
-- e.g. if N = 1000, then O(N/lg N) == 100.  This leaves *plenty* of time
for overlaps in the FFTs.

But then again, it depends on what you want to estimate.  If you "know" that
your input data consists of two sinusoids in white noise, all the cost
tradeoffs change, and I wouldn't be surprised to find that the ARMA model is
cheaper, because you can use a very low-order model (ARMA(4,4)) to get a
good estimate.  The DFT *is* the ML spectral estimator, in the absence of
any a priori model whatsoever of the input data, and it's very cheap to
compute via the FFT.  If you have a data model, the DFT is, as I understand
it, a poorer choice.

And again, if you only have 16 data points, and can't obtain more, order
analysis is really uninteresting, since the size of the implicit constants
dominates, and besides, neither method takes significant time.  There,
questions of what exactly it is you're looking for in those 16 data points
become dominant, and will usually govern your choice of analytic techniques.

					Bart Massey
					..tektronix!videovax.tv.tek.com!bart
					..tektronix!reed.bitnet!bart