如何理解拉普拉斯矩阵的特征值表示图傅里叶变换的频率
1 谐波中的频率含义
众所周知，对于傅里叶变换 \mathcal{F}[f(t)] =\int f(t)e^{-i\omega t}dt ， \omega 表示谐波 \sin \omega t,\cos \omega t 的频率 。
如果从特征值与特征向量的角度来看，有 \Delta e^{-iwt}= -w^2 e^{-iwt} ，也就是说 \omega 和 e^{-iwt} 分别是拉普拉斯算子的特征值和特征向量。
综上两点，可以表述为： 在傅里叶变换中，特征值 \omega 表示特征向量 e^{-iwt} 的频率。
同时，频率的高低具有明确的物理意义 。为直观展示，下面绘制了 \sin t , \sin 3t 与 \sin 6t 的函数图像。
从上可以看出： 低频率的谐波变化稳定，起伏平滑；而高频率的谐波变化剧烈，波动明显。
随着频率的增加，谐波会更频繁地穿过零点。
如果利用定量的统计指标， 可以看出谐波的过零点（zero crossings）会随着频率的增大而显著增加 ：
由此，我们不禁联想到： 当把傅里叶变换拓展到图上之后，对于图傅里叶变换，如何理解拉普拉斯矩阵的特征值与频率之间的关系？ 这也正是本文的主题
2 图傅里叶变换的频率含义
对于 N 个顶点的图 \mathcal{G} ， L 是其拉普拉斯矩阵， \lambda_i 和 u_i （ 1\leq i \leq N ）是 L 的第 i 个特征值与特征向量， f\in \mathbb{R}^N 是定义在 \mathcal{G} 上的一个信号，其图傅里叶变换定义为：
\mathcal{F}[f] =[u_1,\cdots,u_N]^\top\cdot f
而对于N个非负特征值可以从小到大排列为： 0=\lambda_1 \le \lambda_2 \le \cdots \le \lambda_N ，同时也将特征向量 u_i 按照对应特征值的从小到大顺序排列。
那么图傅里叶变换是否能与传统傅里叶变换进行类比？以特征值 \lambda_i 表示特征向量 u_i 的频率？
答案是肯定的。
下面以random sensor network graph [1] 为例进行讨论。以下三幅图分别对于特征向量 u_1 ， u_2 及 u_{51} 进行了可视化。红色框架表示图结构，每个节点上的立柱表示特征向量对应的取值，蓝色表示正值，黑色表示负值。
从图中可以看出：
对应于低特征值的特征向量，其起伏变化平缓，具有很强的局部稳定性（local stationary，含义是相邻节点的信号数值较为接近），
对应于高特征值的特征向量，其起伏变化剧烈，局部波动同样明显。
这与传统傅里叶变换中谐波的频率含义完全相同。
用 e_{pq} 表示图 \mathcal{G} 中连接节点 p 与 q 的边， u_i(p) 与 u_i(q) 分别是特征向量 u_i 在节点 p 与 q 上的数值。
那么特征向量 u_i 的过零点（zero crossings）可以定义为满足 ： u_i(p) \cdot u_i(q) < 0 的边 e_{pq} 的数目。
仍以上面的图结构为例， 其特征向量的过零点随特征值变化的关系如下图所示 （横坐标0到15表示数值从小到大的特征值 \lambda_0 到 \lambda_{15} ）
同样可以看出在定量统计指标上，随着特征值的增大，特征向量的过零点逐渐增加，这表明图傅里叶变换的频率含义与传统傅里叶变换仍然相同。
3 结论
通过上面的对比分析，从定性展示和定量统计两个方面都可以看出：无论是在传统的傅里叶变换还是图傅里叶变换中，特征值都可以表示特征向量的变化频率。
参考
- ^ Shuman, D. I., Narang, S. K., Frossard, P., Ortega, A., & Vandergheynst, P. (2013). The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine, 30(3), 83-98.
