查看“︁線性非移變系統理論”︁的源代码


{{orphan|time=2016-06-30T05:43:41+00:00}}
'''線性非移變系統理論'''建立在[[圖訊號處理]]中對'''線性非移變系統'''的定義上，致力於承襲[[線性非時變系統|線性非時變系統理論]]在操作上的便利性。

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

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

比較被使用的圖位移有：'''連接矩陣A'''、'''拉普拉斯矩陣L'''、'''正規化拉普拉斯矩陣L<sub>N</sub>'''。

== 線性非移變系統<ref>{{Cite journal|title=Discrete Signal Processing on Graphs|url=http://arxiv.org/abs/1210.4752|last=Sandryhaila|first=Aliaksei|last2=Moura|first2=Jose M. F.|journal=IEEE Transactions on Signal Processing|issue=7|doi=10.1109/TSP.2013.2238935|volume=61|pages=1644–1656|issn=1053-587X|access-date=2016-06-30|archive-date=2018-12-12|archive-url=https://web.archive.org/web/20181212144124/http://arxiv.org/abs/1210.4752}}</ref> ==
'''線性非移變系統'''是[[圖訊號處理]]中，有最簡單結構的系統。其性質可最大限度地和[[數位訊號處理]]中的[[線性非時變系統]]對照，並發展出與之類似的運算，達到想要的訊號處理效果。

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

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

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

== 基本運算的推廣形式<ref>{{Cite journal|title=The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains|url=http://arxiv.org/abs/1211.0053|last=Shuman|first=David I.|last2=Narang|first2=Sunil K.|journal=IEEE Signal Processing Magazine|issue=3|doi=10.1109/MSP.2012.2235192|volume=30|pages=83–98|issn=1053-5888|last3=Frossard|first3=Pascal|last4=Ortega|first4=Antonio|last5=Vandergheynst|first5=Pierre|access-date=2016-06-30|archive-date=2020-01-11|archive-url=https://web.archive.org/web/20200111080302/https://arxiv.org/abs/1211.0053}}</ref> ==

=== 圖論傅立葉轉換 ===
詳見[[圖論傅立葉轉換]]。

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

: <math>\hat{s}_{out}(\lambda_k)=\hat{s}_1(\lambda_k)\hat{s}_2(\lambda_k)</math>

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

: <math>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)</math>

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

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

: <math>s_{out}=VD_{\hat{s}_2}V^{-1}s_1</math>

其中<math>V^{-1}</math>為圖論傅立葉轉換矩陣，<math>V</math>即為逆傅立葉轉換矩陣，<math>D_{\hat{s}_2}</math>表示一[[對角矩陣]]，其[[主對角線]]的元素為<math>\hat{s}_2</math>

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

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

: <math>s_{out}=s_{in}*\delta_n=VD_{\hat{s}_{in}}V^{-1}\delta_n=VD_{\hat{s}_{in}}u_n</math>，其中<math>\delta_n(k) = \begin{cases} 1, & \text{if }n=k \\ 0, & \text{if }n\neq k \end{cases}</math>

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

: <math>s_{out}=Hs_{in}</math>

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

: <math>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}</math>

與摺積的定義比較，可知其實可將「對<math>s_{in}</math>使用<math>H</math>濾波」看作「將<math>s_{in}</math>與另一個信號<math>s_H</math>作摺積」，其中<math>s_H</math>符合<math>\hat{s}_H=(h(\lambda_1),h(\lambda_2),...h(\lambda_{N-1}))^T</math>，

此時稱<math>s_H</math>為<math>H</math>的'''脈衝響應，'''<math>\hat{s}_H</math>'''為'''<math>H</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 }}]]
* '''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 {{Wayback|url=http://arxiv.org/abs/1211.0053 |date=20200111080302 }}]]

[[Category:数字信号处理]]