傅里叶变换和卷积题目的论文

傅里叶是一位法国数学家和物理学家的名字，英语原名是Jean Baptiste Joseph Fourier(1768-1830), Fourier对热传递很感兴趣，于1807年在法国科学学会上发表了一篇论文，运用正弦曲线来描述温度分布，论文里有个在当时具有争议性的决断：任何连续周期信号可以由一组适当的正弦曲线组合而成。当时审查这个论文的人，其中有两位是历史上著名的数学家拉格朗日(Joseph Louis Lagrange, 1736-1813)和拉普拉斯(Pierre Simon de Laplace, 1749-1827)，当拉普拉斯和其它审查者投票通过并要发表这个论文时，拉格朗日坚决反对，在他此后生命的六年中，拉格朗日坚持认为傅里叶的方法无法表示带有棱角的信号，如在方波中出现非连续变化斜率。法国科学学会屈服于拉格朗日的威望，拒绝了傅里叶的工作，幸运的是，傅里叶还有其它事情可忙，他参加了政治运动，随拿破仑远征埃及，法国大革命后因会被推上断头台而一直在逃避。直到拉格朗日死后15年这个论文才被发表出来。拉格朗日是对的：正弦曲线无法组合成一个带有棱角的信号。但是，我们可以用正弦曲线来非常逼近地表示它，逼近到两种表示方法不存在能量差别，基于此，傅里叶是对的。用正弦曲线来代替原来的曲线而不用方波或三角波来表示的原因在于，分解信号的方法是无穷的，但分解信号的目的是为了更加简单地处理原来的信号。用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。一个正弦曲线信号输入后，输出的仍是正弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的。且只有正弦曲线才拥有这样的性质，正因如此我们才不用方波或三角波来表示。 为什么偏偏选择三角函数而不用其他函数进行分解？我们从物理系统的特征信号角度来解释。我们知道：大自然中很多现象可以抽象成一个线性时不变系统来研究，无论你用微分方程还是传递函数或者状态空间描述。线性时不变系统可以这样理解：输入输出信号满足线性关系，而且系统参数不随时间变换。对于大自然界的很多系统，一个正弦曲线信号输入后，输出的仍是正弦曲线，只有幅度和相位可能发生变化，但是频率和波的形状仍是一样的。也就是说正弦信号是系统的特征向量！当然，指数信号也是系统的特征向量，表示能量的衰减或积聚。自然界的衰减或者扩散现象大多是指数形式的，或者既有波动又有指数衰减（复指数 形式），因此具有特征的基函数就由三角函数变成复指数函数。但是，如果输入是方波、三角波或者其他什么波形，那输出就不一定是什么样子了。所以，除了指数信号和正弦信号以外的其他波形都不是线性系统的特征信号。用正弦曲线来代替原来的曲线而不用方波或三角波或者其他什么函数来表示的原因在于：正弦信号恰好是很多线性时不变系统的特征向量。于是就有了傅里叶变换。对于更一般的线性时不变系统，复指数信号(表示耗散或衰减)是系统的“特征向量”。于是就有了拉普拉斯变换。z变换也是同样的道理，这时是离散系统的“特征向量”。这里没有区分特征函数和特征向量的概念，主要想表达二者的思想是相同的，只不过一个是有限维向量，一个是无限维函数。傅里叶级数和傅里叶变换其实就是我们之前讨论的特征值与特征向量的问题。分解信号的方法是无穷的，但分解信号的目的是为了更加简单地处理原来的信号。这样，用正余弦来表示原信号会更加简单，因为正余弦拥有原信号所不具有的性质：正弦曲线保真度。且只有正弦曲线才拥有这样的性质。这也解释了为什么我们一碰到信号就想方设法的把它表示成正弦量或者复指数量的形式；为什么方波或者三角波如此“简单”，我们非要展开的如此“麻烦”；为什么对于一个没有什么规律的“非周期”信号，我们都绞尽脑汁的用正弦量展开。就因为正弦量(或复指数)是特征向量。 什么是时域？从我们出生，我们看到的世界都以时间贯穿，股票的走势、人的身高、汽车的轨迹都会随着时间发生改变。这种以时间作为参照来观察动态世界的方法我们称其为时域分析。而我们也想当然的认为，世间万物都在随着时间不停的改变，并且永远不会静止下来。什么是频域？频域(frequency domain)是描述信号在频率方面特性时用到的一种坐标系。用线性代数的语言就是装着正弦函数的空间。频域最重要的性质是：它不是真实的，而是一个数学构造。频域是一个遵循特定规则的数学范畴。正弦波是频域中唯一存在的波形，这是频域中最重要的规则，即正弦波是对频域的描述，因为时域中的任何波形都可用正弦波合成。对于一个信号来说，信号强度随时间的变化规律就是时域特性，信号是由哪些单一频率的信号合成的就是频域特性。 时域分析与频域分析是对信号的两个观察面。时域分析是以时间轴为坐标表示动态信号的关系；频域分析是把信号变为以频率轴为坐标表示出来。一般来说，时域的表示较为形象与直观，频域分析则更为简练，剖析问题更为深刻和方便。目前，信号分析的趋势是从时域向频域发展。然而，它们是互相联系，缺一不可，相辅相成的。贯穿时域与频域的方法之一，就是传说中的傅里叶分析。傅里叶分析可分为傅里叶级数（Fourier Serie）和傅里叶变换(Fourier Transformation)。 根据原信号的不同类型，我们可以把傅里叶变换分为四种类别：1非周期性连续信号傅里叶变换（Fourier Transform）2周期性连续信号傅里叶级数(Fourier Series)3非周期性离散信号离散时域傅里叶变换（Discrete Time Fourier Transform）4周期性离散信号离散傅里叶变换(Discrete Fourier Transform)下图是四种原信号图例：这四种傅里叶变换都是针对正无穷大和负无穷大的信号，即信号的的长度是无穷大的，我们知道这对于计算机处理来说是不可能的，那么有没有针对长度有限的傅里叶变换呢？没有。因为正余弦波被定义成从负无穷大到正无穷大，我们无法把一个长度无限的信号组合成长度有限的信号。面对这种困难，方法是把长度有限的信号表示成长度无限的信号，可以把信号无限地从左右进行延伸，延伸的部分用零来表示，这样，这个信号就可以被看成是非周期性离解信号，我们就可以用到离散时域傅里叶变换的方法。还有，也可以把信号用复制的方法进行延伸，这样信号就变成了周期性离散信号，这时我们就可以用离散傅里叶变换方法进行变换。这里我们要学的是离散信号，对于连续信号我们不作讨论，因为计算机只能处理离散的数值信号，我们的最终目的是运用计算机来处理信号的。但是对于非周期性的信号，我们需要用无穷多不同频率的正弦曲线来表示，这对于计算机来说是不可能实现的。所以对于离散信号的变换只有离散傅里叶变换（DFT）才能被适用，对于计算机来说只有离散的和有限长度的数据才能被处理，对于其它的变换类型只有在数学演算中才能用到，在计算机面前我们只能用DFT方法，后面我们要理解的也正是DFT方法。这里要理解的是我们使用周期性的信号目的是为了能够用数学方法来解决问题，至于考虑周期性信号是从哪里得到或怎样得到是无意义的。每种傅里叶变换都分成实数和复数两种方法，对于实数方法是最好理解的，但是复数方法就相对复杂许多了，需要懂得有关复数的理论知识，不过，如果理解了实数离散傅里叶变换(real DFT)，再去理解复数傅里叶就更容易了，所以我们先把复数的傅里叶放到一边去，先来理解实数傅里叶变换，在后面我们会先讲讲关于复数的基本理论，然后在理解了实数傅里叶变换的基础上再来理解复数傅里叶变换。如 上图所示，实信号四种变换在时域和频域的表现形式。还有，这里我们所要说的变换(transform)虽然是数学意义上的变换，但跟函数变换是不同的，函数变换是符合一一映射准则的，对于离散数字信号处理（DSP），有许多的变换：傅里叶变换、拉普拉斯变换、Z变换、希尔伯特变换、离散余弦变换等，这些都扩展了函数变换的定义，允许输入和输出有多种的值，简单地说变换就是把一堆的数据变成另一堆的数据的方法。 傅里叶变换是数字信号处理领域一种很重要的算法。要知道傅里叶变换算法的意义，首先要了解傅里叶原理的意义。傅里叶原理表明：任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅里叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。和傅里叶变换算法对应的是反傅里叶变换算法。该反变换从本质上说也是一种累加处理，这样就可以将单独改变的正弦波信号转换成一个信号。因此，可以说，傅里叶变换将原来难以处理的时域信号转换成了易于分析的频域信号（信号的频谱），可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅里叶反变换将这些频域信号转换成时域信号。从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。在数学领域，尽管最初傅里叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。"任意"的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类：1. 傅里叶变换是线性算子,若赋予适当的范数,它还是酉算子;2. 傅里叶变换的逆变换容易求出,而且形式与正变换非常类似;3. 正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段;4. 离散形式的傅里叶的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取;5. 著名的卷积定理指出:傅里叶变换可以化复变换可以利用数字计算机快速的算出(其算法称为快速傅里叶变换算法(FFT))。正是由于上述的良好性质,傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。图像傅里叶变换图像的频率是表征图像中灰度变化剧烈程度的指标，是灰度在平面空间上的梯度。如：大面积的沙漠在图像中是一片灰度变化缓慢的区域，对应的频率值很低；而对于地表属性变换剧烈的边缘区域在图像中是一片灰度变化剧烈的区域，对应的频率值较高。傅里叶变换在实际中有非常明显的物理意义，设f是一个能量有限的模拟信号，则其傅里叶变换就表示f的谱。从纯粹的数学意义上看，傅里叶变换是将一个函数转换为一系列周期函数来处理的。从物理效果看，傅里叶变换是将图像从空间域转换到频率域，其逆变换是将图像从频率域转换到空间域。换句话说，傅里叶变换的物理意义是将图像的灰度分布函数变换为图像的频率分布函数，傅里叶逆变换是将图像的频率分布函数变换为灰度分布函数。傅里叶变换以前，图像（未压缩的位图）是由对在连续空间（现实空间）上的采样得到一系列点的集合，我们习惯用一个二维矩阵表示空间上各点，则图像可由z=f(x,y)来表示。由于空间是三维的，图像是二维的，因此空间中物体在另一个维度上的关系就由梯度来表示，这样我们可以通过观察图像得知物体在三维空间中的对应关系。为什么要提梯度？因为实际上对图像进行二维傅里叶变换得到频谱图，就是图像梯度的分布图，当然频谱图上的各点与图像上各点并不存在一一对应的关系，即使在不移频的情况下也是没有。傅里叶频谱图上我们看到的明暗不一的亮点，实际上图像上某一点与邻域点差异的强弱，即梯度的大小，也即该点的频率的大小（可以这么理解，图像中的低频部分指低梯度的点，高频部分相反）。一般来讲，梯度大则该点的亮度强，否则该点亮度弱。这样通过观察傅里叶变换后的频谱图，也叫功率图，我们首先就可以看出，图像的能量分布，如果频谱图中暗的点数更多，那么实际图像是比较柔和的（因为各点与邻域差异都不大，梯度相对较小），反之，如果频谱图中亮的点数多，那么实际图像一定是尖锐的，边界分明且边界两边像素差异较大的。对频谱移频到原点以后，可以看出图像的频率分布是以原点为圆心，对称分布的。将频谱移频到圆心除了可以清晰地看出图像频率分布以外，还有一个好处，它可以分离出有周期性规律的干扰信号，比如正弦干扰，一副带有正弦干扰，移频到原点的频谱图上可以看出除了中心以外还存在以某一点为中心，对称分布的亮点集合，这个集合就是干扰噪音产生的，这时可以很直观的通过在该位置放置带阻滤波器消除干扰。另外说明以下几点：1、图像经过二维傅里叶变换后，其变换系数矩阵表明：若变换矩阵Fn原点设在中心，其频谱能量集中分布在变换系数短阵的中心附近（图中阴影区）。若所用的二维傅里叶变换矩阵Fn的原点设在左上角，那么图像信号能量将集中在系数矩阵的四个角上。这是由二维傅里叶变换本身性质决定的。同时也表明一股图像能量集中低频区域。2 、变换之后的图像在原点平移之前四角是低频，最亮，平移之后中间部分是低频，最亮，亮度大说明低频的能量大（幅角比较大）。 将其发展延伸，构造出了其他形式的积分变换: 从数学的角度理解积分变换就是通过积分运算，把一个函数变成另一个函数。也可以理解成是算内积，然后就变成一个函数向另一个函数的投影：K（s，t）积分变换的核(Kernel)。当选取不同的积分域和变换核时，就得到不同名称的积分变换。学术一点的说法是：向核空间投影，将原问题转化到核空间。所谓核空间，就是这个空间里面装的是核函数。下表列出常见的变换及其核函数： 当然，选取什么样的核主要看你面对的问题有什么特征。不同问题的特征不同，就会对应特定的核函数。把核函数作为基函数。将现在的坐标投影到核空间里面去，问题就会得到简化。之所以叫核，是因为这是最核心的地方。为什么其他变换你都没怎么听说过而只熟悉傅里叶变换和拉普拉斯变换呢？因为复指数信号才是描述这个世界的特征函数！

