图论傅里叶变换

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

${\displaystyle L=D-W}$ 

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

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

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

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

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

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

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

则它的图论傅里叶变换为

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

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

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

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

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

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

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

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

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