圖論傅立葉轉換

圖論傅立葉轉換（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）可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
 圖選定為N點的有向環。
 圖位移選定的連接矩陣。

 N點的第二型離散餘弦轉換（DCT-II）可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
 圖選定為N點的無向道路。
 圖位移選定的拉普拉斯矩陣。
NxM點的二維DCT-II可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
 圖選定為NxM點的柵格。
 圖位移選定的拉普拉斯矩陣。

 參考 
 A. Sandryhaila and Jose M. F. Moura, Discrete Signal Processing on Graphs,　http://arxiv.org/abs/1210.4752 
Category:图论