Forums

Fast Fourier Transform with Wavelets - Anyone have any experience?

Started by clutchfft March 2, 2013
I am trying to improve the speed of an FFT algorithm for processing a sonar
bottom echo return signal.  I implemented FFT for N = 8192 nodes.  An FFT
algorithm has NLogN performance however we're investigating improving the
performance of the algorithm.  There's a paper called Fast Approximate
Fourier Transform via Wavelet Transform which proposes linear performance :
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.3984

Is anyone familiar with this concept?  I am trying to understand how it
exactly works and I'm not too familiar with wavelets.  Is it running an FFT
algorithm but using Wavelets for computation?

Any help is appreciated?  Thanks


On 3/2/13 2:56 PM, clutchfft wrote:
> > I am trying to improve the speed of an FFT algorithm for processing a sonar > bottom echo return signal. I implemented FFT for N = 8192 nodes. An FFT > algorithm has O(NLogN) performance however we're investigating improving the > performance of the algorithm. There's a paper called Fast Approximate > Fourier Transform via Wavelet Transform which proposes linear performance : > http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.3984 > > Is anyone familiar with this concept? I am trying to understand how it > exactly works and I'm not too familiar with wavelets. Is it running an FFT > algorithm but using Wavelets for computation? >
i'm not familiar with that paper, but there was, long ago (maybe around 1977) a new DFT algorithm called the Winograd fast fourier transform that was supposed to be something like O(N). dunno how it works either. i only know how the Cooley-Tukey radix-2^p alg works. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
On Sat, 02 Mar 2013 16:40:09 -0500, robert bristow-johnson
<rbj@audioimagination.com> wrote:

>On 3/2/13 2:56 PM, clutchfft wrote: >> >> I am trying to improve the speed of an FFT algorithm for processing a sonar >> bottom echo return signal. I implemented FFT for N = 8192 nodes. An FFT >> algorithm has O(NLogN) performance however we're investigating improving the >> performance of the algorithm. There's a paper called Fast Approximate >> Fourier Transform via Wavelet Transform which proposes linear performance : >> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.3984 >> >> Is anyone familiar with this concept? I am trying to understand how it >> exactly works and I'm not too familiar with wavelets. Is it running an FFT >> algorithm but using Wavelets for computation? >> > >i'm not familiar with that paper, but there was, long ago (maybe around >1977) a new DFT algorithm called the Winograd fast fourier transform >that was supposed to be something like O(N). dunno how it works either. > i only know how the Cooley-Tukey radix-2^p alg works.
The Winograd transform just rearanges the computations for the FFT algorithm, it does not change the basis functions or the overall behavior of the transform. In other words, for the most part it's just a different computation algorithm for the DFT. A Wavelet transform, however, uses different basis functions with an additional adjustment, the dilation, for the basis functions. The basis "wavelet" functions aren't fixed, either, from application to application, and the selection of the "wavelet" to use is part of the trick of properly applying the transform. So using wavelet transforms to compute the FFT is an interesting trick unrelated to the Winograd transform. Eric Jacobsen Anchor Hill Communications http://www.anchorhill.com
On Saturday, March 2, 2013 11:56:52 AM UTC-8, clutchfft wrote:
> I am trying to improve the speed of an FFT algorithm for processing a sonar > > bottom echo return signal. I implemented FFT for N = 8192 nodes. An FFT > > algorithm has NLogN performance however we're investigating improving the > > performance of the algorithm. There's a paper called Fast Approximate > > Fourier Transform via Wavelet Transform which proposes linear performance : > > http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.3984 > >
The abstract says: " the proposed algorithm computes the exact result, and its computational complexity is on the same order of the FFT, i.e. O(N log 2 N )". That's not linear performance. Dale B. Dalrymple
>On Saturday, March 2, 2013 11:56:52 AM UTC-8, clutchfft wrote: >> I am trying to improve the speed of an FFT algorithm for processing a
sonar
>> >> bottom echo return signal. I implemented FFT for N = 8192 nodes. An
FFT
>> >> algorithm has NLogN performance however we're investigating improving
the
>> >> performance of the algorithm. There's a paper called Fast Approximate >> >> Fourier Transform via Wavelet Transform which proposes linear
performance :
>> >> http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.3984 >> >> > >The abstract says: >" the proposed algorithm computes the exact result, and its computational
complexity is on the same order of the FFT, i.e. O(N log 2 N )".
> >That's not linear performance. > >Dale B. Dalrymple >
Read further (next section). You can achieve linear performance if approximations are made.
On Saturday, March 2, 2013 7:03:11 PM UTC-8, clutchfft wrote:
...
> > Read further (next section). You can achieve linear performance if > approximations are made.
That's always possible, as long as you don't want to calculate something that actually generates the DFT (as the FFT does) or something even similar. The authors hedge: "Of course, the complexity depends on the input data, the wavelets we use, the threshold value used to drop insignificant data, and the threshold value used to prune the butterfly operations. Good tradeoff need to be found. Also the implementation would be more complicated than the classical FFT" It is interesting to note that the authors give no examples of before and after transformation data or performance and have never demonstrated or even claimed the existence of any values for the "good tradeoff". They dropped the idea in 1997 without any example of existence. Good luck! Dale B. Dalrymple
>On Saturday, March 2, 2013 7:03:11 PM UTC-8, clutchfft wrote: >... >>=20 >> Read further (next section). You can achieve linear performance if >> approximations are made. > >That's always possible, as long as you don't want to calculate something
th=
>at actually generates the DFT (as the FFT does) or something even
similar.
> >The authors hedge: >"Of course, the complexity depends on the input data, the wavelets we use,
=
>the threshold value used to drop insignificant data, and the threshold
valu=
>e used to prune the butterfly operations. Good tradeoff need to be found.
A=
>lso the implementation would be more complicated than the classical FFT" > >It is interesting to note that the authors give no examples of before and
a=
>fter transformation data or performance and have never demonstrated or
even=
> claimed the existence of any values for the "good tradeoff". They dropped
=
>the idea in 1997 without any example of existence. > >Good luck! > >Dale B. Dalrymple >
I hope to at least replicate the O(nLogn) performance. I agree with your comment that the author provides no examples.