圖訊號

圖訊號（Graph Signal）的構造方法為在一張圖的頂點上賦予值，故在討論一個圖訊號時，必須先有一張圖。

圖訊號與離散時間訊號相對應，分別是圖訊號處理和數位訊號處理的處理對象。

圖訊號的指標域為圖的頂點集合。與離散時間訊號不同，因為圖的性質，指標不一定有前後的方向性，故一般而言不能將圖訊號的指標域比擬作時間。然而，為了與數位訊號處理中的概念相呼應，有時還是會將其稱作時域。

與離散時間訊號的關係
所有有限維的離散時間訊號皆可用圖訊號來表示，例如

• 一維的離散時間訊號可看作一個圖訊號，其中使用的圖為一條道路。
• 二維的離散時間訊號可看作一個圖訊號，其中使用的圖為一柵格。

更高維離散時間訊號亦可用高維柵格來表示。

圖訊號處理
圖訊號處理（英語：Graph Signal Process, GSP），是與數位訊號處理類似，但處理對象為圖訊號的一個訊號處理的分支。

圖訊號處理的目的為測量及分析圖訊號，發展初期，數學家與工程師從圖論傅立葉轉換開始，仿照數位訊號處理中現有的處理工具，試圖做出對應的圖訊號處理版本。然而當時域從普通的整數改變成圖，因諸多的不確定性，並無法將所有可使用的工具完整地推廣至圖訊號處理版本（見下例）。

圖訊號處理的數學理論基礎為譜圖理論（英語：Spectral graph theory）。

圖訊號處理的域
圖訊號處理領域和數位訊號處理領域相似，工程師在時域、頻域、小波域中研究圖訊號，但這些域的形象與數位訊號處理中使用到的皆有些微差別，例如：

• 時域：圖訊號的時域為一圖的頂點集。在視覺化圖訊號時，最容易的方法是直接視覺化此圖。但在要作圖訊號處理的數學運算時，會先將圖的頂點編號，再依序排列訊號值，故運算式中的圖訊號往往還是以向量的方式出現。
• 頻域：圖訊號的頻域與一般數位訊號相同的是其指標域皆為頻率；不同的是圖訊號的頻域不一定由間隔相同的一連串頻率值所構成，故無法直接對應到有限的整數集合。

時域與頻域的對應關係由圖論傅立葉轉換定義，同一張圖下，不同的圖論傅立葉轉換定義出的頻域未必相同。

圖取樣與重建
圖取樣與重建（Graph Signal Sampling and Reconstruction）旨在從圖結構數據中獲取有限樣本並重構原始圖訊號。傳統的圖訊號取樣（decimation）僅採集部分頂點的訊號值，而本文提出的【局部測量】（local measurement）概念則為取樣提供了一種廣義化方法，允許在一個「無中心局部集」（centerless local set）中，通過線性組合多個頂點的訊號來獲取測量值，從而提高重構的魯棒性與精確度。

局部測量
在圖訊號處理中，一個圖訊號定義為從頂點集 V 映射到實數集的函數，即
f: V \to \mathbb{R}，表示在每個頂點上所觀測到或定義的訊號值。

設圖 G(V,E) 的頂點集 V 被劃分為互不重疊的子集
\{N_i\}_{i \in I}（即無中心局部集），每個局部集 N_i 上定義一個局部權重函數
\phi_i: V \to \mathbb{R}，滿足

\phi_i(v)=\begin{cases}
\geq 0, & \text{若 } v \in N_i,\\[1mm]
0, & \text{若 } v \notin N_i,
\end{cases}
\quad \text{且} \quad \sum_{v\in N_i}\phi_i(v)=1.

則圖訊號 f: V \to \mathbb{R} 的局部測量定義為

f_{\phi_i} = \langle f, \phi_i \rangle = \sum_{v \in N_i} f(v) \phi_i(v).

可見，當僅選取單一頂點（即某頂點 u 的權重取值 1，其餘頂點權重均為 0）時，局部測量退化為傳統取樣；而一般情況下，局部測量則融合了局部集內多個頂點的資訊。

迭代局部測量重構（ILMR）
基於上述局部測量，提出了一種迭代型重構演算法——迭代局部測量重構（Iterative Local Measurement Reconstruction, ILMR）。令 PW_\omega(G) 表示圖 G 上帶限於頻率 \omega 的子空間（即 Paley–Wiener 空間），並設 P_\omega(\cdot) 為將信號投影到 PW_\omega(G) 的投影算子。定義對於每個局部集 N_i 的指示函數

\delta_{N_i}(v)=
\begin{cases}
1, & v \in N_i,\\[1mm]
0, & v \notin N_i.
\end{cases}

則 ILMR 的初始化與迭代更新公式分別為

f^{(0)} = P_\omega\Bigl(\sum_{i\in I} f_{\phi_i} \, \delta_{N_i}\Bigr),

f^{(k+1)} = f^{(k)} + P_\omega\Bigl(\sum_{i\in I} \Bigl(f_{\phi_i} - \langle f^{(k)},\phi_i\rangle\Bigr) \, \delta_{N_i}\Bigr).

證明表明：若原始圖訊號 f 屬於 PW_\omega(G) 且滿足某些條件（例如 \omega ，其中 C_{\max} 與局部集的結構有關），則 ILMR 能以指數速率收斂並準確重構 f ；此外，在雜訊存在的情況下，對局部權重的優化可使重構誤差最小化。

優勢與應用
該局部測量取樣與重構方案對於具有聚類結構或局部關聯性的應用（如感測網絡、社交網絡等）特別適用，因為在這類場景中，單一頂點的訊號可能因雜訊而不穩定，而局部測量能通過融合多點資訊提高信號的魯棒性。此外，ILMR 演算法可通過局部化實現近似運算，適合分佈式處理環境。

圖信號濾波
圖信號濾波（Graph Signal Filtering）指在圖訊號的頻域上設計與應用濾波器，以調整或強化圖訊號中的某些頻率成分。透過圖傅立葉轉換，圖訊號的頻譜反映了信號在圖結構中不同「頻率」成分的能量分佈。利用多項式逼近方法（例如切比雪夫多項式逼近），可設計出圖濾波器，其通式通常定義為

h(S)=\sum_{k=0}^{K} h_k S^k,

其中 S 為圖的移位算子（例如圖拉普拉斯矩陣或其正規化形式），而 h_k 為濾波器係數。此方法可用於去除雜訊、平滑訊號或提取重要特徵。此外，最新研究亦提出統一的代數濾波器設計框架，可將傳統數位濾波技術推廣至圖結構數據。

相關理論工具
現階段圖訊號處理的理論工具皆與數位訊號處理有對應關係：

• 圖位移（Graph-Shift）（對應一般訊號的單位移動）
• 線性非移變系統（Linear-Shift-invariant-system）（對應線性非時變系統）
• 圖論Z轉換（對應Z轉換）
• 圖論傅立葉轉換（對應離散傅立葉轉換）
• 圖論小波轉換（對應小波轉換）
• 流形取樣定理（Sampling theorem on manifold）
• 圖粗糙化（graph coarsening）

參見
*圖論
*離散時間訊號
*數位訊號處理
*

*

*

參考資料