【学习笔记】向量卷积、矩阵卷积与快速傅里叶变换

一、卷积

• CNN中的卷积层，

  • 然后得到$c\times (n-k+1)\times(n-k+1)$的feature map,这里默认stride=1,padding=0

  • 针对每一个卷积核，卷积具体可以写成

    $$U_{j,k}=\sum_{t=0,l=0}^{k-1,k-1}X_{j+t,k+l}W_{t,l}$$

• 向量卷积

  • 给定两个向量$a=(a_0,a_1,…,a_{n-1})^T,b=(b_0,b_1,…,b_{n-1})^T$,向量卷积结果$c=(c_0,c_1,…,c_{2n-2})^T$为

    $$c_k=\sum_{i+j=k}a_ib_j$$

  • 定理：向量$a,b$做卷积运算等价于对分别以$a,b$为系数的多项式做多项式乘法得到的多项式的系数

    • $a=(1,1,1),b=(0,2,5)$,卷积结果$c=(2,7,7,5)$
    • 构造多项式$A(x)=x^2+x+1,B(x)=2x+5$
      • $C(x)=A(x)B(x)=(x^2+x+1)(2x+5)=2x^3+7x^2+7x+5$

• 矩阵卷积(2-D)转化为向量卷积(1-D)

  • 把$X,W$拉成一维向量$\vec{X},\vec{W}$，首先对这两个向量做向量卷积

    $$\vec{U}_j=\sum_{i=0}^j\vec{X}_{j-i}\vec{W}_i$$

  • 根据向量中元素和原本矩阵中对应的关系，可以得到

    $$U_{j,k}=\sum_{t=0,l=0}^{w-1,w-1}X_{j+t,k+l}W_{t,l}=\sum_{t=0,l=0}^{w-1,w-1}\vec{X}_{(n-1-j-t)n+(n-1-k-l)}\vec{W}_{tn+l}\\=\sum_{t=0,l=0}^{n-1,n-1}\vec{X}_{(n-1-j-t)n+(n-1-k-l)}\vec{W}_{tn+l}\\=\sum_{i=0}^{n^2-1-jn-k}\vec{X}_{n^2-1-jn-k-i}\vec{W}_i=\vec{U}_{n^2-1-jn-k}$$

二、快速傅里叶变换

• 假设我们有多项式$A(x)=x^2+3x+2,B(x)=2x^2+1$，想要求$C(x)=A(x)B(x)$

• 如何在计算机中存储多项式？

  • 存储系数，一个最高次数为$d$的多项式需要$d+1$个系数

    • 通过常规的数学算法$(x^2+3x+2)(2x^2+1)=x^2·2x+3x·2x^2+2·2x^2+x^2+3x+2$的方法对系数进行乘法和加法操作，复杂度为$O(d^2)$

  • 任一最高次数为$d$的多项式都可以由$d+1$不同的点唯一确定，（两点确定一条直线）

    • 也就是说$\{(x_0,P(x_0)),(x_1,P(x_1)),…,(x_d,P(x_d))\}$可以用来表示这个多项式

    • $P(x)=p_0+p_1x+…+p_dx^d$，代入上述$d+1$个点可以得到

      $$\begin{pmatrix} P(x_0) \\ P(x_1) \\ \vdots \\ P(x_d) \end{pmatrix}=\begin{pmatrix} 1 & x_0 & x_0^2 & ... & x_0^d \\ 1 & x_1 & x_1^2 & ... & x_1^d \\ 1 & x_2 & x_2^2 & ... & x_2^d \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_d & x_d^2 & \cdots & x_d^d \end{pmatrix}\begin{pmatrix} p_0 \\ p_1 \\ \vdots \\ p_d \end{pmatrix}$$
      • 注意：这里$x_0,x_1,…x_d$两两不同，因此中间的矩阵是一个范德蒙德矩阵，可以证明行列式一定不为0，因此由克莱姆法则可以知道上述方程一定有唯一解，因此可以确定一个唯一的多项式

    • 我们可以用$d+1$个点来表示一个多项式，那么表示$C(x)$我们需要5个点，对于$A(x)$我们取出5个点,$B(x)$我们也取出5个点，我们将这10个点组成5对，分别两两相乘又得到五个点，这五个点就是$C(x)$上的五个点，可以用来表示$C(x)$，复杂度为$O(d)$

    • 那么就有两个问题

      • 我们如何从$P(x)=p_0+p_1x+p_2x^2+…+p_dx^d$中取出$d+1$个点
      • 我们如何从这$d+1$个点还原回一个多项式

