>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.
Reply by dbd●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 clutchfft●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
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.
Reply by dbd●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 Eric Jacobsen●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 robert bristow-johnson●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 clutchfft●March 2, 20132013-03-02
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