Wikipedia's Wavelet article contains this text:
*的Wavelet文章包含以下文字:
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.
离散小波变换的计算复杂度也较低,与快速傅里叶变换的O(N log N)相比,花费O(N)时间。这种计算优势不是变换所固有的,而是反映了频率的对数分割的选择,与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.
这是否意味着还有类似FFT的算法使用频率的对数除法而不是线性?是O(N)吗?对于许多应用来说,这显然是优选的。
3 个解决方案
#1
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.
它被称为对数傅里叶变换。它有O(n)时间。然而,它对于随着域/横坐标增加而缓慢衰减的函数是有用的。
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
有关LFT的更多信息,请访问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."
“我们提出了一个精确的解析表达式,用于对数采样的傅立叶变换。对于变换函数或测量的响应,该过程在计算上明显更有效,其中随着横坐标值的增加,衰减缓慢衰减。我们用电磁地球物理学的例子来说明所提出的方法,其中缩放通常应该应用我们的对数傅里叶变换(LFT)。对于所选择的例子,我们能够获得与FFT中的结果一致的结果。 LFT在地球物理学中的潜在应用包括将宽带电磁频率响应转换为瞬态响应,冰川加载和卸载,含水层补给问题,正常模式和地球潮汐研究在地震学和冲动冲击波建模中。“
#2
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 algorithm
a method based on Filon's qudrature which can be found in
Numerical Recipes
this [PhD thesis][1]. The timescale is log spaced as is the resulting frequeny scale.
Filon算法也是一种基于Filon数学的方法,可以在[数学论文] [数学论文] [1]中找到。时间刻度是对数间隔,因为产生的频率刻度。
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.
该算法用于在观察到的时间间隔内衰减为0的数据/函数(可能不是您的情况),典型的简单示例是指数衰减。
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:
如果您的数据以点(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) = 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) }
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)}
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) }
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: Broadband Dielectric Spectroscopy in Neat and Binary Molecular Glass Formers. University of Bayreuth, 2003, Chapter 3.2.3
[1] Blochowicz,Thomas:纯净和二元分子玻璃形成器中的宽带介电谱。拜罗伊特大学,2003年,第3.2.3章
#3
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).
要做你想做的事,你需要测量不同时间的Windows,这意味着较低的频率最少经常更新(与2的幂成反比)。
Check FPPO here: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf
在此处查看FPPO: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).
这意味着更高的频率会更频繁地更新,但你总是平均(移动平均值很好),但也可以让它移动得更快。当然,如果计划使用逆FFT,你不需要任何这个。此外,为了在较低频率下具有更好的准确度(更小的带宽),意味着需要更快地更新,例如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.
我认为我提供的链接将澄清您的一些选择...不幸的是,在您提出问题7年之后。
#1
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.
它被称为对数傅里叶变换。它有O(n)时间。然而,它对于随着域/横坐标增加而缓慢衰减的函数是有用的。
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
有关LFT的更多信息,请访问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."
“我们提出了一个精确的解析表达式,用于对数采样的傅立叶变换。对于变换函数或测量的响应,该过程在计算上明显更有效,其中随着横坐标值的增加,衰减缓慢衰减。我们用电磁地球物理学的例子来说明所提出的方法,其中缩放通常应该应用我们的对数傅里叶变换(LFT)。对于所选择的例子,我们能够获得与FFT中的结果一致的结果。 LFT在地球物理学中的潜在应用包括将宽带电磁频率响应转换为瞬态响应,冰川加载和卸载,含水层补给问题,正常模式和地球潮汐研究在地震学和冲动冲击波建模中。“
#2
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 algorithm
a method based on Filon's qudrature which can be found in
Numerical Recipes
this [PhD thesis][1]. The timescale is log spaced as is the resulting frequeny scale.
Filon算法也是一种基于Filon数学的方法,可以在[数学论文] [数学论文] [1]中找到。时间刻度是对数间隔,因为产生的频率刻度。
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.
该算法用于在观察到的时间间隔内衰减为0的数据/函数(可能不是您的情况),典型的简单示例是指数衰减。
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:
如果您的数据以点(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) = 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) }
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)}
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) }
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: Broadband Dielectric Spectroscopy in Neat and Binary Molecular Glass Formers. University of Bayreuth, 2003, Chapter 3.2.3
[1] Blochowicz,Thomas:纯净和二元分子玻璃形成器中的宽带介电谱。拜罗伊特大学,2003年,第3.2.3章
#3
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).
要做你想做的事,你需要测量不同时间的Windows,这意味着较低的频率最少经常更新(与2的幂成反比)。
Check FPPO here: https://www.rationalacoustics.com/files/FFT_Fundamentals.pdf
在此处查看FPPO: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).
这意味着更高的频率会更频繁地更新,但你总是平均(移动平均值很好),但也可以让它移动得更快。当然,如果计划使用逆FFT,你不需要任何这个。此外,为了在较低频率下具有更好的准确度(更小的带宽),意味着需要更快地更新,例如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.
我认为我提供的链接将澄清您的一些选择...不幸的是,在您提出问题7年之后。