Graph Convolutional Networks涉及到两个很重要的概念：graph和Convolution。传统的卷积方式在欧式数据空间中大展神威，但是在非欧式数据空间中却哑火，很重要的一个原因就是传统的卷积方式在非欧式的数据空间上无法保持“平移不变性”。为了能够将卷积推广到Graph等非欧式数据结构的拓扑图上，GCN横空出世。在深入理解GCN： 的来龙去脉之前，我觉着我们有必要提前对以下概念有点印象：

论文链接 Semi-supervised Classification with Graph Convolutional Networks

1.拉普拉斯矩阵及其变体 给定一个节点数为 的简单图 ， 是 的度矩阵， 是 的邻接矩阵，则 的拉普拉斯矩阵可以表示为 . 中的各个元素表示如下：

1.传统的傅里叶变换 当变换对象为离散变量时，求积分相当于求内积，即 这里的 就是传说中似乎有点神秘的拉普拉斯算子的特征函数（拉普拉斯算子是欧式空间中的二阶微分算子，卸了妆之后的样子是 ）。 为何这样说呢？是因为从广义的特征方程定义看 , 本身是一种变换， 是特征向量或者特征函数， 是特征值。我们对基函数 求二阶导， . 可以看出 是变换 的特征函数。

在Graph中，拉普拉斯矩阵 可以谱分解(特征分解)，其特征向量组成的矩阵是 ，根据特征方程的定义我们可以得到 。通过对比我们可以发现 相当于 , 相当于 。因此在Graph上的傅里叶变换可以写作 .

