圖訊號

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

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

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

 與離散時間訊號的關係 
所有有限維的離散時間訊號皆可用圖訊號來表示，例如
 一維的離散時間訊號可看作一個圖訊號，其中使用的圖為一條道路。
 二維的離散時間訊號可看作一個圖訊號，其中使用的圖為一柵格。
更高維離散時間訊號亦可用高維柵格來表示。

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

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

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

 圖訊號處理的域 
圖訊號處理領域和數位訊號處理領域相似，工程師在時域、頻域、小波域中研究圖訊號，但這些域的形象與數位訊號處理中使用到的皆有些微差別，例如：
 時域：圖訊號的時域為一圖的頂點集。在視覺化圖訊號時，最容易的方法是直接視覺化此圖。但在要作圖訊號處理的數學運算時，會先將圖的頂點編號，再依序排列訊號值，故運算式中的圖訊號往往還是以向量的方式出現。
 頻域：圖訊號的頻域與一般數位訊號相同的是其指標域皆為頻率；不同的是圖訊號的頻域不一定由間隔相同的一連串頻率值所構成，故無法直接對應到有限的整數集合。
時域與頻域的對應關係由圖論傅立葉轉換定義，同一張圖下，不同的圖論傅立葉轉換定義出的頻域未必相同。

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

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

設圖  的頂點集  被劃分為互不重疊的子集  
（即無中心局部集），每個局部集  上定義一個局部權重函數  
，滿足

則圖訊號  的局部測量定義為

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

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

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

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

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

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

其中  為圖的移位算子（例如圖拉普拉斯矩陣或其正規化形式），而  為濾波器係數。此方法可用於去除雜訊、平滑訊號或提取重要特徵Ortega, A., Frossard, P., Kovacevic, J., Moura, J. M. F. & Vandergheynst, P. (2018). "Graph Signal Processing: Overview, Challenges, and Applications". Proceedings of the IEEE, 106(5), 808–828.Hammond, D. K., Vandergheynst, P. & Gribonval, R. (2011). "Wavelets on graphs via spectral graph theory". Applied and Computational Harmonic Analysis, 30(2), 129–150.。此外，最新研究亦提出統一的代數濾波器設計框架，可將傳統數位濾波技術推廣至圖結構數據Graph Signal Processing: A Unified Algebraic Approach, arXiv:2303.12211, 2023.。

 相關理論工具 
現階段圖訊號處理的理論工具皆與數位訊號處理有對應關係：
 圖位移（Graph-Shift）（對應一般訊號的單位移動）
 線性非移變系統（Linear-Shift-invariant-system）（對應線性非時變系統）
 圖論Z轉換（對應Z轉換）
 圖論傅立葉轉換（對應離散傅立葉轉換）
 圖論小波轉換（對應小波轉換）
 流形取樣定理（Sampling theorem on manifold）
 圖粗糙化（graph coarsening）

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






參考資料

Category:信号处理