是否有使用频率对数除法的 FFT？
维基百科的 小波文章包含以下文本：
离散小波变换的计算复杂度也较低，与 快速傅里叶变换。 这种计算优势并不是变换所固有的，而是反映了对数频率划分的选择，与 FFT 的等间隔频率划分不同。
这是否意味着还有一种类似 FFT 的算法，使用频率的对数除法而不是线性？ 也是O(N)吗？ 对于许多应用程序来说，这显然是更可取的。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
是的。 是的。 不，
它被称为对数傅立叶变换。 它有 O(n) 时间。 然而，它对于随着域/横坐标的增加而缓慢衰减的函数很有用。
回顾一下维基百科的文章：
因此，如果您只能在时间（或空间，选择您对横坐标的解释）上进行本地化，那么小波（或离散余弦变换）是一种合理的方法。 但如果你需要继续下去，那么你就需要傅里叶变换。
了解有关 LFT 的更多信息，请访问 http://homepages.dias.ie/~ajones/publications /28.pdf
这是摘要：
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:
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:
编辑：读完这篇文章后，我认为这个算法对于这个问题并不是真正有用，无论如何我都会为其他读者提供描述。
还有
菲隆算法是一种基于菲隆求积的方法，可以在Numerical Recipes这篇[博士论文][1]中找到。时间尺度是对数间隔的，结果频率尺度也是如此。
该算法用于在观察到的时间间隔内衰减到 0 的数据/函数（这可能不是你的情况），一个典型的简单例子是指数衰减。
如果您的数据由点 (x_0,y_0),(x_1,y_1)...(x_i,y_i) 表示，并且您想要计算频谱 A(f)，其中 f 是频率，可以说 f_min=1/x_max至 f_max=1/x_min
对数间隔。
然后计算每个频率 f 的实部：
A(f) = i=0...i-1 的总和 { (y_i+1 - y_i)/(x_i+1 - x_i) * [ cos(2* pi*f * t_i+1) - cos(2*pi*f*t_i) ]/((2*pi*f)^2) }
虚部为：
A(f) = y_0/(2*pi* f) + i=0...i-1 的总和 { (y_i+1 - y_i)/(x_i+1 - x_i) * [ sin(2*pi*f * t_i+1) - sin(2*pi *f*t_i) ]/((2*pi*f)^2) }
[1] Blochowicz, Thomas：纯和二元分子玻璃成型体中的宽带介电光谱。拜罗伊特大学，2003 年，第3.2.3章
EDIT: After reading up on this I think this algorithm is not really useful for this question, I will give a description anyway for other readers.
There is also
the Filon's algorithma method based on Filon's qudrature which can be found inNumerical Recipesthis [PhD thesis][1].The timescale is log spaced as is the resulting frequeny scale.
This algorithm is used for data/functions which decayed to 0 in the observed time interval (which is probably not your case), a typical simple example would be an exponential decay.
If your data is noted by points (x_0,y_0),(x_1,y_1)...(x_i,y_i) and you want to calculate the spectrum A(f) where f is the frequency from lets say f_min=1/x_max to f_max=1/x_min
log spaced.
The real part for each frequency f is then calculated by:
A(f) = sum from i=0...i-1 { (y_i+1 - y_i)/(x_i+1 - x_i) * [ cos(2*pi*f * t_i+1) - cos(2*pi*f*t_i) ]/((2*pi*f)^2) }
The imaginary part is:
A(f) = y_0/(2*pi*f) + sum from i=0...i-1 { (y_i+1 - y_i)/(x_i+1 - x_i) * [ sin(2*pi*f * t_i+1) - sin(2*pi*f*t_i) ]/((2*pi*f)^2) }
[1] Blochowicz, Thomas: Broadband Dielectric Spectroscopy in Neat and Binary Molecular Glass Formers. University of Bayreuth, 2003, Chapter 3.2.3
为了做你想做的事，你需要测量不同的时间窗口，这意味着较低的频率更新最少（与 2 的幂成反比）。
在这里查看 FPPO：
https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf
这意味着更高频率会更频繁地更新，但你总是平均（移动平均线很好），而且还可以让它移动得更快。 当然，如果计划使用逆 FFT，您就不需要这些。 此外，为了在较低频率下获得更好的精度（更小的带宽），意味着这些需要更慢地更新，例如 16k Windows (1/3 m/s)。
是的，低频信号自然传播得很慢，因此当然需要很多时间来检测它们。 这不是数学可以解决的问题。 这是一种自然的交换，你无法获得高精度、较低的频率和快速的响应。
我认为我提供的链接将澄清您的一些选择......不幸的是，在您提出问题 7 年后。
To do what you want, you need to measure different time Windows, which means lower frequencies get update least often (inversely proportional to powers of 2).
Check FPPO here:
https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf
This means that higher frequencies will update more often, but you always average (moving average is good), but can also let it move faster. Of course, if plan on using the inverse FFT, you don't want any of this. Also, to have better accuracy (smaller bandwidth) at lower frequencies, means these need to update much more slowly, like 16k Windows (1/3 m/s).
Yeah, a low frequency signal naturally travels slowly, and thus of course, you need a lot of time to detect them. This is not a problem that math can fix. It's a natural trade of, and you can't have high accuracy a lower frequency and fast response.
I think the link I provide will clarify some of your options...7 years after you asked the question, unfortunately.