Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is there an FFT that uses a logarithmic division of frequency?

Wikipedia's Wavelet article contains this text:

The discrete wavelet transform is also less computationally complex, taking O(N) time as compared to O(N log N) for the fast Fourier transform. This computational advantage is not inherent to the transform, but reflects the choice of a logarithmic division of frequency, in contrast to the equally spaced frequency divisions of the FFT.

Does this imply that there's also an FFT-like algorithm that uses a logarithmic division of frequency instead of linear? Is it also O(N)? This would obviously be preferable for a lot of applications.

like image 907
endolith Avatar asked Jul 13 '09 16:07

endolith


People also ask

What are the two types of FFT?

These are called the radix-2 and mixed-radix cases, respectively (and other variants such as the split-radix FFT have their own names as well).

What are the types of FFT?

Popular FFT algorithms include the Cooley-Tukey algorithm, prime factor FFT algorithm, and Rader's FFT algorithm. The most commonly used FFT algorithm is the Cooley-Tukey algorithm, which reduces a large DFT into smaller DFTs to increase computation speed and reduce complexity. FFT has applications in many fields.

What is the difference between DFT and FFT?

Discrete Fourier Transform (DFT) is the discrete version of the Fourier Transform (FT) that transforms a signal (or discrete sequence) from the time domain representation to its representation in the frequency domain. Whereas, Fast Fourier Transform (FFT) is any efficient algorithm for calculating the DFT.

What is inverse FFT used for?

Inverse Fast Fourier transform (IDFT) is an algorithm to undoes the process of DFT. It is also known as backward Fourier transform. It converts a space or time signal to a signal of the frequency domain. The DFT signal is generated by the distribution of value sequences to different frequency components.


1 Answers

Yes. Yes. No.

It is called the Logarithmic Fourier Transform. It has O(n) time. However it is useful for functions which decay slowly with increasing domain/abscissa.

Referring back the wikipedia article:

The main difference is that wavelets are localized in both time and frequency whereas the standard Fourier transform is only localized in frequency.

So if you can be localized only in time (or space, pick your interpretation of the abscissa) then Wavelets (or discrete cosine transform) are a reasonable approach. But if you need to go on and on and on, then you need the fourier transform.

Read more about LFT at http://homepages.dias.ie/~ajones/publications/28.pdf

Here is the abstract:

We present an exact and analytical expression for the Fourier transform of a function that has been sampled logarithmically. The procedure is significantly more efficient computationally than the fast Fourier transformation (FFT) for transforming functions or measured responses which decay slowly with increasing abscissa value. We illustrate the proposed method with an example from electromagnetic geophysics, where the scaling is often such that our logarithmic Fourier transform (LFT) should be applied. For the example chosen, we are able to obtain results that agree with those from an FFT to within 0.5 per cent in a time that is a factor of 1.0e2 shorter. Potential applications of our LFT in geophysics include conversion of wide-band electromagnetic frequency responses to transient responses, glacial loading and unloading, aquifer recharge problems, normal mode and earth tide studies in seismology, and impulsive shock wave modelling.

like image 145
Jason Harrison Avatar answered Jan 24 '23 00:01

Jason Harrison