图论傅里叶变换
图论傅里叶变换(Graph Fourier Transform,GFT),是将离散傅里叶变换延伸至处理图信号时的推广型态。其变换函数由其预设的图决定,没有既定的方程式表示法。
在形式上,变换两端(时域和频域)的资料维度皆为有限长。
常见定义
编辑一个已编号的N点一般图(有限不重边无向图)G,考虑它的拉普拉斯矩阵(Laplacian matrix)L:
其中D为此图的度数矩阵,W为邻接矩阵。
且其中 为正交基底矩阵, 为特征值对角矩阵。
此时定义 即为在此图上的图论傅里叶变换矩阵。
现有一图信号依相同编号表示为向量形式
- , 其中 表示编号为k的顶点上的信号值
则它的图论傅里叶变换为
其中 的第k项之频率值为 。
相反地,逆图论傅里叶变换即是将过程逆进行:
广义定义
编辑对于一个N点的图 (可为有向,但通常有限、不重边),图论傅里叶变换的其中一种定义过程为:
- 基本算子:图位移(Graph Shift):
- 图位移 线性映射,可表为一N阶方阵 。
- 图位移是一个抽象定义,并没有特别指对G使用哪种特定方法构造出来的为图位移。
- 比较被使用的图位移有:连接矩阵A、拉普拉斯矩阵L、正规化拉普拉斯矩阵LN。
- 图论傅里叶变换与频域分解:
- 考虑图位移 的广义特征分解(Jordon decomposition)
- 定义 为频域基底矩阵, 为图论傅里叶变换矩阵,也就是说对于图信号 , 为其图论傅里叶变换。
广义定义之范例
编辑参考
编辑- A. Sandryhaila and Jose M. F. Moura, Discrete Signal Processing on Graphs, [[arxiv:1210.4752|http://arxiv.org/abs/1210.4752 (页面存档备份,存于互联网档案馆)]]