上一章讨论了矩阵的特征向量和谱分解相关的内容，我们更有基础去理解拉普拉斯算子和傅里叶变换之间千丝万缕的关系。这一章的主要内容就是讨论拉普拉斯算子的特征函数和傅里叶变换间的龃龉。

卷积与傅里叶变换(Convolutions)

首先了解下卷积与傅里叶变换间的关系，这部分可参考资料很多

卷积是两个函数之间的运算，具体来说，是两个函数相乘后求积分。这种运算可以获取两个函数作用后的结果，如果我们固定其中一个函数作为卷积核，那么这种运算可以得到不同的函数和卷积核作用后的结果。数学定义如下：

$(f\star h)(\mathbf{x})=\int _{\mathbb{R}^d} f(\mathbf{y})h(\mathbf{x-y})d\mathbf{y}$

如果学过傅里叶变换，我们知道有一个重要的结论，两个函数卷积的傅里叶变换等于两个函数先各自做傅里叶变换然后相乘，也就是“时域做卷积等于频域做乘积”:

$(f\star h)(\mathbf{x})=\mathcal{F}^{-1}(\mathcal{F(f(\mathbf{x}))\circ F(h(\mathbf{x}))})$

其中d维傅里叶变换定义为:

$\mathcal{F}(f(\mathbf{x}))=\hat{f}(\xi)=\int_{\mathbb{R^d}} f(\mathbf{x})e^{-2\pi \mathbf{x}^{\top}\xi i}d\mathbf{x}$

上面定义的是连续卷积和傅里叶变换，实际我们处理的信号都是离散的，需要针对性的进行改写(注意离散形式是经过严格数学证明的，当离散的数据趋近于无穷多的时候，两者具有某种程度的等价性，并不是所有算子都有离散形式的)。

拉普拉斯算子的谱分解

上一章讲完了有限维度线性变换的谱分解，然后我们再来看无限维空间下的谱定理，虽然有很多结论是不能通用的，但是不妨碍我们去类比理解。我们将视角放到函数空间，并且列出一些线性算子:

傅里叶变换：

$\mathcal{F}(f(x))=\hat{f}(\xi)=\int_{\mathbb{R^d}} f(x)e^{-2\pi x\cdot\xi i}dx$

它满足线性映射的条件：

$\begin{aligned} \mathcal{F}(f+g)&=\mathcal{F}(f)+\mathcal{F}(g)\\ \mathcal{F}(kf)&=k\mathcal{F}(f)\\ \end{aligned}$

拉普拉斯算子：

$\Delta f=\sum^d_{j=1}\frac{\partial^2f}{\partial x^2_j}$

它也满足线性映射的条件：

$\begin{aligned} \Delta(f+g)&=\Delta(f)+\Delta(g)\\ \Delta(kf)&=k\Delta(f)\\ \end{aligned}$

下面我们将会展现拉普拉斯算子的一些独特的性质。首先有一个事实，拉普拉斯算子是自伴的。伴随算子A的定义为：对于空间V中的所有向量v和w,都有$(Av,w)=(v,A^* w)$，那么$A^*$称为A的伴随算子。类似于矩阵中的矩阵转置。自伴算子就是$A^*=A$，类似于矩阵中的对称矩阵。既然拉普拉斯算子是自伴算子，那么由谱定理可知，它一定可以被对角化，并且它的特征函数可以构成一个酉算子。

拉普拉斯算子的特征函数是什么呢？其实可以通过多种直观的方法得到，因为拉普拉斯算子是二阶微分，微分算子大多在$e^x$这类指数函数上是保持不变的，我们设$f(x)=e^{2\pi i x\cdot \xi}$，那么:

$\Delta f(x)=-4\pi^2|\xi|^2 f(x)$

可以看见,$\Delta$的特征函数就是$f(x)$，特征值就是$-4\pi^2|\xi|^2$。当$\xi$为任意实数的时候，说明$\Delta$的特征值有无数个。好巧不巧的是，这个特征函数正好是傅里叶变换中的所谓”基函数”。我们马上会推导出一个有趣的结果：

