傅里叶变换与卷积的关系,CNN工作原理

介绍

为了理解卷积，我们需要证明一下傅里叶变换，首先看一下傅里叶变换的两个公式，频域和时域：

$$F(\omega)=\int^{+ \infty}_{-\infty}f(t)e^{-i\omega t} dt$$ $$f(t)=\frac{1}{2\pi}\int^{+\infty}_{-\infty}F(\omega)e^{i\omega t}d\omega$$

先把泛函的基本思想复习一下：泛函分析研究的是算子在空间里的性质，那里可以把函数当成向量来做分解和投影；讨论傅里叶变换时，这些函数默认处在完备的内积空间里。把工具准备好，就可以试着推一遍傅里叶变换了。

证明

先定义内积空间D，它诱导的范数满足齐次性、非负性和三角不等式。为方便起见把D叫作频域空间，把原函数f(x)变换到D里。

$$d_i∈D,\vec f = f(x),<f,d>$$

把d定义为D的一组正交基，f(x)看作空间里的向量。f在基d上的投影分量为u，由投影关系可得：

$$|\vec u_i|=|\vec f|\cos<\vec f,\vec d_i>$$

把向量除以它的长度变成单位向量，同时得到内积的表达式，方便接下来的推导。

$$\vec u_i =|\vec f||\vec d_i|\cos<\vec f,\vec d_i>\frac{\vec d_i}{|\vec d_i|}$$ $$\vec u_i = <\vec f,\vec d_i>\hat {\vec d_i}$$

我们最后得到了内积关系关于d的单位向量。我们进行展开内积：

$$<\vec f,\vec d_i> =\int_{-\infty}^{+\infty}\vec f(x)\; \vec d_i \; dx$$

代入后可以得到：

$$\vec u_i=\int_{-\infty}^{+\infty}\vec f(x)\; \vec d_i \; dx·\vec {\hat d_i}$$

我们希望各个基向量彼此正交，而欧拉公式给出的复指数$e^{i\omega t}$正好满足这一点，取$d=e^{i\omega t}$，于是得到最后结果：

$$u_i=\int^{+ \infty}_{-\infty}f(t)e^{-i\omega t} dt = F(w)$$

这样时域转频域就证明了。我们利用展开内积的关系可以得到：

$$\vec f = \sum F(w)\vec {\hat d_i}=\sum F(w)\frac{\vec d_i}{|\vec d_i|}$$ $$\sum F(w)\frac{\vec d_i}{|\vec d_i|}=\sum F(w)\frac{\vec d_i}{<\vec d_i,\vec d_i>^{\frac{1}{2}}}$$ $$<\vec d_i,\vec d_i> = \int_{-\frac{l}{2}}^{\frac{l}{2}}e^{iwt}e^{-iwt}dt=l=\frac{2\pi}{dw}$$ $$\sum F(w)\frac{\vec d_i}{<\vec d_i,\vec d_i>^{\frac{1}{2}}}=\frac{1}{2\pi}\sum F(\omega)e^{i\omega t}d\omega$$

我们把无穷级数用积分的形式表达出来就有：

$$f(t)=\frac{1}{2\pi}\int^{+\infty}_{-\infty}F(\omega)e^{i\omega t}d\omega$$

这样我们就证明了傅里叶的两个变换。

卷积与傅里叶变换的关系

卷积定理说的其实就一件事：

$$F(f*g)=F(f)·F(g)$$

两个函数卷积之后再变换，等于各自变换之后相乘。时域里要滑窗逐点算的卷积，到频域就变成一次乘法，这也是实际计算卷积时常用FFT加速的原因；CNN里的卷积层做的就是这种滑窗运算（严格说没翻转核，是互相关），同样能从频域来分析。

总结

傅里叶变换的正、反两个公式到这里就推完了。它和卷积的关系也就一句话：卷积的傅里叶变换，等于两个函数各自傅里叶变换的乘积——卷积在频域里就是乘法，这也是频域分析能用在CNN上的原因。