圖傅里葉變換（GFT）

從離散餘弦變換的正交基的特徵來看看提取頻域信號的基向量應該具有什麼性質：

窗寬爲8的一維 DCT 的基向量如上圖所示，從左到右，信號的變化由慢變快，第一個向量對應直流信號，最後一個對應最高頻信號。

用一個具體的量來衡量這種變化快慢就是 過零點數。從左到右，向量的過零點數分別爲：0,1,2,3,4,5,6,7。因爲窗口大小爲8，過零點數最大也只能是7。

通過上述觀察，我們可以類似地構造圖信號的正交基向量，希望它有如下性質：

• 相互正交
• 過零點數逐漸增加，變化快慢逐漸增加

事實上，圖的拉普拉斯矩陣 $L = D - W$L=D−W 的特徵向量正好具有上述性質，如下圖所示：

因爲， $L\in \mathbb{R}^{N\times N}$L∈RN×N 的特徵向量 $\{u_1,\ldots,u_N\},${u1​,…,uN​}, 正好是如下優化問題的解：
$u_1 = \underset{ ||f||=1}{arg min} f^TLf \\ u_2 = \underset{f\perp u_1, ||f||=1}{arg min} f^TLf \\ \cdots \\ u_N = \underset{f\perp u_1,u_2,\ldots,u_{N-1},\\ ||f||=1} {argmin}f^TLf$u1​=∣∣f∣∣=1argmin​fTLfu2​=f⊥u1​,∣∣f∣∣=1argmin​fTLf⋯uN​=f⊥u1​,u2​,…,uN−1​,∣∣f∣∣=1argmin​fTLf
因爲 $L$L 爲半正定陣，所以 $min f^TLf=0$minfTLf=0，當且僅當 $f=k\vec{\mathbf{1}},k\in R$f=k1 ,k∈R，所以 $u_1 = \frac{1}{\sqrt{N}} \vec{\mathbf{1}}$u1​=N ​1​1 .

當 $\lambda_1\leq\lambda_2\leq\ldots\leq\lambda_N$λ1​≤λ2​≤…≤λN​，易知：
$\lambda_1 = \underset{ ||f||=1}{min} f^TLf =0\\ \lambda_2 = \underset{f\perp u_1, ||f||=1}{min} f^TLf \\ \cdots \\ \lambda_N = \underset{f\perp u_1,u_2,\ldots,u_{N-1},\\ ||f||=1} {min}f^TLf =\lambda_{max}$λ1​=∣∣f∣∣=1min​fTLf=0λ2​=f⊥u1​,∣∣f∣∣=1min​fTLf⋯λN​=f⊥u1​,u2​,…,uN−1​,∣∣f∣∣=1min​fTLf=λmax​

實際上， $f^TLf = \sum_{i<j}(f_i-f_j)^2$fTLf=∑i<j​(fi​−fj​)2 表示圖信號的總體變分 ，反應圖信號在圖上的變化快慢。

GFT

對於無向圖，拉普拉斯矩陣 $L$L是對稱的，所以保證有 N 個特徵向量，對 L 特徵分解得： $L = U\Lambda U^T$L=UΛUT再寫明白點就是 $LU = L[u_1,\ldots,u_N] = [Lu_1,\ldots,Lu_N]=[\lambda_1u_1,\ldots,\lambda_N u_N] = U\Lambda$LU=L[u1​,…,uN​]=[Lu1​,…,LuN​]=[λ1​u1​,…,λN​uN​]=UΛ其中 $U$U爲單位正交陣，即 $UU^T=U^TU=I$UUT=UTU=I

$U = [u_1,\ldots,u_N]$U=[u1​,…,uN​] 即爲拉普拉斯矩陣的 N 個單位特徵（列）向量。

傅里葉變換就是將原信號在正交基上展開：
$x = U\hat{x}= [u_1,\ldots,u_N][\hat{x}_1,\ldots,\hat{x}_N]^T$x=Ux^=[u1​,…,uN​][x^1​,…,x^N​]T
其中 $\hat{x} = U^T x$x^=UTx就是原始圖信號 $x$x的圖傅里葉變換，對應各正交分量上的係數，即原信號在各個基向量上投影。