查看“︁圖論傅立葉轉換”︁的源代码

{{NoteTA
|G1 = Signals and Systems
}}


'''圖論傅立葉轉換'''（Graph Fourier Transform，GFT），是將[[離散傅立葉轉換]]延伸至處理[[圖訊號]]時的推廣型態。其轉換函數由其預設的[[圖論|圖]]決定，沒有既定的方程式表示法。

在形式上，變換兩端（時域和頻域）的資料維度皆為有限長。

== 常見定義 ==
一個已編號的N點一般圖（有限不重邊無向圖）G，考慮它的'''拉普拉斯矩陣'''（Laplacian matrix）L：

:<math>L = D-W</math>

其中D為此圖的度數矩陣，W為邻接矩陣。

因L為[[实对称矩阵|實對稱矩陣]]，L會有[[特征分解|特徵分解]]：

:<math>L=V \Lambda V^{-1}</math>

且其中<math>V</math>為正交基底矩陣，<math>\Lambda</math>為[[特征值|特徵值]]對角矩陣。

此時定義 <math>V^{-1}</math>即為在此圖上的'''圖論傅立葉轉換矩陣'''。

現有一圖訊號依相同編號表示為向量形式

:<math>s=(s_1,s_2, ... s_N)^T</math>, 其中<math>s_k</math>表示編號為k的頂點上的訊號值

則它的圖論傅立葉轉換為

:<math>\hat{s}=V^{-1}s</math> 

其中<math>\hat{s}</math>的第k項之頻率值為<math>\Lambda_{k,k}</math>。

相反地，逆圖論傅立葉轉換即是將過程逆進行：

:<math>s = V\hat{s}</math>

== 廣義定義 ==
對於一個N點的圖<math>G</math>（可為有向，但通常有限、不重邊），圖論傅立葉轉換的其中一種定義過程為：
* 基本算子：圖位移（Graph Shift）：
** 圖位移<math>S:  \mathbb{C}^N\rightarrow \mathbb{C}^N</math>線性映射，可表為一N階方陣 。
** 圖位移是一個'''抽象定義'''，並沒有特別指對G使用哪種特定方法構造出來的為圖位移。
** 比較被使用的圖位移有：'''連接矩陣A'''、'''拉普拉斯矩陣L'''、'''正規化拉普拉斯矩陣L<sub>N</sub>'''。
* '''圖論傅立葉轉換'''與頻域分解：
** 考慮圖位移<math>A</math>的廣義特徵分解（Jordon decomposition）<math>S = VJV^{-1}</math>
** 定義<math>V</math>為頻域基底矩陣，<math>V^{-1}</math>為圖論傅立葉轉換矩陣，也就是說對於圖信號<math>s</math>，<math>\hat{s}=V^{-1}s</math> 為其圖論傅立葉轉換。

== 廣義定義之範例 ==
* N點[[離散傅立葉轉換]]（DFT）可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
*# 圖<math>G</math>選定為N點的有向[[環 (圖論)|環]]。
*# 圖位移<math>S</math>選定<math>G</math>的'''連接矩陣'''。

* N點的第二型[[離散餘弦轉換]]（DCT-II）可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
*# 圖<math>G</math>選定為N點的無向[[道路 (图论)|道路]]。
*# 圖位移<math>S</math>選定<math>G</math>的'''拉普拉斯矩陣'''。
*NxM點的二維DCT-II可由圖論傅立葉轉換的廣義定義，經由以下選擇得到：
*# 圖<math>G</math>選定為NxM點的柵格。
*# 圖位移<math>S</math>選定<math>G</math>的'''拉普拉斯矩陣'''。

== 參考 ==
* '''A. Sandryhaila and Jose M. F. Moura''', Discrete Signal Processing on Graphs,　[[arxiv:1210.4752|http://arxiv.org/abs/1210.4752 {{Wayback|url=http://arxiv.org/abs/1210.4752 |date=20181212144124 }}]]
[[Category:图论]]