从傅里叶变换的基本思想来看，对 进行傅里叶变换的本质就是将 转换为一组正交基下的坐标表示，进行线性变换，而坐标就是傅里叶变换的结果，下图中的 就是 在第一个基上的投影分量的大小。

我们通过矩阵乘法将Graph上的傅里叶变换推广到矩阵形式：

是Graph上第 个节点的特征向量，可得Graph上的傅里叶变换形式： 。 此处的 是Graph的拉普拉斯矩阵的特征向量组成的特征矩阵的转置，在拉普拉斯矩阵的优良性质中我们知道拉普拉斯矩阵的特征向量组成的矩阵为正交阵，即满足 ，所以Graph的逆傅里叶变换形式为 ，矩阵形式如下：

到此为止我们已经通过类比从传统的傅里叶变换推广到了Graph上的傅里叶变换。接下来我们就要借助傅里叶变换这个桥梁使得Convolution与Graph把酒言欢了。

在前言中我们了解了大名鼎鼎的卷积定理：函数卷积的傅里叶变换是其傅里叶变换的乘积，即对于 ,两者的卷积是其傅里叶变换的逆变换： 我们把上一节中得到的Graph上的傅里叶变换公式代入得到： 是Hamada积，表示逐点相乘。 我们一般将 看作输入的Graph的节点特征，将 视为可训练且参数共享的卷积核来提取拓扑图的空间特征。为了进一步看清楚卷积核 ，我们将上式改写为： 也许有人对于上式的变换心存疑虑，证明其实很简单，有意者请看这位答主的解答 GCN中的等式证明 - 知乎

