一维离散卷积、循环位移矩阵和 FFT

这个系统可以是汽车改造厂，输入一辆车之后，先将其拆分成 3 个大部件：如底盘框架、驱动系统、其他，这些设备需要一辆车三倍的空间来放置； 下一个时刻再将其以新的方式重新组装，但留出一个接口，第三个时刻在这个接口上加装了可以灵活拆卸的带机翼的引擎，总的来说整个飞行汽车是原来汽车的两倍大小。

于是 [3,1,2] 表示的是改造厂在收到一辆汽车后三天里这辆车所占据的空间大小；

假设工厂能同时处理任意多的汽车，卷积结果记录的就是每天该工厂中已使用的空间大小。

比如：

• 第一天来了 4 辆车，马上被拆分，一共占据 12 个单位的空间
• 第二天来了 6 辆车，当天拆解占 6*3=18 个单位，第一天那 4 辆进入重新组装，占 4*1=4 个单位。当天总占用是 18+4=22。
• 第三天来了 1 辆车，当天拆解占 1*3=3 个单位，第一天那 4 辆进入安装机翼引擎阶段，占 4*2=8 个单位。第二天那 6 辆进入重新组装，占 6*1=6 个单位。当天总占用是 3+8+6=17。
• 第四天：没有新车。第三天那 1 辆进入重新组装，占 1*1=1；第二天那 6 辆进入安装机翼引擎阶段，占 6*2=12；第一天那 4 辆已经超过三天，不再占空间。总占用 1+12=13。
• 第五天：没有新车。第三天那 1 辆进入安装机翼引擎阶段，占 1*2=2；第二天那 6 辆已经超过三天，不再占空间。总占用 2。
• 第六天及以后：0。

最终结果是数组：[12, 22, 17, 13, 2]。

这种解释下，算法描述可以是：

把 [4,6,1] 翻转成 [1,6,4] 放在 [3,1,2] 左侧，向右滑动表示时间的流逝：

当 4 滑动到和 3 重叠时，表明第一辆车进入第一个流程，点乘得到 12:

      [3, 1, 2]
[1, 6, 4]
       12

接着再滑动到 4 和 1 对齐表示第一辆车进入第二阶段，6 和 3 对齐表示第二辆车进入第一阶段，求内积：

   [3, 1, 2]
[1, 6, 4]
   18 + 4 = 12

如此继续下去，其高层思路可以表述为：

将输入向量翻转，放到卷积核左侧，开始右移，然后对重叠部分内积并 append 到结果数组中，如此循环。

这是标准的卷积算法描述，一个卷积系统会对各输入进行完全相同且独立的处理，比如不同汽车零部件不会发生“化学反应”消失或突然增大，由于输入是在不同时刻进入的，因此对系统来说，某个时刻的状态是对不同时刻输入在不同阶段处理结果的线性叠加。

这称为线性时不变系统，它就是一种任务在相继时刻开始，但每个环节都能并行处理地流水线系统。

物理上这种例子有很多，比如垃圾处理场每天有不同吨数的垃圾输入，而每天又在焚烧垃圾，因此对每个单位的垃圾，它都有一个响应曲线，如果处理厂对所有垃圾一视同仁，那么就可以近似为时不变系统，垃圾处理厂就是一个卷积机器。

同样还有像人的消化系统，你每个时刻摄入一定量的食物（可以是 0），而胃对任何输入都进行类似处理，如果身体状态平稳，那么每个时刻处理方式近似为不变的。

在物理系统中，我们有时间，有因果，但写成数学表达之后，这些东西往往没有了（除非额外加入一些解释），数学表达本身是抽象的，能够覆盖更多的场景。

现在从算法描述而非物理机制上去看待卷积。

输入的每个值按顺序乘以卷积核 [3,1,2] 然后滑动一位再叠加的思路和整数或者多项式乘法是一样的：

考虑不存在进位的 112 和 103 相乘的情况，竖式乘法写成：

  112
× 103
------
--336
-000
112
------
11536

这里就相当于输入信号是 [1,0,3], 卷积核是 [1,1,2] 时的卷积，只不过这里是从低位（最后一天）开始乘，标准卷积是从高位开始乘，因此写成：

  112
× 103
------
  112 # 第一个输入处理结果
---000 # 第二个输入处理结果
----336 # 第三个输入处理结果
---------
  11536

但二者是等价的。

而之所以乘法要从低位开始，是因为处理进位是有顺序的，比如输入是 [1,0,5]:

  112
× 105
------
--560
-000
112
------
11760

[1,1,2] 和 5 相乘不是 [5,5,10] 而是 [5,6,0], 这放在物理世界里可以强行解释成一种魔法：原本三个连续时刻是 [5,5,10], 但最后一天是 10 它超过了今天的上限，于是它能够去修改昨天的状态，把 5 变成 6, 把今天的 10 则变成 0 。