对与任意一个函数$f(x)$,将其用傅里叶逆变换表示为:

$\begin{aligned} \Delta f(x)&=\Delta\int_{\mathbb{R^d}} \hat{f}(\xi)e^{2\pi i x\cdot\xi }d\xi\\ &=\int_{\mathbb{R^d}} \hat{f}(\xi)\Delta e^{2\pi i x\cdot\xi }d\xi \\ &=\int_{\mathbb{R^d}} -4\pi^2|\xi|^2 \hat{f}(\xi) e^{2\pi i x\cdot\xi }d\xi \end{aligned}$

同时，$\Delta f$整体作为一个函数，也可以用傅里叶逆变换表示为：

$\Delta f(x)=\int_{\mathbb{R^d}} \widehat{\Delta f}(\xi)e^{2\pi i x\cdot\xi }d\xi\\$

然后我们得到了下面的等式：

$\widehat{\Delta f}(\xi)=-4\pi^2|\xi|^2 \hat{f}(\xi)$

换个更好看的方式：

$\mathcal{F}(\Delta f)(\xi)=-4\pi^2|\xi|^2 \mathcal{F}(f)(\xi)$

再两边都加上傅里叶逆变换：

$\Delta f(\xi)=\underbrace{ \mathcal{F^{-1}}(\underbrace{ -4\pi^2|\xi|^2 \underbrace{\mathcal{F}(f)}_{傅里叶变换}}_{乘特征值})}_{傅里叶逆变换}(\xi)$

对比上一章我们的矩阵谱分解:

$T\alpha=\underbrace{P\underbrace{\Lambda \underbrace{P^{-1}\alpha}_{将特征向量变换到标准正交基}}_{每个特征向量乘上对应的特征值}}_{将标准正交基变回特征向量}$

其实两个是可类比的，我们现在可以说，拉普拉斯算子的全体特征函数（傅里叶基函数）构成了函数空间的一个规范正交基()，它们的逆变换就是傅里叶变换。

离散傅里叶变换的矩阵

上面我们讨论了连续拉普拉斯算子的谱分解，类比了矩阵的对角化。虽然很直观，但是连续拉普拉斯算子是作用在无限维的向量空间，矩阵是作用在有限维的向量空间，当我们实际进行工程计算的时候，只能处理有限维的空间，这里就涉及到算子的离散化，算子离散化的核心问题就是，当采样点趋近于无穷多的时候，离散算子能否收敛至连续算子。

研究离散Fourier变换的另一个好处是，可以更加直观的感受所谓傅里叶基是如何组成傅里叶变换的。不会讨论的很复杂。

连续的傅里叶变换为:

$\mathcal{F}(f(x))=\hat{f}(\xi)=\int_{\mathbb{R^d}} f(x)e^{-2\pi x\cdot\xi i}dx$

当时域x为离散取值时，例如取N个样本，并且间隔为T，定义为$f[0],f[1],…,f[k],…f[N-1]$。其余非样本点都取f(x)=0，那么连续傅里叶变换的积分就变成了求级数：

$\begin{aligned} \hat{f}(\xi)&=f[0]e^{-2\pi0\cdot\xi i}+f[1]e^{-2\pi T\cdot\xi i}+...+f[k]e^{-2\pi kT\cdot\xi i}+...+f[N-1]e^{-2\pi(N-1)T\cdot\xi i}\\ \end{aligned}$

得到：

$\hat{f}(\xi)=\sum^{N-1}_{k=0}f[k]e^{-2\pi kT\cdot\xi i}$

设

$\xi=0,\frac{1}{NT},\frac{1}{NT}\times2,...,\frac{1}{NT}\times (N-1)$

最后得到傅里叶变换的离散形式：

$\hat{f}[n]=\sum^{N-1}_{k=0}f[k]e^{-\frac{2\pi}{N}nk i} \ \ \ \ \ \ (n=0:N-1)$