至此，我们已经推导出来GCN的雏形。

1. 第一代GCN 卷积操作的核心是由可训练且参数共享的卷积核，所以第一代GCN是直接把上式中的 中的对角线元素 替换为参数 。先初始化赋值，然后通过反向传播误差来调整参数 。 所以第一代GCN就变成了酱个样子： 是Graph中每个节点特征的表示向量， 是每个节点经过GCN卷积之后的输出。Graph中的每个节点都要经过卷积核卷积来提取其相应的拓扑空间，然后经过激活函数 传播到下一层。 第一代GCN的缺点也是显而易见的，主要有以下几点，

2. 第二代GCN 面对第一代GCN参数过多的缺点，第二代GCN进行了针对性的改进。由于Graph上的傅里叶变换是关于特征值的函数 ， 也可写作 ，用k阶多项式对卷积核进行改进: 将其代入到 可以得到： 所以第二代GCN是介个样子： 可以看出二代GCN的最终化简结果不需要进行矩阵分解，直接对拉普拉斯矩阵进行变换。参数是 ，k一般情况下远小于Graph中的节点的数量 ，所以和第一代GCN相比，第二代GCN的参数量明显少于第一代GCN，减低了模型的复杂度。对于参数 ，先对其进行初始化，然后根据误差反向传播来更新参数。但是仍旧需要计算 ，时间复杂度为 . 另外我们知道对于一个矩阵的k次方，我们可以得到与中心节点k-hop相连的节点，即 中的元素是否为0表示Graph中的一个结点经过k跳之后是否能够到达另外一个结点，这里的k其实表示的就是卷积核感受野的大小，通过将每个中心节点k-hop内的邻居节点聚合来更新中心节点的特征表示，而参数 就是第k-hop邻居的权重。

未完待续。

1.在谱域图卷积中，我们对图的拉普拉斯矩阵进行特征分解。通过在傅里叶空间中进行特征分解有助于我们我们理解潜在的子图结构。ChebyNet, GCN是使用谱域卷积的典型深度学习架构。

2.空域卷积作用在节点的邻域上，我们通过节点的k-hop邻居来聚合得到节点的特征表示。空域卷积相比谱域卷积更加简单和高效。GraphSAGE和GAT 是空域卷积的典型代表。

参考文献 1. 2. 3.