由于乘法是在处理抽象的数字系统（信息处理），而不是物理系统，因此这里并没有任何魔法。

但我们可以继续想，进位是如何产生的？

实际上，以上竖式乘法是对数用十进制表示之后执行乘法（加法的固定次数循环累加）的一种表征层算法。

312 可以写成 \( 3*10^2+1*10^1+2*10^0 \)。令 x=10，312 就是 \(3x^2+x+2\)，461 就是 \(4x^2+6x+1\)。

两者相乘：

\[ (3x^2+x+2)(4x^2+6x+1)=12x^4+22x^3+17x^2+13x+2 \]

这里系数从高到低是 12, 22, 17, 13, 2。和卷积结果数组 [12, 22, 17, 13, 2] 完全一样。

进位是把 x=10 代入之后，根据十进制表征系统，一些“时刻”的状态产生了分裂，分裂的碎片有些会“混叠”到其他状态。

因此我们可以“发明”新的乘法算法，先进行以上卷积操作得到 [12, 22, 17, 13, 2], 然后再额外进行十进制表征专有的的分裂和混叠，

所以针对卷积进行优化的算法，比如后文介绍的 FFT 可以应用在整数乘法上，发明出一种更“奇怪”的整数乘法算法：先对两个数进行某种变换，然后按位乘法，再做一次变换，最后进行数字重组。

在其他的进制表示下，比如 16 或 8 进制下进行乘法，卷积部分仍然完全一样，差别仅仅在于对 \( x^k \) 的系数变化了（基变换），以及最后用不同进制下“分裂和混叠”方式来处理最终结果。

我们熟悉的竖式乘法，则是在卷积的每一步循环中对结果状态进行“分裂和混叠”重组。

注意这里我使用了打引号的“混叠”，因为在信号处理中，混叠（aliasing）有更具体的指代，即频率上叠加，但无论是进制的位还是频率，都是一种不同层级的混合。

以上例子表明，多项式乘法本身就在进行卷积，而乘法完全是一种信息处理的规则，它比物理系统更为灵活（只是不那么直观）。

比如多项式乘法是满足交换律的，那么卷积也自然满足交换律，如果把交换律应用回到最初的飞行汽车的例子，得到的解释是：

• 对所有车都先应用第一步工序，扩展成 [12,18,3]
• 把 [4,6,1] 右移并应用第二步工序得到 [4,6,1]
• 把 [4,6,1] 再右移并应用第二步工序得到 [8,12,2]

最终叠加：

[12,18,3]
    [4,6,1]
      [8,12,2]
-------------
12, 22,17, 13, 2

我们不是用 [3,1,2] 作为工厂去处理输入的 [4,6,1] 辆车，而是把后者看作系统。

捉着数学上是把 [3,1,2] 翻转成 [2,1,3] 放在 [4,6,1] 左侧然后向右滑动

      [4, 6, 1] 
[2, 1, 3] 
       12

接着再滑动到 4 和 1 对齐表示第一辆车进入第二阶段，6 和 3 对齐表示第二辆车进入第一阶段，求内积：

   [4, 6, 1]
[2, 1, 3]
   18 + 4 = 12

另外多项式乘法中 \( x^k \) 的系数来自于卷积核和输入中不同的指数 \( x^i \) 和 \( x^j \) 满足 i+j=k 的组合场景，因此它是一种按类进行计数（counting）的活动，这也是为什么卷积会出现在概率中，两个独立的随机变量相加是一种卷积。当然也解释了为什么组合数学里会用多项式（生成函数，或者母函数）来帮助计数。

再例如 \( (3x^2+x+2)(4x^2+6x+1)=12x^4+22x^3+17x^2+13x+2 \) 中的指数 \( x^4 \) 是和 10 进制表示的位对应的，但它和汽车制造中的天数的意义对不上，为此我们可以把当前选择的一组基 \( (x^2,x,1) \) 切换成： \( (x,x^2,x^3) \) ，这样天数可以自然增长

于是： \[ 3x^2+x+2 \to 3x+x^2+2x^3 \]

\[ 4x^2+6x+1 \to 4x+6x^2+x^3 \]

两者相乘：

\[ (3x+x^2+2x^3)(4x+6x^2+x^3) \]

合并同类项：

\[ 12x^2+22x^3+17x^4+13x^5+2x^6 \]

仍然得到系数 [12,22,17,13,2]

但这里 12 对应的是 \( x^2 \) ，指数 2 并不能对应“第一天”的解释，在 4 和 (3,1,2) 相乘的时候，它不应该改变 (3,1,2) 原本的基，比如 3 对应第一天，1 对应第二天，这些应该被保留，因此 4 不应该编码成 4x, 而就是 4

