如何使用快速傅里叶变换执行矩阵卷积

Question

我需要将许多大型 3D 数组(形状为 500x500x500(添加到一起，并希望通过在傅里叶空间中使用乘法来加快该过程。问题是，与简单地添加矩阵相比，在傅里叶空间中乘法时，我没有得到相同的答案。

为了测试它，我写了一个最小的例子试图让它工作，但答案不是我所期望的。要么我的数学知识是错误的，要么是我没有正确使用函数。

下面是显示我正在尝试执行的操作的最简单代码：

import numpy as np
c = np.asarray(((1,2),(2,3)))
d = np.asarray(((1,4),(1,5)))
print("Transform")
Nc = np.fft.rfft2(c)
Nd = np.fft.rfft2(d)
print("Inverse")
Nnc = np.fft.irfft2(Nc)
Nnd = np.fft.irfft2(Nd)
print("Somme")
S = np.dot(Nc, Nd)
print(np.fft.irfft2(S))

当我打印 S 时，我得到的结果：

[[6, 28],[10,46]]

但是根据我对傅里叶空间

的理解，乘法意味着傅里叶空间之外的加法，所以我应该得到S = c + d？

我使用 FFT 函数做错了什么，还是我假设 S 应该等于 c 加 d？

Answer 1

这里有一点误解：

傅里叶空间中的乘法对应于空间域中的卷积，而不是加法。

没有办法以这种方式加速加法。

Answer 2

如果你想通过傅里叶域计算c+d，你必须将两个光谱相加，而不是将它们相乘：

np.fft.irfft2(Nc+Nd) == c+d  # (up to numerical precision)

当然，这比简单地在空间域中添加矩阵要慢得多。

正如@Florian所说，卷积可以通过在空间域中乘法来加速。