A More Accurate Fourier Transform

[MathGeek314]

A colleague and I are looking for feedback on a technique we've implemented and code we've written to use Fourier transforms to determine frequency, phase, and amplitude of oscillatory components more accurately. This program has the same functionality as an FFT (Fast Fourier transform), but due to modern computing speeds, does not use an FFT method.

Code is here:

https://sourceforge.net/projects/amoreaccuratefouriertransform/

Paper describing it is here:

http://arxiv.org/pdf/1507.01832v1.pdf

Please have a look and tell us what you think.

 

[amanuensis]

It could be very useful in experimental modal analysis.
Does the method work with short-duration time signal ?

 

[GregLocock]

Your EI appears to offer frequency resolution better than 1/T. Is this the case?

Sorry now I've actually read the discussion, not just looked at the graphs. It seems to me that this method suffers from the well known pitfalls of zero padding. That is, you are assuming that there is only one peak of interest inside each 1/T bin, amongst others.

http://www.ni.com/tutorial/4880/en/

Cheers

Greg Locock


New here? Try reading these, they might help FAQ731-376

http://eng-tips.com/market.cfm?

 

[MathGeek314]

//Your EI appears to offer frequency resolution better than 1/T. Is this the case?

Sorry now I've actually read the discussion, not just looked at the graphs. It seems to me that this method suffers from the well known pitfalls of zero padding. That is, you are assuming that there is only one peak of interest inside each 1/T bin, amongst others. //

Almost. Like zero padding, you are gaining a smaller step size, but the ability to resolve two distinct peaks in a frequency span of 1/T has some subtleties. If you know the actual shape of a single component peak (from a single frequency) that results from the window function, you can then work with two peaks of that given shape and do a non-linear least squares fit to the resulting Fourier transform output. This technique can determine the amplitude and frequency of two components under a single broadened peak even if you cannot resolve two distinct peaks by trying different window functions. Being able to get as many points as you like under each peak makes it simple to fit the resulting peaks to the sum of individual "peak" functions with an appropriate non-linear least squares approach.

The other advantages over the FFT are that (for single components), the amplitude can be determined with accuracy even in cases where it is not directly under an FFT bin. For resolved peaks, the phase can also be determined accurately. I've never appreciated the phase accuracy of FFTs (woth or without zero padding) or the gyrations needed to get accurate amplitudes in the same units as the original signal. With the EI method, the only issue getting the amplitude in the same units is adjusting in the well-known manner for the window function.

Finally, in extreme cases, one can take 10-100 points under a single peak. A comparable approach with zero padding requires creating a data set that is 90-99% zeros.

 

[MathGeek314]

//It could be very useful in experimental modal analysis.
Does the method work with short-duration time signal ?//

The method will always work as well or (usually) better than FFT with no requirement to be a power of 2 number of points and no penalty for any number of points. It is the most accurate Fourier transform possible with a given number of points, and they need not even be equally spaced!

 

[amanuensis]

It's amazing.

There is a super easy criterion to know whether that can be useful.

How many points can be plotted in a frequency range (Delta F) where Delta F is -3 dB frequency band around a peak ?
Does this number depend on the peak frequency ?
Does this number depend on sampling time (Delta T) and acquisition time (Length) of the signal ?

For example if the ratio (Delta F)/F = 0.001,
how many points can be obtained if F = 10Hz or if F = 100Hz ?

Is there an inverse transform ?

If it works, you gonna change the world.

 

[MathGeek314]

//How many points can be plotted in a frequency range (Delta F) where Delta F is -3 dB frequency band around a peak ?//

As many as the user desires, limited only by computation time. We've done a lot of testing with 10 and 100 points per FFT bin (1/T).

//Does this number depend on the peak frequency ?//

No.

//Does this number depend on sampling time (Delta T) and acquisition time (Length) of the signal ?//

Since the method computes an explicit numerical integral, the sampling time (step size) need not even be uniform. But if the sampling time is uniform, it effects only the maximum meaningful frequency (in the usual way). Further, the Fourier transform can be computed over any desired range of meaningful frequencies. One need not compute from Fmin = 0 Hz to Fmax = sample rate/2. If only a few peaks of approximately known frequencies are of interest, one need only compute the frequency spectrum under those peaks.

//For example if the ratio (Delta F)/F = 0.001,
how many points can be obtained if F = 10Hz or if F = 100Hz ?//

100 or 1000 or 100,000. Whatever the user desires. Our testing has shown (depending on the noise level), computing 100 points per FFT bin can yield more accurate determinations of the frequency and phase that correspond to a single peak.

//Is there an inverse transform ?//

We've written and tested code for it, but it is not included in the release. There are already a lot of inverse transforms out there, and we didn't see the demand, since the advantages of our method are mostly limited to data analysis applications limited to frequency analysis. As far as we can tell, applications that use inverse transforms won't really benefit from our method compared with traditional methods. Since the code has been released, we've had over 100 downloads per week, and no one has expressed an interest in the inverse transform.