因此编码应该是： \[ (3x+x^2+2x^3)(4+6x+x^2) \] 结果为： \[ 12x+22x^2+17x^3+13x^4+2x^5 \]

这个表征结果上看很符合汽车改造厂系统的物理解释的，从指数可以直接看出工厂当天空间占用，比如第 4 天有 13 个。

但这种表示在数学上并不对称，另外，在中间表示的解释上也不尽人意，比如 \( (4+6x+x^2) \) 似乎只能说是第 0 天有 4 辆车进入，第 1 天有 6 量。

更好的表示方法是统一用 \( (1,x,x^2,...) \) 这个基，即跳数下标从 0 开始，汽车厂会处理当天进入的汽车，这里“当天”用 0 表示，且第 0 天有 4 辆车进入，这样整个系统编码为：

\[ (3+x+2x^2)(4+6x+x^2) = 12+22x+17x^2+13x^3+2x^4 \]

这里核心体现了，不同的基选择，代表了不同的解释，而不同的解释会对应不同的意义，这些意义可以是现实目标需求驱动而选择的，或者是出于某种数学上的性质（比如对称性等）

回到整数十进制乘法中卷积和最后的“混叠”的现象，这种区分提供了某种对卷积进行扩展的启发，比如假设 x 是一个非常大的数，计算中几乎不会出现进位，但它仍然是有限的，由于计算机里整数表示是有限的，会“溢出”，导致 \( x^3=1 \)

那么

\[ (3+x+2x^2)(4+6x+x^2) = 12+22x+17x^2+13x^3+2x^4 \]

可以写成

\[ (3+x+2x^2)(4+6x+x^2) = 12+22x+17x^2+13+2x \]

最终结果是 \( 25+24x+17x^2 \)

注意这种混叠不像进位那样，要求把某个位的数比如 13 拆分成 10 和 3, 然后把 10 移动到高位。

它是各个位（或时间）上的整体移动，这使得它仍然能写成纯粹的卷积

按卷积标准定义来看，循环卷积相当于把 [4,6,1] 左侧添加两个 pad 值扩展成 [6,1,4,6,1] 然后翻转成 [1,6,4,1,6]:

先就把翻转后信号和卷积核右对齐然后内积：

    [3,1,2]
[1,6,4,1,6]
     12+1+12=25

然后向右滑动：

  [3,1,2]
[1,6,4,1,6]
   18+4+2=24

再向右滑动：

[3,1,2]
[1,6,4,1,6]
 3+6+8=17

最终输出 [25,24,17]

要对应到汽车改造厂的物理解释上，相当于第一辆车进入时已经有 1 辆车在第一阶段，6 辆车在第二阶段。

而一般卷积或者称为线性卷积则是在负时间轴上默认为 0:

    [3,1,2]
[1,6,4,0,0]
     12+0+0=12

另一种解释是，如果输入是 [4,6,1,4,6,1,4,6,1..] 循环的话，得到的结果会出现 25, 24, 17 的循环，也就是说只要输入是周期性的，且我们不太关注信号起始，那么这种循环卷积是自然地。

\[ C= \begin{bmatrix} 3&2&1\\ 1&3&2\\ 2&1&3 \end{bmatrix}. \]

该矩阵虽然是 3x3 的，但其中所有数值都来自于卷积核 [3,1,2] ，因此它的有效参数是 3 个。

这三个参数都分布在矩阵的各个斜线上，它实际可以写成：

\[ C=3I+1R_3+2R_3^2 \]

其中 \( R_3 \) 是循环移位矩阵，即一种排序 (Permutation) 矩阵：

\[ R_3= \begin{bmatrix} 0&0&1\\ 1&0&0\\0&1&0 \end{bmatrix} \]

如果输入是 x=[a,b,c], 那么 \( R_3x \) 会得到 [c,a,b], 即对输入循环右移一位， \(R_3^2\) 就是右移两位，而 \( R_3 ^3 \) 则回到了 I 。

\( Cx=3Ix + 1 R_3x+2R_3^2x \) 中 x=[4,6,1]， Cx 各部分解释为：

• 3Ix 表示先用 3 乘以整个输入序列得到 [12,18,3]；
• \( 1R_3x \) 表示 x 循环右移乘以 1 得到 [1,4,6];
• \( 2R_3^2x \) 表示 x 继续循环右移乘以 2 得到 [12,2,8];

最后相加得到 [25,24,17] 。

这是符合将标准卷积用交换律重新解释之后的以下流程的：

[12,18, 3] # 3 乘以 [4,6,1]
 1  [1, 4, 6] # 1 乘以 [4,6,1] 并循环右移一位
12  2  [6, 1, 4] # 2 乘以 [4,6,1] 并循环右移两位
-------------
25, 24,17, (13, 2) # 最后两项加到了前两项

