圖神經網路基礎：傅里葉級數與傅里葉變換

• 2022 年 1 月 15 日
• 筆記
• ML & DL 雜碎知識

一、從簡單變換到傅里葉級數

　　如下圖所示，在笛卡爾坐標系中，由於我們定義了一組基  $e_{x}=(1,0), e_{y}=(0,1)$  ，因此 坐標系中的所有點才能夠被一個坐標唯一地表示:

　　這樣的好處是有了坐標以後，點與點之間就不再是相互孤立的存在，也就有了距離的關係。這個過程就是一種變換，即把坐標變換到坐標系中。

　　這種簡單的變換是將空間中的點使用一組基來表示，點是基的加權累加。類比到函數中，對於一個函數，我們期待使用一組基函數來表示。傅里葉級數與傅里葉變換就是用來辦到這件事的方法，其中傅里葉級數能夠將任意周期函數表示成一組基函數依照各自的係數的累加，而傅里葉變換針對的是非周期函數。

　　首先間述傅里葉級數，它可以將任意周期函數分解為簡單震蕩函數（正弦函數和餘弦函數， 這些函數作為基函數) 的加和。具體地，對於周期為   $T$ 的周期函數  $f(t) $，可以分解為三角函 數的組合:

　　　　$f(t)=a_{0}+\sum_{n=1}^{+\infty}\left[a_{n} \cos (n \omega t)+b_{n} \sin (n \omega t)\right]$

　　這裡的   $w=\frac{2 \pi}{T}$   ，稱為基頻率。類比笛卡爾坐標系， $a_{0}, a_{n}, b_{n}$   就相當於坐標，而   $1, \cos (n \omega t), \sin (n \omega t) $  就相當於基向量，不同的是， $1, \cos (n \omega t), \sin (n \omega t) $  是一組函 數，而基向量是一組向量，笛卡爾坐標系使用基向量來表示點，傅里葉級數使用基函數來表 示周期函數。

　　這裡保留一個疑問：在上面對任意周期函數 f(t) 的分解公式中，這裡的  $1, \cos (n \omega t), \sin (n \omega t) $   這些基函數都是沒有相位的，也就是說這些基函數在坐標系中都是 關於   $y$   軸對稱的，那麼在   $f(t)$   不關於   $y$   軸對稱時，這些關於   $y $  軸對稱的基函數們真的能夠通 過線性組合得到一個不關於   $y$   軸對稱的周期函數嗎? 這一點是很難直觀想像的，在下面的章 節中我們會證明這件事。

　　本節類比了笛卡爾坐標系與傅里葉級數，首先對變換有一個簡單的概念，接下來的章節會介 紹更多的細節。

二、傅里葉級數

2.1 三角函數系

　　一個三角函數係為：

　　　　$\{1, \sin (\omega x), \cos (\omega x), \sin (2 \omega x), \cos (2 \omega x), \cdots, \sin (n \omega x), \cos (n \omega x), \cdots\}$

　　注意   $1$   也可以看做一個函數，其實也就是   $\cos (0 \omega x)$ ，由於   $\sin (0 \omega x)=0$   ，所以我們就不 管它了。另外這裡的  $ \omega$   也就是上面提到的基頻率，可以看到這個基頻率的大小由要分解的函 數   $f(t) $  的周期   $T$   決定的，也就是說使用傅里葉級數分解周期函數時不同周期的函數要使用不 同的三角函數系來作為基函數。

　　在笛卡爾坐標系中，基向量滿足的性質是不同的基向量之間兩兩正交（內積為 0 ），相同的 基向量內積為 1 。假設兩個基向量   $v$   和   $ m$  ，用下標表示基向量的維度，則他們的內積就是對 應的維度相乘之後的累加：

　　　　$v \cdot m=v_{1} m_{1}+v_{2} m_{2}+\cdots+v_{n} m_{n}=0$

　　傅里葉級數的基函數之間也有類似的性質，基向量之間的內積是以累加的方式計算的，類似 的，基函數之間的內積是以積分的形式計算的。同樣類似的，不同基函數之間的內積為   $0$ ， 同一基函數的內積為一個正數。

