圖論傅立葉轉換（Graph Fourier Transform，GFT），是將離散傅立葉轉換延伸至處理圖訊號時的推廣型態。其轉換函數由其預設的圖決定，沒有既定的方程式表示法。
在形式上，變換兩端（時域和頻域）的資料維度皆為有限長。
常見定義
一個已編號的N點一般圖（有限不重邊無向圖）G，考慮它的拉普拉斯矩陣（Laplacian matrix）L：
:L = D-W
其中D為此圖的度數矩陣，W為邻接矩陣。
因L為實對稱矩陣，L會有特徵分解：
:L=V \Lambda V^{-1}
且其中V為正交基底矩陣，\Lambda為特徵值對角矩陣。
此時定義 V^{-1}即為在此圖上的圖論傅立葉轉換矩陣。
現有一圖訊號依相同編號表示為向量形式
:s=(s_1,s_2, ... s_N)^T, 其中s_k表示編號為k的頂點上的訊號值
則它的圖論傅立葉轉換為
:\hat{s}=V^{-1}s
其中\hat{s}的第k項之頻率值為\Lambda_{k,k}。
相反地，逆圖論傅立葉轉換即是將過程逆進行：
:s = V\hat{s}
廣義定義
對於一個N點的圖G（可為有向，但通常有限、不重邊），圖論傅立葉轉換的其中一種定義過程為：
- 基本算子：圖位移（Graph Shift）：
** 圖位移S: \mathbb{C}^N\rightarrow \mathbb{C}^N線性映射，可表為一N階方陣 。
圖位移是一個抽象定義**，並沒有特別指對G使用哪種特定方法構造出來的為圖位移。
比較被使用的圖位移有：連接矩陣A、拉普拉斯矩陣L、正規化拉普拉斯矩陣LN**。
- 圖論傅立葉轉換與頻域分解：
** 考慮圖位移A的廣義特徵分解（Jordon decomposition）S = VJV^{-1}
** 定義V為頻域基底矩陣，V^{-1}為圖論傅立葉轉換矩陣，也就是說對於圖信號s，\hat{s}=V^{-1}s 為其圖論傅立葉轉換。
廣義定義之範例
- N點離散傅立葉轉換（DFT）可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
*# 圖G選定為N點的有向環。
*# 圖位移S選定G的連接矩陣。
- N點的第二型離散餘弦轉換（DCT-II）可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
*# 圖G選定為N點的無向道路。
*# 圖位移S選定G的拉普拉斯矩陣。
*NxM點的二維DCT-II可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
*# 圖G選定為NxM點的柵格。
*# 圖位移S選定G的拉普拉斯矩陣。
參考
- A. Sandryhaila and Jose M. F. Moura, Discrete Signal Processing on Graphs, //arxiv.org/abs/1210.4752
评论 (0)