由于 \( R_3 \) 只是单位矩阵的每一列循环右移一位的结果（对应是右移变换），因此它还是单位正交矩阵， \( R_3^T \) 就是它的逆。

因此 \( \|R_3x\|^2 = x^T R_3^TR_3x= x^Tx \), 也就是它不会改变输入向量的范数，因此它的特征根的模长都是 1, 比如可以是 1 ，-1 也可以是复数。

比如代数法求特征根：

\[ det(R_3-\lambda I)= \begin{bmatrix} -\lambda&0&1\\ 1&-\lambda&0\\0&1&-\lambda \end{bmatrix} \]

特征方程就是 \( \lambda^3=1 \), 因此此时特征根是 \( \lambda = (1,e^{\frac{2}{3}\pi i},e^{\frac{4}{3}\pi i}) \)

而假设 u,v 是 \( R_3 \) 的特征向量，那么 \( R_3u=\lambda_1 u \), \( R_3v=\lambda_2 v \)

\( R_3u \) 和 \( R_3v \) 进行内积得到 \( u^TR_3^TR_3v = u^Tv = \bar{\lambda_1}\lambda_2 u^Tv \)

注意对于不同的 \( \lambda_1 \) 和 \( \lambda_2 \), 它们在复平面单位圆的不同位置，共轭乘积 \( \bar{\lambda_1}\lambda_2 \) 不会等于 1 （尽管结果模长等于 1, 但以上要求数直接为 1）, 比如以上 1 乘以 \( e^{\frac{2}{3}\pi i} \neq 1 \), 所以为了 \( u^Tv = \bar{\lambda_1}\lambda_2 u^Tv \) 成立， \( u^Tv = 0 \) 必须恒成立， 也就是说 \(R_3\) 的不同特征向量也是正交的。

这使得 \( R_3\) 可以进行特殊的对角化： \( R_3 = F \Lambda F^* \), 这里 F 的列是单位向量且列之间相互正交， \( F^* \) 是它的逆，也是它的共轭转置。

而且对所以 k>=0 ， 有 \( R_3^k = F\Lambda^k F^* \) ，所以所有 \( R_3^k \) 共享特征矩阵 F, 只是特征值是 \( \Lambda^k \)

所以对于 \( C=3I+1R_3+2R_3^2 \), 它的特征向量矩阵也是 F, 特征根是 \( D = 3I+\Lambda+2\Lambda^2 \) 上对角线上的元素。

在这种情况下 Cx 写成 \( FDF^*x \), 那么计算卷积可以先对 x 应用一个 \( F^* \) 变换，转换到 F 的列作为基的空间，在 F 空间对每个元素根据 D 对角线数值缩放，再通过 F 变换返回原空间。

这看上去很是复杂，任何能对角化的矩阵 \( A=XDX^{-1} \) 对 x 进行变换似乎都能描述成这三步。

而即便 A 不能对角化甚至不是方阵，也能通过 SVD 写成 \( A=U\Sigma V^T \) ，那么对 x 变换也是经过 3 步，所以这有什么意义？

这里的关键就在于，一般的 nxn 矩阵 C 进行 Cx 变换，复杂度是 \( O(n^2) \)，因为 x 中 n 个元素要和 C 的 n 行进行点乘，而每个点乘有 n 次乘法和加法。（即便用滑动窗口方式卷积，也是 n 维卷积核与 n 维向量循环移动 n 次，每次做 O(n) 的内积，复杂度还是平方级别）

一般矩阵 A 进行对角化或者 SVD 分解的代价本身就是 \( O(n^3) \) 级别，即便能提前做分解，得到的特征向量或者奇异矩阵中数值也没有什么规律的话，拆分成两步 \( O(n^2) \) 的操作，效率反而更低了。

但我们看到，任意 nxn 循环卷积矩阵 \( C_n = c_0 I+c_1R_3+c_2 R_3^2+\dots+ c_{n-1}R_3^{n-1} \) 都共享一个特征矩阵 \( F_n \)

因此我们可以事先就准备好这个矩阵 \( F_n \) ，这样在进行变换时就不会有对角化的复杂度参与进来。（而且这个矩阵也很容易计算，见下节）

更重要的是 F 矩阵里面的元素有很强的规律性，使得 \( v=F^*x \) 和 Fv 这两个操作通过快速傅里叶变换可以优化到 \( n\log(n) \) 复杂度，所以卷积的复杂度就变成了 \( 2n\log(n) \) ，仍然是是 nlog(n) 级别。

因此我们将卷积算法从 \( O(n^2) \) 优化到了 \( O(n\log(n)) \), 另外，很多实际需求本身是要将 x 转换到 F 空间，然后对它进行特定变换后再转回来，所以无论从效率还是需求驱动上，我们都希望能对 x 在 F 空间和原空间里快速切换。。

