译者 | 陈彩娴
校对 | 青 暮
卷积的看法无处不在。它事实 有什么特殊 之处呢？在本文中，作者从第一性原理中推导出卷积，并批注 它自然地来自平移对称性。
在阅读卷积的起源与历史的历程中，读者有时机相识 到卷积看法和卷积运算符的生长历史。卷积积分最早是泛起在法国著名数学家达朗贝尔在1754年揭晓 的著作《宇宙系统 的几个要点研究》（Recherches sur différents points importants du système du monde）里所先容 的泰勒定理推导中。
人们常误以为卷积积分最早是泛起在法国数学家拉普拉斯1773年的论文《行星轨道的平均倾角、地球形状与函数》（Mémoire sur l’inclinaison moyenne des orbites des comètes, sur la figure de la terre et sur les fonctions中，但现实 上，拉普拉斯是在1778年撰写概率论时才真正使用卷积。
在早期，卷积被实验命名为法语“résultante”、意大利语“composizione”、德语“faltung”等，均指向“折叠”、“卷曲”之类的寄义。英语用来指代“卷积”的单词“convolution”取自拉丁文“con”（together，“一起”）和volvere（roll up，“卷起”），使德语“faltung”的直译，最早泛起在Aurel Friedrich Wintner揭晓 于1934年的论文中，厥后又被Gustav Doetsch（现代拉普拉斯变换理论的奠基人）等着名 数学家在权威作品中引用，以是 “convolution”的职位也由此得以牢靠 。沃尔泰拉（Volterra）最早在1910年使用星星运算符（*），但形状稍有差异。卷积的现代体现形式“f∗g”最早是由Gustav Doetsch在1923年提出的。
日前，帝国理工教授Michael Bronstein在《Deriving convolution from first principles》中从第一性原理即平移稳固 性或对称性（translational invariance or symmetry）推导出卷积，而不是事先假设卷积的存在。这个脑洞看似平平无奇，但效果却惊掉下巴！
1 可交流性
基础的信号处置赏罚 课程中教过一个公式，这个公式对含有两个n维向量x和w的离散卷积（discrete convolution，此处特指“循环卷积”）作了如下界说：
在这里，为了利便 明确 与阅读，作者假设所有索引的取值规模为0到n-1，并对n取模。将上面的公式写成矩阵向量乘法，会获得一个循环矩阵，如下图所示：
循环矩阵具有多对角线结构（multi-diagonal structure），每个对角线上的元素有相同的值。它可以通过堆叠向量w的平移向量（对n取模）来形成。因此，这里使用符号C(w)来指代由向量w形成的循环矩阵。由于 所有卷积x∗w都可以等同于循环矩阵C(w)x的乘积，以是 x∗w和C(w)x这两项表达在本文中会交替使用。
我们知道在线性代数中，矩阵乘法是非交流的，好比说，一样平常 情形 下AB≠BA。可是 ，循环矩阵是一个很是特殊的破例 ：循环矩阵可交流。换句话说，C(w)C(u)=C(u)C(w)。这条规则适用于所有循环矩阵或向量u和w。同样地，我们可以说，卷积运算是遵照 交流律的，即x∗w=w∗x。
若w=[0,1,0…,0]，则C(w)是一个能将向量往右移动一个位置的特殊循环矩阵。该矩阵称为（右）平移运算符（作者将“运算符”与“矩阵”交流使用），用S体现。右平移运算符的转置为左移位运算符。很显然，向左移动，然后向右移动并没有任何作用，反之亦然。这批注 ，S是正交矩阵（orthogonal matrix）：
循环矩阵的特点在于可交流性。Bamieh2018年的论文《Discovering transforms: a tutorial on circulant matrices, circular convolution, and the discrete Fourier transform》中的引理3.1指出：当且仅当矩阵是平移可交流的时间 ，这个矩阵才气称为“循环矩阵”。
这个发现有以下几个意义：
首先，这批注 循环矩阵具有一个很是主要 的属性，即平移等变性（translation equivariance）：卷积的平移可交流性批注 ，先平移向量然后举行 卷积，或先卷积再平移，效果 是一样的。
注重 ：有些同砚 容易混淆“invariance”与“equivariance”的看法，前者指的是“unchanged”，稳固 ，后者指的是“changing in the same way”，通过同样的方式举行 改变。许多信号处置赏罚 的教科书也会将作者此处谈到的“shift equivariance”（平移等变性）说成“shift invariance”（平移稳固 性）。若是 f(Sx)=Sf(x)，则函数为平移等变性；若是 f(Sx)=f(x)，则函数为平移稳固 性。
“平移稳固 性”是物理学中的一个基础看法，经常以“平移对称性”的说法泛起，指的是物理规则自力 于空间内的地理位置。在经典力学的变分公式中，凭证 诺特定理（Noether's theorem），动量守恒的基本规则是由平移稳固 性导出。
其次，卷积可以界说为“平移-等变线性运算”：为了知足 平移可交流，矩阵必须具有循环结构。这正是我们一最先 所希望的，就是将卷积从平移对称性的第一性原理中推导出来。
作者没有不加分辨地接受信号处置赏罚 课程课本 书给出的卷积公式、证实 它的平移等变性（shift equivariance）性子 ，而是从平移等变性出发，再得出卷积公式是唯一知足 的线性操作。
图注：平移等变性的展示，即平移和模糊操作是可交流的。
2 卷积和傅里叶变换
信号处置赏罚 课程中还讲到另一个主要 征象 ，即卷积和傅里叶变换（Fourier transform）之间的联系。
由于我们此处探讨的是有限维向量（finite-dimensional vectors），以是 此处“傅里叶变换”指的是“离散傅里叶变换”（Discrete Fourier Transform，DFT）。
傅里叶变换能将卷积运算对角化，从而将在频域内执行两个向量的卷积作为它们傅里叶变换的逐元素乘积。没有人能诠释 傅里叶变换中正弦和余弦的泉源 以及它们的特殊之处。
为了举行 更深入的研究，我们要回首线性代数中的一个事实：交流矩阵可以团结 对角化。
换句话说，知足 AB=BA的两个矩阵将具备相同的特征向量（但可能特征值差异）。
更确切地说，团结 对角化意味着两个交流矩阵具有相同的本征空间，由于 在一样平常 情形 下，本征值具有非通俗 的多重性（non-trivial multiplicity）。由于在这里作者讨论的所有特征值都很简朴，因此只围绕一个配合的特征基举行 讨论。
由于所有循环矩阵都是可交流的，因此我们可以选择其中一个矩阵，并盘算它的特征向量（上述定理确保了这些向量也是所有循环矩阵的特征向量）。
为利便 起见，我们选择平移运算符S。由于S是正交矩阵，以是 我们也期望其特征向量是正交的。论文《DISCOVERING TRANSFORMS: A TUTORIAL ON CIRCULANT MATRICES, CIRCULAR CONVOLUTION, AND THE DISCRETE FOURIER TRANSFORM》中的4.1节中通过简朴的盘算得出以下结论：“傅里叶变换能将平移运算符对角化”。
可是 ，由于S是非对称的，因此它没有实数特征值（对称的实数矩阵具有实数特征值）。S的特征值恰恰 是单元矩阵的复数根。
接下来是这篇文章的第二个“震惊”发现：这正是正弦与余弦的泉源 ！它们是平移运算符的特征向量，作者将它们称为矩阵的列Φ。需要注重 的是，特征向量是复数，因此在转置Φ时需要举行 复数共轭。与Φ*相乘（从左边最先 ）被称为“傅里叶变换”，而与Φ相乘被称为“傅里叶逆变换”。
由于所有循环矩阵都可以团结 对角化，因此它们也可以通过傅里叶变换举行 对角化。循环矩阵仅在特征向量上有所区别。最后一个常被忽视的点是：C(w)的特征值是向量w的傅里叶变换。
此处矩阵C通过傅里叶变换“对角化”，指的是矩阵Φ*CΦ是对角的。由于傅里叶变换是一个正交矩阵（Φ*Φ= I），因此在几何上，它起着相当于n维旋转的坐标系转变 的作用。在此坐标系中，C的作用变为按元素的乘积。
上述的结论可以总结为一个卷积定理：卷积x∗w可以看作在原始坐标系上将循环矩阵C(w)作用于x（有时称为 “空间域”卷积）；或者在傅里叶的基础上（“频谱域”），先盘算Φ*x的傅里叶变换，再乘以w的傅里叶变换，然后盘算傅里叶逆变换。
由于 Φ具有特殊的冗余结构，以是 可以用快速傅里叶变换（FFT）算法以?(n log n)重大 度将Φ*x和Φx的效果 盘算出来。
为什么卷积的这个界说云云 主要 、并需要通过这种方式举行 解说呢？作者引用了爱尔维修（Helvétius）的一句话：“The knowledge of certain principles easily compensates the lack of knowledge of certain facts.”（“有些原理所包罗的知识能轻盈 填补 某些事实的知识空缺”。）在卷积的案例中，它的第一性原理（平移对称性）推导历程能很轻松地推广到其他领域。
原文链接：
1、https://towardsdatascience.com/deriving-convolution-from-first-principles-4ff124888028
2、https://arxiv.org/pdf/1805.05533