• 如何从$P(x)=p_0+p_1x+p_2x^2+…+p_dx^d$中取出$d+1$个点

  • 选取$d+1$个点$x_0$计算$P(x_0)$,那么每个点的计算复杂度为$O(d)$，总的计算复杂度就是$O(d^2)$

  • 有没有可能我们计算完一个点的值后，另一个横坐标不同的点的纵坐标也就计算出来了？

    • 比如$P(x)=x^2$,那么我们计算完$P(x_0),P(-x_0)$也就知道了
    • 奇偶性

  • $以P(x)=3x^5+2x^4+x^3+7x^2+5x+1$为例

    • 根据奇偶性将$P(x)$分组为$P(x)=(2x^4+7x^2+1)+(3x^5+x^3+5x)$

    • 更进一步将奇函数部分的x提出，$P(x)=(2x^4+7x^2+1)+x(3x^4+x^2+5)$

    • 我们将这样的形式统一写成

      $$P(x)=P_e(x^2)+xP_o(x^2)$$

    • 那么计算$P(x)$的过程就转化为了计算$P_e(x^2)$和$P_o(x^2)$的过程，同时我们可以把$x^2$看成一个整体，然后计算$P_e(x^2)$和$P_o(x^2)$的次数就变成了$\frac{d}{2}$

      • 但是由于$P_e(x^2)、P_o(x^2)$的整体定义域变为了正实数，我们在实数域内没法通过同样的找到$x_0,-x_0$的方式减少计算的点的个数
        • 扩展到复数域
        • 这样我们还是可以通过成对取点的方式递归计算$P_e(x^2)$和$P_0(x^2)$
        • 复杂度$O(nlogn)$

    • 更进一步，我们要如何计算出这几个复数呢

      • 以$P(x)=x^3+x^2-x-1$为例，我们需要取出4个点$(x_1,-x_1,x_2,-x_2)$

        • 其中$x_1^2=-x_2^2$,那么我们就需要从$x_1^4$中求得它的两个平方根
        • 最简单的方法就是令$x_1^4=1$，那么最后的4个点就是1的4次方根(4th roots of unity)

      • 取出$d+1$个点，方便起见，我们直接取出$n=2^k$个点，其中$2^{k-1}<d+1\le2^k$

      • 那么我们可以取出$1的n次方根(1, \omega^1,\omega^2,…,\omega^{n-1})$,(n-th roots of unity)

        $$\begin{pmatrix} P(x_0) \\ P(x_1) \\ \vdots \\ P(x_d) \end{pmatrix}=\begin{pmatrix} 1 & x_0 & x_0^2 & ... & x_0^d \\ 1 & x_1 & x_1^2 & ... & x_1^d \\ 1 & x_2 & x_2^2 & ... & x_2^d \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_d & x_d^2 & \cdots & x_d^d \end{pmatrix}\begin{pmatrix} p_0 \\ p_1 \\ \vdots \\ p_d \end{pmatrix},x_k=\omega^k,\omega=e^{\frac{2\pi i}{d+1}},$$

• 如何从这$d+1$个点还原回一个多项式

  • 我们将一个多项式表示成$d+1$个点（插值，参考拉格朗日插值）

  • 如何快速的转化回去？

    • IFFT，下面最终矩阵的形式和FFT非常相似，我们还是可以用类似的递归的方法来计算 $$\begin{pmatrix} P(x_0) \\ P(x_1) \\ \vdots \\ P(x_d) \end{pmatrix}=\begin{pmatrix} 1 & x_0 & x_0^2 & ... & x_0^d \\ 1 & x_1 & x_1^2 & ... & x_1^d \\ 1 & x_2 & x_2^2 & ... & x_2^d \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_d & x_d^2 & \cdots & x_d^d \end{pmatrix}\begin{pmatrix} p_0 \\ p_1 \\ \vdots \\ p_d \end{pmatrix},x_k=\omega^k,\omega=e^{\frac{2\pi i}{d+1}},$$

$$\begin{pmatrix} p_0 \\ p_1 \\ \vdots \\ p_d \end{pmatrix}=\begin{pmatrix} 1 & x_0 & x_0^2 & ... & x_0^d \\ 1 & x_1 & x_1^2 & ... & x_1^d \\ 1 & x_2 & x_2^2 & ... & x_2^d \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_d & x_d^2 & \cdots & x_d^d \end{pmatrix}^{-1}\begin{pmatrix} P(x_0) \\ P(x_1) \\ \vdots \\ P(x_d) \end{pmatrix} \\ =\frac{1}{n}\begin{pmatrix} 1 & x_0^{-1} & x_0^{-2} & ... & x_0^{-d} \\ 1 & x_1^{-1} & x_1^{-2} & ... & x_1^{-d} \\ 1 & x_2^{-1} & x_2^{-2} & ... & x_2^{-d} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_d^{-1} & x_d^{-2} & \cdots & x_d^{-d} \end{pmatrix}\begin{pmatrix} P(x_0) \\ P(x_1) \\ \vdots \\ P(x_d) \end{pmatrix}$$

• 用FFT和IFFT计算卷积

  • 前面已经得到对于两个矩阵$X,W$的卷积，我们可以用$\vec{X},\vec{W}$的向量卷积来得到

    $$\vec{U}=\vec{X}*\vec{W}$$

  • 而向量卷积等价于用由$\vec{X},\vec{W}$作为系数的两个多项式的乘法

    • 用FFT对$\vec{X},\vec{W}$分别进行插值表示,取同样的点个数($X$比$W$的规模大，按照$X$的取)，这些点的横坐标是一样的，得到了$\vec{X},\vec{W}$在同样的几个点下的插值表示，分别表示为一个向量

    • 对得到的这两个向量进行Hadamard乘积计算，即对应位置相乘，即可得到多项式乘法的结果的插值结果，然后再对插值结果进行IFFT计算即可得到卷积，即

      $$\vec{U}=\vec{X}*\vec{W}=IFFT(FFT(\vec{X})∘FFT(\vec{W}))$$