我们知道了 nxn 的矩阵 \( R_n \) 的所有特征根都满足 \( | \lambda | = 1 \) ，因此它们是在复平面单位圆上，但如何得到它的特征向量？

回到 \( R_n \) 的意义，它是对给定向量 v 循环右移 (\(R_n v\)) 后除以一个模长为 1 的系数 \( \lambda \) 又回到了自身：v 。

这里“循环”的含义值得多说一句。右移会把最后一个元素搬到最前面，而 \(R_n^n=I\)，所以 \(R_n^{n-1}=R_n^{-1}\)。也就是说，右移 n-1 位等价于左移一位，或者说 n-1 次幂就是 -1 次幂。这个关系让“右移”和“左移”在幂次上通过取负号统一起来，也解释了为什么下面特征向量的指数可以写成负号。

什么向量对平移操作能保持某种稳定性？

首先全部值相等的向量 [c,c,…,c] 平移后还是自身，因此 [1,1,…,1] 是 \(R_n\) 的一个特征向量，对应特征值为 1。

如果特征值为 -1 呢？对应什么？

此时会想到 [1,-1,1,…,-1] 这样的交替向量，而这种向量只在 n 为偶数的时候才满足平移的某种不变性。

回到 n=3 的例子：

\[ det(R_3-\lambda I)= \begin{bmatrix} -\lambda&0&1\\ 1&-\lambda&0\\0&1&-\lambda \end{bmatrix}\]

计算 det 的时候，右下角 1 的符号取决于 n 的奇偶性：

• 如果 n 是奇数，其符号是正，但此时对角线上有奇数个 \( -\lambda \) 相乘，于是特征方程为 \( 1-\lambda^n= 0 \), 但此时不会有 -1 特征根。
• 如果 n 为偶数，右下角 1 符号是负的，但对角线上有偶数个 \( -\lambda \) 相乘，于是特征方程为 \( -1+\lambda^n= 0 \), 仍然是 \( \lambda^n = 1 \), 但此时有 -1 特征根。

注意之所以只有 n 为偶数时 -1/1 交替才成立，是因为需要满足 \( (-1)^n = 1 \) 。

而我们有 n 个这样的数满足 \( \lambda^n = 1 \), 1 是所有 n 情况下的特例，而 -1 是 n 为偶数情况下的特例。

但给定任意特征根 \( \lambda \), 都满足这个式子，因此 \( v = [1,\lambda^{-1},\lambda^{-2},\dots, \lambda^{-(n-1)}]^T \) 就是 \(R_n\) 的特征向量。

把它循环右移得到 \( R_n v = [\lambda^{-(n-1)},1,\lambda^{-1},\lambda^{-2},\dots, \lambda^{-(n-2)}]^T \)。

因为 \( \lambda^{-(n-1)}=\lambda^{-n+1}=\lambda \)，写成 \( [\lambda, 1, \lambda^{-1},\lambda^{-2},\dots,\lambda^{-(n-2)}]^T \), 它就是 \( \lambda v \)。

所以这里循环右移矩阵的优美之处在于，只要有了 \( \lambda^n = 1 \) 这个式子，那么所有特征根和所有特征向量都有了。

更具体的只要被告知循环右移矩阵的宽度 n ，然后令 \( \omega=\frac{2\pi}{n} \) ， \( W=e^{\omega i} = e^{2\pi i/n} \) ，只要有 W 就能按在复平面上向量角度从小到大生成所有特征根：

\[ W^0,W^1,W^2,\ldots,W^{n-1}. \]

而且根据复数的性质，乘以 W 自身是不断旋转，所以 W 可以称为（复平面）旋转因子。

而 \( R_n \) 的第 k 个特征向量是

\[ v_k= \begin{bmatrix} 1\\ W^{-k}\\ W^{-2k}\\ \vdots\\ W^{-(n-1)k} \end{bmatrix}. \]

然后可以排列成矩阵，比如 n=3 时为：

\[ V_3 = \begin{bmatrix} 1&1&1\\ 1&e^{-2\pi i/3}&e^{-4\pi i/3}\\ 1&e^{-4\pi i/3}&e^{-2\pi i/3} \end{bmatrix} \]

归一化之后是：

\[ F_3 = \frac{1}{\sqrt{3}} \begin{bmatrix} 1&1&1\\ 1&e^{-2\pi i/3}&e^{-4\pi i/3}\\ 1&e^{-4\pi i/3}&e^{-2\pi i/3} \end{bmatrix} \]

注意这是对称的，转置等于其自身，对所有 n 都成立，即 \( F_n = F_n^T \) ，或者一般地写成 \( F = F^T \)

共轭转置为：