　　首先，如果從三角函數系中任意取兩個函數   $f(x), g(x) $ （當然也包括 $1$ 這個函數），有:

　　　　$\int_{-\pi}^{\pi} f(x) g(x) \mathrm{d} x=0$

　　比如：

 　　　　$\begin{array}{l}&\int_{-\pi}^{\pi} 1 \cdot 1 \mathrm{~d} x=2 \pi \\&\int_{-\pi}^{\pi} \sin (n \omega x) \sin (n \omega x) \mathrm{d} x=\pi \\&\int_{-\pi}^{\pi} \cos (n \omega x) \cos (n \omega x) \mathrm{d} x=\pi\end{array}$

2.2 傅里葉級數的直觀理解

2.2.1 矩形波的分解

　　以一個周期矩形波為例，難以想像的是這個矩形波是可以被傅里葉級數分解的。下圖中展示了多個正弦函數如何逐步組合成為一個矩形波，隨著震蕩函數的增加，它們最終就可以組成一個矩形波：

　　注意這裡只有正弦函數而沒有餘弦函數，這裡的正弦函數並非指的是前面對  $f(t)$  的分解公式里的正弦函數，公式里的正弦函數是沒有相位的，而這裡說的正弦函數是有相位的。我們之前說任意周期函數都可以由正弦和餘弦函數累加而組成，這裡的正弦函數和餘弦函數是沒有相位的，而事實上我們只需要有相位的正弦函數就可以組成任意的周期函數了。下圖也同樣展示了這些有相位的正弦波組合成矩形波的過程：

　　這裡的正弦波之間還有一些直線，這些直線其實也是正弦波，只不過振幅為  $0$  ，這說明組成一個周期函數時，可能一些成分是不需要的。

2.2.2 頻譜

　　上面的圖立體地展示了正弦波組合成周期函數的過程，如果我們從側面來看這個立體圖，也就得到了所謂的頻譜（Spectrum）：

　　其實也就相當於以這些正弦波的頻率做橫軸，振幅做豎軸得到影像：

　　　　現在再重新來看一個周期函數的立體分解圖，也就是說從正面來看看到的是時域（Time Domain）的影像，而從側面來看看到的就是頻域（Frequency Domain）影像：

2.2.3 相位譜

　　頻譜記錄了正弦波的頻率和振幅，但沒有記錄相位資訊，同樣的我們可以以頻率為橫軸，相位為縱軸構建一個相位譜（phase spectrum）：

　　利用頻譜和相位譜就可以記錄所有的組成一個周期函數的正弦函數了。最終，放一張集合圖：

2.2.3 傅里葉級數的由來

　　現在我們解釋下面這個式子的由來，也順便回答第一個章節留下的疑問：

　　　　$f(t)=a_{0}+\sum \limits _{n=1}^{+\infty}\left[a_{n} \cos (n \omega t)+b_{n} \sin (n \omega t)\right]$

　　利用帶有相位的正弦函數可以組合成任意的周期函數，當然這裡的基頻率還是   $\omega=\frac{2 \pi}{T} $， 這 個過程用公式可以表示為:

　　　　$f(t)=\sum_{n=0}^{+\infty} A_{n} \sin \left(n \omega t+\varphi_{n}\right)$

　　利用和角公式進行一些變換:

　　　　$\begin{array}{l}f(t)&=\sum\limits _{n=0}^{+\infty} A_{n} \sin \left(n \omega t+\varphi_{n}\right) \\&=\sum\limits_{n=0}^{+\infty} A_{n}\left[\sin (n \omega t) \cos \left(\varphi_{n}\right)+\cos (n \omega t) \sin \left(\varphi_{n}\right)\right] \\&=\sum\limits_{n=0}^{+\infty}\left[A_{n} \cos \left(\varphi_{n}\right) \sin (n \omega t)+A_{n} \sin \left(\varphi_{n}\right) \cos (n \omega t)\right] \\&=A_{0} \cos \left(\varphi_{0}\right) \underbrace{\sin (0 \omega t)}_{=0}+\underbrace{A_{0} \sin \left(\varphi_{0}\right)}_{\text {記作 } a_{0}} \underbrace{\cos (0 \omega t)}_{=1}+\sum\limits_{n=1}^{+\infty}[\underbrace{A_{n} \cos \left(\varphi_{n}\right)}_{\text {記作 } b_{n}} \sin (n \omega t)+\underbrace{A_{n} \sin \left(\varphi_{n}\right)}_{\text {記作 } a_{n}} \cos (n \omega t)] \\&=a_{0}+\sum\limits_{n=1}^{+\infty}\left[a_{n} \cos (n \omega t)+b_{n} \sin (n \omega t)\right]\end{array}$

