audio - 是否有使用频率对数除法的 FFT？

Question

维基百科的Wavelet article包含以下文字:

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.

这是否意味着还有一种类似 FFT 的算法，使用频率的对数除法而不是线性？也是O(N)吗？对于许多应用程序来说，这显然是更可取的。

Answer 1

是的。是的。没有。

它被称为对数傅里叶变换。它有 O(n) 时间。然而，它对于随着域/横坐标的增加而缓慢衰减的函数很有用。

引用维基百科文章:

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

因此，如果您只能在时间(或空间)上进行本地化，请选择您对横坐标的解释)，那么小波(或离散余弦变换)是一种合理的方法。但如果你需要继续下去，那么你就需要傅里叶变换。

了解有关 LFT 的更多信息，请访问 http://homepages.dias.ie/~ajones/publications/28.pdf

这是摘要:

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.