\[ F_3^* = \frac{1}{\sqrt{3}} \begin{bmatrix} 1&1&1\\ 1&e^{2\pi i/3}&e^{4\pi i/3}\\ 1&e^{4\pi i/3}&e^{2\pi i/3} \end{bmatrix} \]率

由于 F 对称，它也就是 \( F_3 \) 的共轭矩阵，即 \( \bar{F_3} \)

如果从参数量来看，F 和 F* 矩阵唯一需要的就是 n ，有了 n ，就能用 n 去平分一个圆周 \( 2\pi \) 并用复指数写成旋转因子 W, 然后就知道矩阵 F 中第 j 行第 k 列值为：

\[ F_{j,k}=\frac1{\sqrt n}W^{-jk}, \qquad j,k=0,1,\ldots,n-1. \]

也知道 F 的共轭转置（也就是共轭）矩阵 F* 中第 j 行第 k 列值为：

\[ (F^*)_{j,k}=\frac1{\sqrt n}W^{jk}. \]

在理解前文之后，这部分已经是孤立的问题，即如何通过矩阵元素的规律性找到一种加速矩阵乘法的算法，这几乎是算法设计的领域，可以单独搜索 FFT 关键词了解。

以下是算法的核心思路：

我们把 \(F^*x\) 称为对向量 x 的傅里叶变换。从矩阵角度看，它就是把 x 切换到以 F 的列为基的 n 维坐标系下。

\(F^*x\) 的第 j 个分量，也就是 \(F^*\) 第 j 行与 x 的内积，是

\[ y_j=\frac1{\sqrt n}\sum_{k=0}^{n-1}x_k W^{jk}, \qquad j=0,1,\ldots,n-1. \]

这里 j 是行指标，对应输出频率；k 是列指标，对应输入位置。归一化常数 \(1/\sqrt n\) 是全局应用的，可以先放到一边，只关注不带常数的求和

\[ \hat y_j=\sum_{k=0}^{n-1}x_k W^{jk} \]

直接算每个 \( \hat y_j\) 需要 n 次乘法，j 从 0 到 n-1，一共 \(O(n^2)\)。

但由于 F 的行和列都是被一个 W 以等比数列形式参数化的，这里有很强的结构性。

我们直接以 \( F_8^* \) 为例，它的第 0 行是全 1 （任何 n 对应的第 0 行都是 1）

当然可以直接用 \( \hat y_0=x_0+x_1+x_2+x_3+x_4+x_5+x_6+x_7, \) 求和，但这样这一行就独立做完了，复杂度是 O(n).

接着看第 1 行：

\[ \hat y_1=x_0+Wx_1+W^2x_2+W^3x_3+W^4x_4+W^5x_5+W^6x_6+W^7x_7. \]

如果也这样直接算，同样是 O(n) 次乘法和加法。照这个做法，n 行都各自独立求和，总复杂度就是 \(O(n^2)\)。

这问题在于，第 1 行和第 0 行明明共享同一批输入，却各自重新乘了一遍。

比如第 1 行可以拆成偶下标和奇下标两部分：

\[ \hat y_1=(x_0+W^2x_2+W^4x_4+W^6x_6)+W(x_1+W^2x_3+W^4x_5+W^6x_7). \]

括号里的两个求和，其实就是 \( F_4 \) 和 (x0,x2,x4,x6) 和 (x1,x3,x5,x7) 两个数据相乘（离散傅里叶变换）的结果

如果这两个子问题的结果已经被算过，第 1 行只需要一次乘法和一次加法就能拼出来。

而 \( F_8 \) 的第 5 行每个元素是第 1 行的 4 次方（n/2 次方）为：

\[ 1, W^5, W^{10},\ W^{15},\ W^{20},\ W^{25}, W^{30}, W^{35} \]

因为 \(W^8=1\)，这些幂次可以约化。\(W^5\) 保持不变，\(W^{10}=W^2\)，\(W^{15}=W^7\)，\(W^{20}=W^4\)，\(W^{25}=W^1 =W^9\)，

\(W^{30}=W^6 \)，\(W^{35}=W^3 = W^{11}\)。所以第 5 行可以写成：

\[ 1,\ W^5,\ W^2,\ W^7,\ W^4,\ W^1,\ W^6,\ W^3. \]

或者

\[ 1,\ W^5,\ W^2,\ W^7,\ W^4,\ W^9,\ W^6,\ W^{11}. \]

按奇偶下标拆开，偶下标位置（0,2,4,6）是

\[ 1,\ W^2,\ W^4,\ W^6, \]

奇下标位置（1,3,5,7）是

\[ W^5,\ W^7,\ W^9,\ W^{11}. \]

把奇部分提出一个 \(W^5\)： \( W^5\cdot(1,\ W^2,\ W^4,\ W^6). \)

