線性非移變系統理論

線性非移變系統理論建立在圖訊號處理中對線性非移變系統的定義上，致力於承襲線性非時變系統理論在操作上的便利性。

圖位移（Graph Shift）

對於一個N點的圖$G$（可為有向，但通常有限、不重邊），可定義圖位移$S$，為一線性映射從圖訊號時域映射到圖訊號時域，可表為一N階方陣 。

圖位移是一個抽象定義，並沒有特別指對$G$使用哪種特定方法構造出來的為圖位移。

比較被使用的圖位移有：連接矩陣A、拉普拉斯矩陣L、正規化拉普拉斯矩陣L_N。

線性非移變系統

線性非移變系統是圖訊號處理中，有最簡單結構的系統。其性質可最大限度地和數位訊號處理中的線性非時變系統對照，並發展出與之類似的運算，達到想要的訊號處理效果。

定義

在一$N$點的圖上，給定已定義的圖位移$S$，若線性映射$H:\mathbb {C} ^{N}\rightarrow \mathbb {C} ^{N}$滿足$HS=SH$，則稱其為線性非移變系統（LSI）。

基本性質

1. 不受圖位移$S$的作用前後順序影響。
2. 可表示為圖圖位移$S$的多項式，也就是說存在$h$多項式，使得$H=h(S)$。更嚴謹地，若考慮的是N-1階以下的多項式，則$h$唯一存在。

傳遞函數

根據性質2.，再以給定好圖位移的情況下，對所有線性非移變系統$H$，可唯一定義其傳遞函數$h$，$h$為最高次項小於N-1階的多項式，且$H=h(S)$。

基本運算的推廣形式

圖論傅立葉轉換

詳見圖論傅立葉轉換。

摺積

摺積在圖訊號時域中因為沒有顯著的前後關係，無法定義一個良好的計算式。但因同一張圖上的圖訊號在頻域中之頻率值相同，摺積的推廣定義可使用摺積原本的性質：頻域中的峰值相乘，也就是

${\hat {s}}_{out}(\lambda _{k})={\hat {s}}_{1}(\lambda _{k}){\hat {s}}_{2}(\lambda _{k})$

其中$s_{1}$、$s_{2}$為輸入訊號，$s_{out}$為輸出訊號，$\{\lambda _{k}\}_{k=0...N-1}$為頻域之特徵頻率。對上式作逆圖論傅立業轉換，得

$s_{out}(i)=(s_{1}*s_{2})(i)=\sum _{k=0}^{N-1}{\hat {s}}_{1}(\lambda _{k}){\hat {s}}_{2}(\lambda _{k})u_{k}(i)$

其中$\{u_{k}\}_{k=0...N-1}$為圖論傅立葉基底。將此式作為摺積之推廣定義。

上式有另一個使用矩陣的表示法

$s_{out}=VD_{{\hat {s}}_{2}}V^{-1}s_{1}$

其中$V^{-1}$為圖論傅立葉轉換矩陣，$V$即為逆傅立葉轉換矩陣，$D_{{\hat {s}}_{2}}$表示一對角矩陣，其主對角線的元素為${\hat {s}}_{2}$

平移

平移在圖訊號時域中亦因為沒有好的順序關係，無法被良好的直接定義。

但因一般數位訊號處理的平移運算等價於將訊號與一個單位脈衝訊號摺積，其推廣定義可以利用此性質

$s_{out}=s_{in}*\delta _{n}=VD_{{\hat {s}}_{in}}V^{-1}\delta _{n}=VD_{{\hat {s}}_{in}}u_{n}$，其中$\delta _{n}(k)={\begin{cases}1,&{\text{if }}n=k\\0,&{\text{if }}n\neq k\end{cases}}$

濾波

濾波是讓輸入訊號經過一系統，產生輸出訊號的過程。在時域中的表現形式為

$s_{out}=Hs_{in}$

若$H$是線性非移變系統，存在多項式傳遞函數$h$使得$h=h(S)$，故

$Hs_{in}=h(S)s_{in}=h(V\Lambda V^{-1})s_{in}=Vh(\Lambda )V^{-1}s_{in}=VD_{{\hat {s}}_{H}}V^{-1}s_{in}$

與摺積的定義比較，可知其實可將「對$s_{in}$使用$H$濾波」看作「將$s_{in}$與另一個信號$s_{H}$作摺積」，其中$s_{H}$符合${\hat {s}}_{H}=(h(\lambda _{1}),h(\lambda _{2}),...h(\lambda _{N-1}))^{T}$，

此時稱$s_{H}$為$H$的脈衝響應，${\hat {s}}_{H}$為$H$的頻率響應。

參考

• A. Sandryhaila and Jose M. F. Moura, Discrete Signal Processing on Graphs, [[arxiv:1210.4752|http://arxiv.org/abs/1210.4752 （頁面存檔備份，存於互聯網檔案館）]]
• David I Shuman, Sunil K. Narang, Pascal Frossard, Antonio Ortega, Pierre Vandergheynst, The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains, [[arxiv:1211.0053|http://arxiv.org/abs/1211.0053 （頁面存檔備份，存於互聯網檔案館）]]