定义
对图的拉普拉斯矩阵进行特征值分解，这个过程被称为图傅里叶变换，得到的特征值为图傅里叶变换的谱，得到的特征向量为图傅里叶变换的变换基底。
举例而言，对于图1中国存在的由图像像素构成的图（graph）而言，首先使用边缘检测算法检测出小方块内存在的边缘；然后将除了边缘部分的图像分割成4×4的小方块；随后将小方块内的每个像素点都建模为图里面的顶点；最后，通过像素点相对边缘的位置进行边的取值——如果两个像素点没有被边缘切开就认为这两个像素点之间存在着一条权重为1的边，反之，如果两个像素点被一条边缘给切开了，那么这两个像素点之间的就不存在边。在图的建模完成之后，再对图计算邻接矩阵A和度数矩阵D，并且得到拉普拉斯矩阵L=D-A。如果对拉普拉斯矩阵L求特征值，由于L是实对称矩阵，所以一定存在L=U∧UT，其中U是特征向量组成的矩阵，∧是特征值组成的对角矩阵，不同特征值对应的不同的特征向量正交，并且U和UT正交。此时得到的U和UT就是图傅里叶变换的基底，∧即为图傅里叶变换得到的谱。
图 1 图的建模过程以及拉普拉斯矩阵的计算方式[2]
参考文献
[1] Wei Hu, Gene Cheung, Antonio Ortega et al. “Multiresolution graph fourier transform for compression of piecewise smooth images”. IEEE Transactions on Image Processing, 2015, 24(1): 419– 433.
[2] Shen G, Kim W S, Narang S K, et al. Edge-adaptive transforms for efficient depth map coding[C]//28th Picture Coding Symposium. IEEE, 2010: 566-569.
[3] Hammond D K, Vandergheynst P, Gribonval R. Wavelets on graphs via spectral graph theory[J]. Applied and Computational Harmonic Analysis, 2011, 30(2): 129-150.