所以第 5 行的偶部分和第 1 行的偶部分完全一样，都是 \(1,W^2,W^4,W^6\)；奇部分则等于同一个偶部分再乘以 \(W^5\)。但 \(W^5=W^4\cdot W=-W\)，而 \(W^4=-1\)，所以 \(W^5=-W\)。

对 x 应用并区分奇偶之后，

\[ \hat y_5=(x_0+W^2x_2+W^4x_4+W^6x_6)-W(x_1+W^2x_3+W^4x_5+W^6x_7). \]

括号里的两项，和第 1 行括号里的两项完全相同。也就是说，第 1 行和第 5 行共享同一对 \( F_4 \) 对 x 偶数和奇数作用的第一行结果 \( E_1 \) 和 \( O_1 \)，只是一个取加、一个取减：

\[ \hat y_1=E_1+W^1O_1, \]

\[ \hat y_5=E_1-W^1O_1. \]

类似地，第 0 行和第 4 行配对，共享 \( E_0 \) 和 \( O_0 \)；第 2 行和第 6 行配对，共享 \(E_2\) 和 \(O_2\)；第 3 行和第 7 行配对，共享 \(E_3\) 和 \(O_3\)。

这样一次 \( F_8x \) 就等于两次 \( F_4 x_{e} \) 和 \( F_4 x_{o} \) ，然后对结果进行合并，合并时每行有 2 次加法，8 行就是 O(2*8)

对于任意 n 都可以这样应用，这里利用的是第 j 行和第 j+n/2 行会出现的指数循环特性。

于是复杂度 \( T(n)=2T(\frac{n}{2})+n \), 而 \( 2T(\frac{n}{2}) = 2 (2T(\frac{n}{4})+\frac{n}{2}) \) = \( 4T(\frac{n}{4})+n \) 这个拆分只能进行 \( \log(n) \) 层，于是就是是 log(n) 个 n 相加，复杂度为 nlog(n)

对于 \( C=3I+1R_3+2R_3^2 \)，其特征根是 \( D=3I+\Lambda+2\Lambda^2 \) 对角线上的元素。

将卷积核 [3,1,2] 记为 c，且 \(R_3\) 的第 k 个特征根记为 \( \lambda_k \)。

那么 C 的第 k 个特征根是两个向量的内积：\( \)，而第二个向量正是 \(R_3\) 的第 k 个特征向量的共轭转置。

于是 C 的所有特征根可以通过 \( F_3^*c \) 得到，也就是说通过对 c 进行傅里叶变换得到。

此时完整的关于卷积的另一种图景出现了。 用卷积核 [3,1,2] 和 x=[4,6,1] 进行循环卷积，等价于：

• 对卷积核 [3,1,2] 做正向 FFT，即 \( F^*c \)，得到所有特征根组成的向量 d；
• 对信号 x 做正向 FFT，即 \( y=F^*x \)；
• d 和 y 按位相乘得到 dy；
• 对 dy 做逆向 FFT 得到 \( Fdy \)，最终就是循环卷积结果。

这称为卷积定理，即两个向量的循环卷积等价于对两个向量分别做 FFT 后按位相乘然后进行逆向 FFT:

\[ Cx=F\big((F^*c)\cdot(F^*x)\big) \]

对于非循环卷积，也可以用前文提到的技巧扩充卷积核与信号，变成循环卷积然后应用该定理。

由于 FFT 使得正反向变换都是 nlog(n), 于是整个流程总体复杂度也是 nlog(n)

这种高效来自四个条件同时成立：

• 第一，所有循环卷积矩阵共享同一个特征矩阵 F，这来自 \(R_3\) 的移位结构，去掉循环性，每个矩阵就要单独做特征分解，代价是 \( O(n^3) \)。
• 第二，F 是酉矩阵，所以 \(F^*\) 就是逆，变换和逆变换可以对称地进行，去掉正交性，就要额外求逆。
• 第三，F 的元素有 \( W^{-jk} \) 的规律性，使得 \(F^*x\) 和 \(Fy\) 可以用 FFT 在 \(O(n\log n)\) 内完成，去掉这个规律性，比如特征向量没有解析形式，就退回 \(O(n^2)\)。
• 第四，特征值向量 \( d=F^*c \) 本身也可以通过一次 FFT 得到，因为 c 就是核系数按多项式顺序排列的，去掉这个对应关系，D 的计算就要单独付出 \(O(n^2)\) 甚至更高的代价。

四个条件里，循环性给出共享特征矩阵，酉性给出对称逆变换，指数规律给出 FFT，多项式对应给出 D 的快速计算。缺任何一个，整体复杂度都会从 \(O(n\log n)\) 退回至少 \(O(n^2)\)。

