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

# Fast Fourier Transform with Wavelets - Anyone have any experience?

Started by ●March 2, 2013

Reply by ●March 2, 20132013-03-02

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."

Reply by ●March 2, 20132013-03-02

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

Reply by ●March 2, 20132013-03-02

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

Reply by ●March 2, 20132013-03-02

>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 asonar>> >> bottom echo return signal. I implemented FFT for N = 8192 nodes. AnFFT>> >> algorithm has NLogN performance however we're investigating improvingthe>> >> performance of the algorithm. There's a paper called Fast Approximate >> >> Fourier Transform via Wavelet Transform which proposes linearperformance :>> >> 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 computationalcomplexity 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.

Reply by ●March 3, 20132013-03-03

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

Reply by ●March 3, 20132013-03-03

>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 somethingth=>at actually generates the DFT (as the FFT does) or something evensimilar.> >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 thresholdvalu=>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 anda=>fter transformation data or performance and have never demonstrated oreven=> 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.