为什么FFT加速了与卷积有关的计算？

Question

我看到很多文献中都说通过使用fft可以实现更快的卷积运算。我知道需要从结果中获取fft和ifft，但我真的不明白为什么使用fft可以使卷积更快？

- Nicole

---

如果卷积核很大，FFT 比直接卷积更快。这个结论来自程序员交流网站上的一个问题。链接为 http://programmers.stackexchange.com/q/171757/4280。 - DarenW

Answer 1

对于足够大的滤波器，FFT加速卷积，因为每个输出样本的卷积需要N次乘法（和N-1次加法），相反，对于一个包含N个样本的块而言，需要(2)N²个操作。

考虑到为FFT处理而添加零时必须将块大小加倍，因此每个块需要(2)*(2N)*log(2N)个操作以执行FFT，2N个操作以进行乘法，并且再次需要4N*log(2N)个操作以执行逆FFT，当8Nlog2N ≤ 2N²时就达到了盈亏平衡点。

其基本原因如下：

1）离散时间域信号可以表示为频率的和。
2）时间域中的卷积（O(N²)）等于频率域中的乘法（O(N)）。
3）这种变换是可逆的。
4）存在一种方法可以在不到N²个操作的情况下将信号从时域转换到频域（这就是“快速傅里叶变换”的第一个F）。

直接FT是O(N²)，其中每个频域元素F(i)=Σf(i)*exp(i*pi/N)。

然而，FFT基于发现exp(i*pi/N)具有某些对称性，允许计算在奇/偶向量中分割。偶向量可以在O(N)的代价下计算，而奇向量需要一个半尺寸的完整FT。由于这可以重复直到N=2，因此总体复杂度将是（与）Nlog(N)成比例。

- Aki Suihkonen

---

一个警告：FFT中的主要操作也是复杂的（这意味着复数乘法需要4次实数乘法和2次加法，或者使用Karatsuba分解需要3次乘法和5次加法）。无论如何，KNlog(kN)最终都会比N^2小。 - Aki Suihkonen

那么，为什么FFT空间中的计算成本比时间小，我的意思是，它使用更小的数据块还是其他原因？您所说的过滤器是什么意思？ - Nicole

FFT 必须使用更大的块。 - Aki Suihkonen

这个解释不完整、不正确且误导性。请参考http://programmers.stackexchange.com/questions/171757/computational-complexity-of-correlation-in-time-vs-multiplication-in-frequency-s获取更好的解释。 - thang

也要指出的是，该链接中答案的作者错误地低估了二维FFT的运行时间。虽然二维傅里叶变换(FT)具有可分离性的优点，但存在一些开销。WxW图像的二维FT不同于W*W向量的一维FT，但它们非常接近。 - thang