现在回到卷积矩阵之间的组合问题。如果有两个循环卷积矩阵 \(C_1\) 和 \(C_2\)，先进行 \(C_1\) 再进行 \(C_2\)，也就是对信号做两次卷积，那么这等价于做一次卷积，这从多项式视角看最清楚：

假设 \(C_1\) 对应核 [3,1,2]，\(C_2\) 对应核 [4,6,1]。把它们分别写成多项式：

\[ H_1(x)=3+x+2x^2, \]

\[ H_2(x)=4+6x+x^2. \]

两次卷积复合，就对应两个多项式相乘：

\[ H_1(x)H_2(x)=(3+x+2x^2)(4+6x+x^2). \]

展开得到

\[ 12+22x+17x^2+13x^3+2x^4. \]

在循环卷积里，因为 \(P^3=I\)，所以 \(x^3=1\)、\(x^4=x\)。把高次项折回来：

\[ 12+22x+17x^2+13+2x=25+24x+17x^2. \]

于是复合后的等效核就是 [25,24,17]。换句话说，两个卷积核先做一次卷积，得到的新核再作用在信号上，和先后做两次卷积完全一样。

或者说，两个卷积核的合并本身就是一次卷积，以上例子和用 [3,1,2] 作为核， [4,6,1] 作为信号进行卷积是完全相同的代数推导。

可选补充

前文以右移矩阵 \(R_n\) 为主线，把循环卷积矩阵的多项式拆分、特征分解、FFT 和卷积定理都梳理了一遍。左移矩阵 \(P_n\) 在数学上完全等价，只是符号和顺序上多了一层翻转。

这里只把不同点集中列出来，作为对照。

左移矩阵的定义是

\[ P= \begin{bmatrix} 0&1&0\\ 0&0&1\\ 1&0&0 \end{bmatrix}, \qquad P[a,b,c]^T=[b,c,a]^T. \]

它把向量循环左移一位，满足 \(P^n=I\)。对应的循环卷积矩阵仍然可以写成多项式，但系数顺序与卷积核不再一致：

\[ C=3I+2P+P^2. \]

卷积核是 [3,1,2]，但多项式系数是 (3,2,1)，也就是核的循环左移一次再翻转。换句话说，左移视角下，核需要先翻转再移位，才能和 \(P\) 的幂次对齐。右移视角下，\(C=3I+1R+2R^2\)，系数顺序和核完全一致，这是右移更直观的地方。

特征值方面，左移和右移完全一样，都是 n 次单位根：

\[ \lambda_k=e^{i2\pi k/n},\qquad k=0,1,\ldots,n-1. \]

不同在于特征向量。右移的特征向量是负指数：

\[ v_k= \begin{bmatrix} 1\\ W^{-k}\\ W^{-2k}\\ \vdots\\ W^{-(n-1)k} \end{bmatrix}, \]

左移的特征向量是正指数：

\[ v_k= \begin{bmatrix} 1\\ W^{k}\\ W^{2k}\\ \vdots\\ W^{(n-1)k} \end{bmatrix}. \]

因此左移的特征矩阵是右移特征矩阵的共轭转置。如果记右移特征矩阵为 \(F\)，那么左移特征矩阵就是 \(F^*\)；反过来，左移的共轭转置就是 \(F\)。正向 FFT 在右移视角下是 \(F^*x\)，在左移视角下就变成 \(Fx\)。两者只差一个共轭。

卷积定理在左移视角下写成

\[ Cx=F^*\big((Fc)\cdot(Fx)\big), \]

其中 \(c\) 是核 [3,1,2] 循环左移一次再翻转得到的 (3,2,1)。但这一步翻转和左移实际等价于直接对原始核 [3,1,2] 做正向 FFT，因为

\[ 3+1\lambda+2\lambda^2 =3+2\lambda^{-1}+1\lambda^{-2}, \]

而 \(\lambda^{-1}=\bar\lambda\)。所以最终仍然可以统一成：对原始核做正向 FFT，对信号做正向 FFT，逐点相乘，再做逆向 FFT。左移视角下需要多解释一步翻转，右移视角下则直接成立。

FFT 的递归结构在两种视角下形式相同，只是旋转因子的正负号互换。右移用 \(W^{jk}\) 做正向变换，左移用 \(W^{-jk}\)。蝴蝶操作中，右移的配对是 \(j\) 与 \(j+n/2\)，左移的配对完全一样，只是 \(W^j\) 换成 \(W^{-j}\)。复杂度都是 \(O(n\log n)\)。

总结成一句话：左移和右移在特征值、FFT 递归、卷积定理的整体结构上完全一致，唯一区别是特征向量和变换方向取共轭。右移的优点是多项式系数与卷积核顺序一致，不需要翻转；左移则多一步翻转，但特征向量是正指数形式，写起来更接近传统的傅里叶级数展开。两者只是同一件事的两种符号约定。