图论傅里叶变换


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

在形式上,变换两端(时域和频域)的资料维度皆为有限长。

常见定义

一个已编号的N点一般图(有限不重边无向图)G,考虑它的拉普拉斯矩阵(Laplacian matrix)L:

 

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

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

 

且其中 为正交基底矩阵, 特征值对角矩阵。

此时定义  即为在此图上的图论傅里叶变换矩阵

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

 , 其中 表示编号为k的顶点上的信号值

则它的图论傅里叶变换为

 

其中 的第k项之频率值为 

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

 

广义定义

对于一个N点的图 (可为有向,但通常有限、不重边),图论傅里叶变换的其中一种定义过程为:

  • 基本算子:图位移(Graph Shift):
    • 图位移 线性映射,可表为一N阶方阵 。
    • 图位移是一个抽象定义,并没有特别指对G使用哪种特定方法构造出来的为图位移。
    • 比较被使用的图位移有:连接矩阵A拉普拉斯矩阵L正规化拉普拉斯矩阵LN
  • 图论傅里叶变换与频域分解:
    • 考虑图位移 的广义特征分解(Jordon decomposition) 
    • 定义 为频域基底矩阵, 为图论傅里叶变换矩阵,也就是说对于图信号   为其图论傅里叶变换。

广义定义之范例

  • N点离散傅里叶变换(DFT)可由图论傅里叶变换的广义定义,经由以下选择得到:
    1.  选定为N点的有向
    2. 图位移 选定 连接矩阵
  • N点的第二型离散余弦变换(DCT-II)可由图论傅里叶变换的广义定义,经由以下选择得到:
    1.  选定为N点的无向道路
    2. 图位移 选定 拉普拉斯矩阵
  • NxM点的二维DCT-II可由图论傅里叶变换的广义定义,经由以下选择得到:
    1.  选定为NxM点的栅格。
    2. 图位移 选定 拉普拉斯矩阵

参考