圖論傅立葉轉換

圖論傅立葉轉換（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、正規化拉普拉斯矩陣L_N。
• 圖論傅立葉轉換與頻域分解：
  • 考慮圖位移$A$的廣義特徵分解（Jordon decomposition）$S=VJV^{-1}$
  • 定義$V$為頻域基底矩陣，$V^{-1}$為圖論傅立葉轉換矩陣，也就是說對於圖信號$s$，${\hat {s}}=V^{-1}s$ 為其圖論傅立葉轉換。

廣義定義之範例

• N點離散傅立葉轉換（DFT）可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
  1. 圖$G$選定為N點的有向環。
  2. 圖位移$S$選定$G$的連接矩陣。

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

參考

• A. Sandryhaila and Jose M. F. Moura, Discrete Signal Processing on Graphs,　[[arxiv:1210.4752|http://arxiv.org/abs/1210.4752 （页面存档备份，存于互联网档案馆）]]