图论傅里叶变换

图论傅里叶变换（Graph Fourier Transform，GFT），是将离散傅里叶变换延伸至处理图信号时的推广型态。其变换函数由其预设的图决定，没有既定的方程式表示法。

在形式上，变换两端（时域和频域）的资料维度皆为有限长。

常见定义

一个已编号的N点一般图（有限不重边无向图）G，考虑它的拉普拉斯矩阵（Laplacian matrix）L：

$L=D-W$

其中D为此图的度数矩阵，W为邻接矩阵。

因L为实对称矩阵，L会有特征分解：

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

且其中$V$为正交基底矩阵，$\Lambda$为特征值对角矩阵。

此时定义 $V^{-1}$即为在此图上的图论傅里叶变换矩阵。

现有一图信号依相同编号表示为向量形式

$s=(s_{1},s_{2},...s_{N})^{T}$, 其中$s_{k}$表示编号为k的顶点上的信号值

则它的图论傅里叶变换为

${\hat {s}}=V^{-1}s$

其中${\hat {s}}$的第k项之频率值为$\Lambda _{k,k}$。

相反地，逆图论傅里叶变换即是将过程逆进行：

$s=V{\hat {s}}$

广义定义

对于一个N点的图$G$（可为有向，但通常有限、不重边），图论傅里叶变换的其中一种定义过程为：

• 基本算子：图位移（Graph Shift）：
  • 图位移$S:\mathbb {C} ^{N}\rightarrow \mathbb {C} ^{N}$线性映射，可表为一N阶方阵 。
  • 图位移是一个抽象定义，并没有特别指对G使用哪种特定方法构造出来的为图位移。
  • 比较被使用的图位移有：连接矩阵A、拉普拉斯矩阵L、正规化拉普拉斯矩阵L_N。
• 图论傅里叶变换与频域分解：
  • 考虑图位移$A$的广义特征分解（Jordon decomposition）$S=VJV^{-1}$
  • 定义$V$为频域基底矩阵，$V^{-1}$为图论傅里叶变换矩阵，也就是说对于图信号$s$，${\hat {s}}=V^{-1}s$ 为其图论傅里叶变换。

广义定义之范例

• N点离散傅里叶变换（DFT）可由图论傅里叶变换的广义定义，经由以下选择得到：
  1. 图$G$选定为N点的有向环。
  2. 图位移$S$选定$G$的连接矩阵。

• N点的第二型离散余弦变换（DCT-II）可由图论傅里叶变换的广义定义，经由以下选择得到：
  1. 图$G$选定为N点的无向道路。
  2. 图位移$S$选定$G$的拉普拉斯矩阵。
• NxM点的二维DCT-II可由图论傅里叶变换的广义定义，经由以下选择得到：
  1. 图$G$选定为NxM点的栅格。
  2. 图位移$S$选定$G$的拉普拉斯矩阵。

参考

• A. Sandryhaila and Jose M. F. Moura, Discrete Signal Processing on Graphs,　[[arxiv:1210.4752|http://arxiv.org/abs/1210.4752 （页面存档备份，存于互联网档案馆）]]