　　最終得到了我們之前說過的傅里葉級數，同時也解釋了前面留下的疑問。

2.2.4 求解傅里葉級數的係數

　　對於一個周期函數    $f(t)$  ，如何求它分解為傅里葉級數後的係數  $a_{0}, a_{n}, b_{n}$  呢? 同樣類比笛卡 爾坐標系，一個坐標點與一個基向量做內積就可以得到這個坐標點在這個基向量上的係數， 那麼一個周期函數只需要與一個基函數做積分，也就可以得到對應的係數。那麼首先求  $a_{0}$  (  $a_{0} $   對應的基函數為  $\cos (0 t) $ ）:

　　　　$\begin{array}{l}\int_{0}^{T} f(t) \cos (0 t) \mathrm{d} t&=\int_{0}^{T}\left(a_{0}+\sum \limits _{n=1}^{+\infty}\left[a_{n} \cos (n \omega t)+b_{n} \sin (n \omega t)\right]\right) \cos (0 t) \mathrm{d} t \\&=\int_{0}^{T} a_{0} \cos (0 t) \mathrm{d} t+\int_{0}^{T} \sum \limits_{n=1}^{+\infty}[a_{n} \underbrace{\cos (n \omega t) \cos (0 t)}_{\text {積分 } 0}+b_{n} \underbrace{\sin (n \omega t) \cos (0 t)}_{\text {積分為 } 0}] \mathrm{d} t \\&=a_{0} T\end{array}$

　　那麼就有：

　　　　$a_{0}=\frac{1}{T} \int_{0}^{T} f(t) \mathrm{d} t$

　　然後求 $ a_{n}$  ，對應的基函數為 $\cos (n \omega t)$  : 

　　　　$\begin{array}{l}\int_{0}^{T} f(t) \cos (n \omega t) \mathrm{d} t&=\int_{0}^{T}\left(a_{0}+\sum \limits _{m=1}^{+\infty}\left[a_{m} \cos (m \omega t)+b_{m} \sin (m \omega t)\right]\right) \cos (n \omega t) \mathrm{d} t \\&=\int_{0}^{T} a_{0} \cos (n \omega t) \mathrm{d} t+\int_{0}^{T} \sum \limits_{m=1}^{+\infty} a_{m} \cos (m \omega t) \cos (n \omega t) \mathrm{d} t+\int_{0}^{T} \sum_{m=1}^{+\infty} b_{m} \sin (m \omega t) \cos (n \omega t) \mathrm{d} t \\&=\int_{0}^{T} a_{n} \cos (n \omega t) \cos (n \omega t) \mathrm{d} t \\&=\int_{0}^{T} a_{n} \cos ^{2}(n \omega t) \mathrm{d} t \\&=\int_{0}^{T} a_{n} \frac{1+\cos (2 n \omega t)}{2} \mathrm{~d} t \\&=a_{n} \frac{T}{2}\end{array}$

　　那麼就有：

　　　　$a_{n}=\frac{2}{T} \int_{0}^{T} f(t) \cos (n \omega t) \mathrm{d} t$

　　最後用類似的方法求得  $b_{n}$:

　　　　$b_{n}=\frac{2}{T} \int_{0}^{T} f(t) \sin (n \omega t) \mathrm{d} t$

2.2.5 歐拉公式與傅里葉級數

　　首先有歐拉公式如下：

　　　　$e^{i \theta}=\cos (\theta)+i \sin (\theta)$

　　可以簡單的將歐拉公式理解為複數的另一種表示形式， $e^{i \theta} $  看做複數。為了能夠化簡傅里葉級 數的表達形式，我們需要應用到歐拉公式。
　　當   $\theta=n \omega t $   以及  $  \theta=-n \omega t $  時，根據歐拉公式有:

　　　　$\begin{array}{l}e^{i n \omega t}=\cos (n \omega t)+i \sin (n \omega t) \\e^{-i n \omega t}=\cos (n \omega t)-i \sin (n \omega t)\end{array}$

　　那麼：

　　　　$\begin{aligned}\cos (n \omega t) &=\frac{e^{i n \omega t}+e^{-i n \omega t}}{2} \\\sin (n \omega t) &=\frac{e^{i n \omega t}-e^{-i n \omega t}}{2 i}\end{aligned}$

　　將這兩項代入傅里葉級數，並進行整理：

　　　　$\begin{array}{l}f(t)&=a_{0}+\sum \limits _{n=1}^{+\infty}\left[a_{n} \frac{e^{i n \omega t}+e^{-i n \omega t}}{2}+b_{n} \frac{e^{i n \omega t}-e^{-i n \omega t}}{2 i}\right] \\&=a_{0}+\sum \limits_{n=1}^{+\infty}\left(\frac{a_{n}-i b_{n}}{2}\right) e^{i n \omega t}+\sum \limits_{n=1}^{+\infty}\left(\frac{a_{n}+i b_{n}}{2}\right) e^{-i n \omega t} \\&=\sum \limits_{n=0}^{0} a_{n} e^{i n \omega t}+\sum \limits_{n=1}^{+\infty}\left(\frac{a_{n}-i b_{n}}{2}\right) e^{i n \omega t}+\sum \limits_{n=-1}^{-\infty}\left(\frac{a_{-n}+i b_{-n}}{2}\right) e^{i n \omega t} \\&=\sum \limits_{-\infty}^{+\infty} c_{n} e^{i n \omega t}\end{array}$

　　其中：

　　　　$\begin{array}{l}\text { 當 } n=0 \text { 時 }, c_{n}=a_{0} \\\text { 當 } n=1,2,3, \cdots \text { 時, } c_{n}=\frac{a_{n}-i b_{n}}{2} \\\text { 當 } n=-1,-2,-3, \cdots \text { 時, } c_{n}=\frac{a_{-n}+i b_{-n}}{2}\end{array}$

　　上一小節我們求得了係數  $a_{0}, a_{n}, b_{n}$  ，現在將這些係數代入經過歐拉公式變換後的傅里葉級 數。首先，當  $n=0$  時:

　　　　$\begin{array}{l}c_{n}=a_{0} \\=\frac{1}{T} \int_{0}^{T} f(t) \mathrm{d} t \\=\frac{1}{T} \int_{0}^{T} f(t) e^{-i 0 \omega t} \mathrm{~d} t\end{array}$

　　$\text { 當 } n=1,2,3, \cdots \text { 時: }$

　　　　$\begin{array}{l}c_{n}&=\frac{a_{n}-i b_{n}}{2} \\&=\frac{\frac{2}{T} \int_{0}^{T} f(t) \cos (n \omega t) \mathrm{d} t-i \frac{2}{T} \int_{0}^{T} f(t) \sin (n \omega t) \mathrm{d} t}{2} \\&=\frac{1}{T} \int_{0}^{T} f(t)[\cos (n \omega t)-i \sin (n \omega t)] \mathrm{d} t \\&=\frac{1}{T} \int_{0}^{T} f(t) e^{-i n \omega t} \mathrm{~d} t\end{array}$

　　可見對於任意的 $n$ ，所有的 $c_{n}$ 的表達式都是一樣的，總結一下，傅里葉級數最終可以寫為:

　　　　$f(t)=\sum_{n=-\infty}^{+\infty} c_{n} e^{i n \omega t}, \text { 其中 } c_{n}=\frac{1}{T} \int_{0}^{T} f(t) e^{-i n \omega t} \mathrm{~d} t$

　　上面的式子也就說明，任意的一個周期為  $t$  的周期函數，都可以使用一組  $c_{n}$  來表示它。也就 是說，在時域內  $(t, f(t))$  可以唯一地確定函數  $f(t)$  ，而在頻域內，函數  $f(t)$  由  $\left(n, c_{n}\right)$  來 唯一確定，這就是從時域到頻域的轉換，如下圖：

 　　上圖右邊縱軸  $c_{n}$  其實是個複數，可以理解為應該有兩個維度，一個實部，一個虛部，但是這 里為了簡單畫圖，就把它畫成了實數，但其實它是個複數。

三、傅里葉變換

　　傅里葉變換針對非周期函數，一個非周期函數可以看做周期無限大的函數。同樣的以 $\boldsymbol{\omega}$ 作為 基頻率，滿足 $\omega=\frac{2 \pi}{T}$ ，當 $T \rightarrow+\infty$ 時， $ \omega \rightarrow 0 $ ，又有 $\omega=(n+1) \omega-n \omega=\Delta \omega $ ，因此 $\Delta \omega \rightarrow 0$ 。

　　在這裡我們將 $c_{n}$ 寫作從 $-\frac{T}{2}$ 到 $\frac{T}{2} $ 的積分:

　　　　$c_{n}=\frac{1}{T} \int_{-\frac{T}{2}}^{\frac{T}{2}} f(t) e^{-i n \omega t} \mathrm{~d} t$

　　那麼對於非周期函數  $f(t)$  來說有：

　　　　$\begin{array}{l}f(t)&=\underset{T \rightarrow+\infty}{lim}    \sum \limits_{n=-\infty}^{+\infty} c_{n} e^{i n \omega t} \\&=\underset{T \rightarrow+\infty}{lim}    \sum \limits_{n=-\infty}^{+\infty} \frac{1}{T} \int_{-\frac{T}{2}}^{\frac{T}{2}} f(t) e^{-i n \omega t} \mathrm{~d} t \cdot e^{i n \omega t} \\&=\underset{\Delta \omega \rightarrow 0}{lim}    \sum \limits_{n=-\infty}^{+\infty} \frac{\Delta \omega}{2 \pi} \int_{-\infty}^{+\infty} f(t) e^{-i n \omega t} \mathrm{~d} t \cdot e^{i n \omega t}\end{array}$

　　從下圖中可以看做，當  $\Delta \omega \rightarrow 0$  時，雖然 $n$  為離散的量，但是  $n \omega$  會變成一個連續的量: 

　　注意   $\Delta \omega=\omega$  ，另外我們令  $ W=n \omega$   ，那麼我們有:  

　　　　$\begin{array}{l}f(t)&=\lim _{\omega \rightarrow 0} \sum \limits _{n=-\infty}^{+\infty} \frac{\omega}{2 \pi} \int_{-\infty}^{+\infty} f(t) e^{-i n \omega t} \mathrm{~d} t \cdot e^{i \pi \omega t} \\&=\int_{-\infty}^{+\infty} \frac{1}{2 \pi}\left(\int_{-\infty}^{+\infty} f(t) e^{-i W t} \mathrm{~d} t\right) e^{i W t} \mathrm{~d} W \\&=\frac{1}{2 \pi} \int_{-\infty}^{+\infty}\left(\int_{-\infty}^{+\infty} f(t) e^{-i W t} \mathrm{~d} t\right) e^{i W t} \mathrm{~d} W\end{array}$

　　注意這裡的  $\int_{-\infty}^{+\infty} f(t) e^{-i W t} \mathrm{~d} t$  是對   $t$  進行積分，因此它是關於 $W$  的函數，定義:  

　　　　$F(W)=\int_{-\infty}^{+\infty} f(t) e^{-i W t} \mathrm{~d} t$

　　$F(W)$   就是   $f(t)$  的傅里葉變換，將 $F(W)$ 代入 $f(t)$ 得:

　　　　$f(t)=\frac{1}{2 \pi} \int_{-\infty}^{+\infty} F(W) e^{i W t} \mathrm{~d} W$

　　$f(t)$  就是傅里葉變換的逆變換。 

參考：

　　1、圖卷積神經網路(GCN)深入理解(1) 矩陣的譜分解

　　2、圖卷積神經網路課程筆記（一）——譜域圖卷積（Spectral）背景知識及經典模型