矩阵卷积的快速算法

悲剧的面试

上周二去面试一家公司，好几个问题上都卡住了。

原先刷的都是算法、数据结构上的问题。简历上写的课程上的知识几乎全忘了（本身也没兴趣），结果面试官按着简历上的课程问，悲剧了。

题目

一个M×N的矩阵A，以及一个K×K的矩阵B，对两个矩阵做卷积运算，复杂度为多少？有没有快速运算？

思路

如果考虑暴力法，那复杂度显然是$O(MNK^2)$。

快速算法当时一直在往动态规划上套，死活想不出来，%>_<%

回来仔细想了想，这不是能用变换域做嘛%>_<%

这个和编程倒是没什么关系，是用在信号处理和图像处理上的。

卷积运算在频域会变成乘法运算，复杂度大降。

数学原理

假设矩阵a为M×N的矩阵，b为K×K的矩阵，那么它们的卷积为

$$s(m, n)=a*b=\sum_{i=0}^{K-1}\sum_{j=0}^{K-1}a(m-i,n-j)b(i, j)$$

很容易看出来，复杂度是$O(MNK^2)$。

如果对$s$做二维DFT(M+k-1与N+k-1点），有

$$S(u,v)=\sum_{m=0}^{M+K-2}\sum_{n=0}^{N+K-2}s(m,n)e^{-j\frac{2\pi mu}{M+K-1}}e^{\frac{2\pi nv}{N+K-1}} \\ =\sum_{m=0}^{M+K-2}\sum_{n=0}^{N+K-2}s(m,n)e^{-j\frac{2\pi (m-i)u}{M+K-1}}e^{-j\frac{2\pi (n-j)v}{N+K-1}}e^{-j\frac{2\pi iu}{M+K-1}}e^{-j\frac{2\pi ju}{N+K-1}} \\ =\sum_{m=0}^{M+K-2}\sum_{n=0}^{N+K-2}\sum_{i=0}^{K-1}\sum_{j=0}^{K-1}a(m-i,n-j)b(i, j)e^{-j\frac{2\pi (m-i)u}{M+K-1}}e^{-j\frac{2\pi (n-j)v}{N+K-1}}e^{-j\frac{2\pi iu}{M+K-1}}e^{-j\frac{2\pi ju}{N+K-1}} \\ =\sum_{i=0}^{K-1}\sum_{j=0}^{K-1}b(i, j)\sum_{m=0}^{M+K-2}\sum_{n=0}^{N+K-2}a(m-i,n-j)e^{-j\frac{2\pi (m-i)u}{M+K-1}}e^{-j\frac{2\pi (n-j)v}{N+K-1}}e^{-j\frac{2\pi iu}{M+K-1}}e^{-j\frac{2\pi ju}{N+K-1}} \\ =\sum_{i=0}^{K-1}\sum_{j=0}^{K-1}b(i, j)e^{-j\frac{2\pi iu}{M+K-1}}e^{-j\frac{2\pi ju}{N+K-1}} A(u,v) \\ =B(u,v)A(u,v)$$

当然如果使用普通的DFT，变换与反变换过程的复杂度是$O(M^2N^2)$，相乘的复杂度是$O(MN)$，总体的复杂度是$O(M^2N^2)$

比普通的卷积效果还差。

这时候就要祭出大杀器FFT了，变换域反变换过程的复杂度降低到了$O(MNlogMlogN)$，总体的复杂度为$O(MNlogMlogN)$。

那么如果$K^2>logMlogN$，这样的计算就能够带来性能上的提高。