与实空间卷积相比，FFT卷积的缺点是什么？

Question

因此，我知道FFT卷积比实空间卷积具有更低的计算复杂度。但是FFT卷积的缺点是什么呢？

内核大小是否总是必须与映像大小相匹配，或者是否有函数来处理这个问题，例如，在pythons和scipy包中？那么抗混叠效果呢？

Answer 1

卷积定理卷积基于f和g两种函数，如果Fd()和Fi()表示正、逆傅里叶变换，以及*和.卷积和乘法，则：

f*g = Fi(Fd(d).Fd(g))

要将其应用于信号f和内核g，需要处理一些事情：

• 要使乘法步骤成为可能，f和g必须具有相同的大小，因此您需要对内核进行零填充(或者输入，如果内核比内核长)。
• 当做DFT时，这是FFT所做的，得到的函数频域表示是周期性的。这意味着，默认情况下，您的内核在进行卷积时环绕边缘。如果你想要这个，那一切都很好。但如果不是，您必须添加一个额外的零填充内核的大小，以避免它。
• 大多数(全部？)FFT包仅能很好地工作(从性能上看)，其大小没有任何大的素因子。将信号和内核大小舍入到下一个2的幂是一种常见的做法，可能会导致(非常)显着的加速。

如果您的信号和内核大小为f_l和g_l，则在时域中进行简单的卷积需要g_l * (f_l - g_l + 1)乘法和(g_l - 1) * (f_l - g_l + 1)加法。

对于快速傅立叶变换方法，你必须至少做3个大小为f_l + g_l的FFT，以及f_l + g_l乘法。

对于大尺寸的f和g，其n*log(n)复杂度明显优于前者。对于小内核来说，直接的方法可能更快。

scipy.signal有convolve和fftconvolve方法供您使用。fftconvolve为您透明地处理上面描述的所有填充。

Answer 2

而快速卷积比直接形式卷积具有更好的“大O”复杂度，但也有一些缺点或注意事项。我为文章做了一些思考，我写了一段时间前的文章。

1. 更好的“大O”复杂性并不总是更好。对于小于一定尺寸的滤波器，直接形式卷积比使用FFT更快。确切的大小取决于所使用的平台和实现。交叉点通常在10-40系数范围内.
2. 延迟。快速卷积本质上是一种分块算法。对一些实时应用程序来说，在转换它们之前一次排队数百个或数千个样本可能是不可接受的。
3. 实现的复杂性。直接形式在内存、代码空间和作者/维护者的理论背景方面更简单。
4. 在定点DSP平台上(而不是通用CPU)：定点FFT有限字长的考虑使得大型定点FFT几乎毫无用处。在尺寸谱的另一端，这些芯片都有专门的MAC结构，它们都是为执行直接表单FIR计算而设计的，增加了te (N^2)直接形式比O(NlogN)快的范围。这些因素往往创造一个有限的“甜蜜点”，其中定点FFT是有用的快速卷积。