我们把级数写成矩阵形式：

$\left[ \begin{matrix} \hat{f}[0]\\ \hat{f}[1]\\ \hat{f}[2]\\ \vdots\\ \hat{f}[N-1]\\ \end{matrix} \right]= \left[ \begin{matrix} 1&1&1&1\cdots& 1\\ 1&W&W^2&W^3\cdots& W^{N-1}\\ 1&W^2&W^4&W^6\cdots& W^{N-2}\\ 1&W^3&W^6&W^9\cdots& W^{N-3}\\ \vdots\\ 1&W^{N-1}&W^{N-2}&W^{N-3}\cdots& W\\ \end{matrix} \right] \left[ \begin{matrix} f[0]\\ f[1]\\ f[2]\\ \vdots\\ f[N-1]\\ \end{matrix} \right]$

其中$W=exp(-i2\pi /N)$。中间的大矩阵F就是离散傅里叶变换的矩阵形式。现在给出一些事实，当样本间的间隔T趋近于无穷小的时候，N趋近于无穷大，矩阵F变成无限维矩阵，并且离散傅里叶变换逐渐收敛于连续傅里叶变换，矩阵逐渐变成了函数空间的算子。

结合上一节中说到的拉普拉斯算子的谱分解，由特征函数组成的傅里叶变换算子，可以看成是F逐渐逼近得到的。那么一维离散拉普拉斯算子就可以按照上面写成：

$L=F^{-1} \Lambda F$

其中F矩阵就是离散傅里叶变换矩阵，并且:

$\Lambda=\left[ \begin{matrix} 0&0&0&0\cdots& 0\\ 0&-4\pi^2|\frac{1}{NT}|^2&0&0\cdots& 0\\ 0&0&-4\pi^2|\frac{2}{NT}|^2&0\cdots& 0\\ 0&0&0&-4\pi^2|\frac{3}{NT}|^2\cdots& 0\\ \vdots\\ 0&0&0&0\cdots&-4\pi^2|\frac{N-1}{NT}|^2\\ \end{matrix} \right]$

同样的，当$N\rightarrow ∞$且$T\rightarrow0$的时候，一维离散拉普拉斯算子收敛至一维连续拉普拉斯算子。

这章详细讨论了连续拉普拉斯算子和傅里叶变换之间的关系，在最后也简单推导了下离散傅里叶矩阵，下一章的核心内容就是理清Graph Laplacian和Laplacian之间的关系，既然拉普拉斯算子的特征函数可以构成傅里叶变换，那么图拉普拉斯算子凭什么也可以呢？

Graph Laplacian

图拉普拉斯算子定义为 $L=D-A$，其中D为度矩阵，A为邻接矩阵。这样定义的核心想法是要在图上模拟连续的拉普拉斯算子，就是求某个节点周围邻居与其的二阶差分之和。现在很少有资料讲图拉普拉斯算子和连续拉普拉斯算子之间的联系，基本上都是这样的套路：

因为连续的拉普拉斯算子的特征函数是傅里叶变换的基函数，所以，图上的拉普拉斯算子的特征向量就是离散傅里叶变换的基。

这句话包含的信息量太大。首先，上面一节讨论的一位连续拉普拉斯算子是在欧式空间中的，它的离散形式比较简单，但是我们实际的数据假如处于高维空间的低维流形上，连续拉普拉斯算子的形式就变了，那么，它的离散形式该是什么样呢？再次，离散和连续lplacian的特征值和特征函数是什么样的关系，和我们期望的是一样的吗？

这两个问题很难直接得到答案，因为这是一个研究方向，即针对离散拉普拉斯算子的收敛性做的研究，因为我数学也不是很好，这部分涉及到微分流形、函数的收敛性以及算子的特征函数等内容，理论性太强，看的我头皮发麻，也是看个大概，后面一章会简单说说几篇论文和他们的思路。

参考文献

[1] Fourier Transform .TERENCE TAO

[2] Lecture 7-The Discrete Fourier Transform