利用聯合平滑性的時變圖信號重構算法

索秋月 林基明,2 王俊義

1(桂林電子科技大學信息與通信學院 廣西 桂林 541004) 2(西安電子科技大學通信工程學院 陜西 西安 710071)

0 引 言

近年來，在社交網絡、電力網絡、交通運輸網絡、傳感器網絡等領域產生海量數據，這些數據具有復雜的非歐幾里得特性。圖信號處理就是一種處理高維非歐幾里得數據的新工具，它用圖捕獲數據的拓撲結構。圖結構中的頂點對應數據中的每個元素，連接兩兩頂點的邊表示數據元素之間的關聯關系，從而從網絡中獲取的數據對應圖結構上的信號。圖信號處理工具把傳統的信號處理概念擴展到圖上，進而處理和分析不規則高維數據[1-3]。

在各種實際應用中，噪聲污染、數據丟失，以及為了節省能量或方便傳輸進行的數據采樣現象非常普遍，因此，為了保證所獲得數據的真實性，從有噪、有缺失的圖信號觀測值中重構真實的圖信號很有研究意義。從而，圖信號重構算法成為了學者們的一個研究熱點。在圖信號處理領域，隨時間變化的圖信號為時變圖信號。現有的時變圖信號重構算法都是從降低算法的復雜度和提高算法的重構精度兩方面進行創新。為了降低重構算法的計算復雜度，一些分布式重構算法被提出[4-7]。另一方面，為了提升信號重構精度，現有的文獻常常利用數據的相關性。文獻[8]提出一個基于正則化的恢復框架，該框架最小化高通圖濾波器輸出和相對于已知樣本的恢復誤差，并給出了該優化問題的封閉解。該文提供了一種把信號恢復問題描述為優化問題的解決思路。文獻[9]提出一種基于變差最小化的重構算法,將圖信號重構問題轉化為一個優化問題，并用交替方向乘子法得到重構信號，從而提供了一種通用的信號重構問題解決方案。文獻[10]提出一種利用時差信號在圖上的平滑性的時變圖信號重構算法，該算法顯著提高了時變圖信號的重構精度。文獻[11]將用于時變圖信號分析的聯合諧波分析概念提升為一個成熟的時間-頂點信號處理框架，該框架把傳統信號處理技術與圖信號處理新工具聯系了起來，并證明了該框架可以用于提高時變圖信號的重構精度。文獻[12]建立了一種聯合圖域模型，并根據模型中傳感器網絡數據的關聯特性設計了迭代重構算法，提高了重構精度。

受以上研究的啟發，本文提出利用聯合平滑性的時變圖信號重構算法(Joint Smooth Reconstruction of Time-Varying Graph Signals，JSR-TVGS)。在2個公開的真實數據集上分別進行實驗，結果表明：與僅利用時差信號平滑性的批量重構算法[10](Batch Reconstruction of Time-Varying Graph Signals，BR-TVGS)、僅利用聯合變差最小化的重構算法[11](Joint Variation Minimization Reconstruction，JVMR)相比，JSR-TVGS算法重構精度更高。

1 圖信號處理相關知識

在圖信號處理(Graph Signal Processing)[1]中，一個無向、連通、加權圖表示為：G=(V，E，W)，其中：V={v1,v2,…,vN}是圖的N個頂點的集合；E={ei,j}是連接頂點的連邊集合，元素ei,j表示vi和vj有邊相連；W∈RN×N是圖的加權鄰接矩陣,也是對稱矩陣。元素wij是非負的，表示vi和vj邊的權重，定量地表示了圖上頂點信號之間的相似性，兩個頂點無邊相連時wij=0，且wij=0,i=1,2,…,N。假設圖上的時變圖信號是等時間間隔采樣的連續T個時刻的信號，把N個頂點上的時變圖信號表示為X=[x1,x2,…,xT]∈RN×T,式中：xt∈RN,t=1,2,…,T表示在時刻t的圖信號，矩陣X的元素xit表示頂點vi在時刻t的信號值。圖拉普拉斯矩陣定義為：

LG=D-W

(1)

(2)

不同的特征值λi,i=1,2,…,N視為圖譜域的圖頻率,特征值的大小表示圖頻率的大小[14]。

2 利用聯合平滑性的重構算法

2.1 時差信號平滑性

時變圖信號存在兩種相關性：(1) 某一時刻，空間上相鄰的圖信號相似；(2) 某一頂點的圖信號隨著時間變化緩慢。因此，不能忽略時間維度上的相關性。時變圖信號越平滑，則信號之間的變差越小。通過傅里葉變換，可以直觀地了解信號的變化快慢，定量表示信號之間的變差。

圖信號在t時刻的變差可以表示[1]為：

(3)

(4)

進而把時差信號的平滑性定義為：

S2(XDh)=tr((XDh)TLG(XDh))

(5)

時變圖信號的觀測矩陣可以表示為：

Y=J°X+N

(6)

式中：°表示哈達瑪積；N是加性高斯白噪聲；J∈{0,1}N×T是采樣算子，定義為：

(7)

式中：v表示頂點；St表示在時刻被采樣的頂點的集合。

基于時差信號在圖域中的平滑性，文獻[10]提出一種時變圖信號的重構算法(BR-TVGS)，該算法的優化問題表示為：

(8)

式中：η是正則化參數。文獻[10]雖然考慮了時間的影響，但其假設時變圖信號在時間維度是每個時刻圖信號簡單獨立地序列疊加，忽略了信號在時域中的平滑性。

2.2 時變圖信號的聯合變差

由第1節可知圖傅里葉變換(GFT)定義為：GFT{X}=U-1X，矩陣X左乘一個圖傅里葉變換矩陣，相當于矩陣X每列獨立地進行圖傅里葉變換，忽視了信號的時間維度。為了同時獲得時變圖信號在時間域和圖域的頻率分量，文獻[15]和文獻[11]把圖信號處理與傳統信號處理統一起來，定義了圖-時間傅里葉變換：

JFT{X}=U-1XV-1

(9)

S(X)=tr(XTLGX)+tr(XLTXT)

(10)

式中：LT為時域圖拉普拉斯矩陣，LT=VΛTV-1，ΛT(m,m)=2(1-cos(ωm))。S(X)越小，圖信號越平滑。由式(10)可知，時變圖信號的聯合變差是圖域變差與時域變差的和，即時變圖信號的平滑性可在圖域和時域分開討論。

文獻[11]基于聯合諧波分析，提出聯合變差最小化重構算法(JVMR)，其優化問題模型為：

(11)

式中：γ1、γ2是正則化參數。JVMR算法利用了信號在時域中的全局平滑性，但沒有充分利用信號在圖域中的平滑性。

2.3 本文算法簡介

基于時變圖信號的聯合變差可分離的性質，本文利用時變圖信號分別在圖域和時域中的平滑性來重構信號，并把時變圖信號重構問題描述為如式(12)所示的優化問題。

(12)

式中:α、β>0是正則化參數。本文默認存在收集所有頂點觀測數據Y的計算中心，已知圖拉普拉斯矩陣LG和時域圖拉普拉斯矩陣LT且不隨時間變化。根據式(13)的推導：

(13)

(14)

β(LT?IN)z

(15)

1) 對任意的頂點vt∈V,i=1,2,…,N,一定存在一個時刻t∈{1,2,…,T}使Jv,t=1。

2) 有一個基準時刻t0∈{1,2,…,T}，使得對于任一時刻t∈{1,2,…,T}，t≠t0,存在一個頂點vt∈V滿足Jvtt0=Jv,t=1。

+β(LT?IN)]-1Qvec(Y)

(16)

然而，式(16)涉及大小為MN×MN的矩陣的逆的計算，該計算的計算復雜度較高，尤其是當重構一個大規模頂點集的長期跟蹤的數據時，式(16)的計算復雜度更高。因此，本文用快速迭代收縮閾值算法[16-17](Fast Iterative Shrinkage-Thresholding Algorithm，FISTA)求解式(12)。

FISTA求解最小化問題的思想基于梯度下降法，基于梯度下降思想得到迭代計算公式為：

X(k+1)=X(k)-μ▽f(X(k))

(17)

相比梯度下降法優化了每一步迭代起始點X(k)的選擇，進而更快地找到最小值點。

根據式(12)，得到f(X)的梯度如下：

基于上述分析，本文提出利用聯合平滑性的時變圖信號重構算法(JSR-TVGS)。具體步驟如下。

步驟1基于時變圖信號聯合變差概念，得到圖拉普拉斯矩陣LG和時域圖拉普拉斯矩陣LT。

步驟2采樣。使采樣算子J同時滿足文獻[10]定理中的兩個條件，并從真實數據集得到觀測數據Y。

步驟3初始化設置。迭代次數k初始值為1，時差算子Dh；正則化參數α、β；步長μ；S(1)=X(0)=Y；τ1=1；最大迭代次數K；終止迭代閾值ε。

步驟4迭代。

1)X(k)=S(k)-μ▽f(S(k))。

步驟5若k=K或|f(X(k)-f(X(k-1))|/|f(X(k))|<ε則迭代終止，并輸出重構的時變圖信號X(k)；否則令k=k+1，并跳轉到步驟4。

3 實驗與結果分析

在實驗中，選取了2個不同的真實數據集進行重構算法的仿真測試。用圖信號處理工具箱GSPBox[18]構建時變圖信號的圖域模型G=(V,E,W)和聯合域圖模型中的參數LG、LT。為了不失一般性，采用簡單的均勻采樣策略，采樣率為固定值r∈(0,1)。在每個時刻t∈{1,2,…,T}，采樣的頂點數為所有頂點數N與采樣率r的積：Ns=N×r，每個時刻從N個頂點中隨機地采樣Ns個頂點，對應采樣矩陣J每列的非零元素。每個時刻的采樣互相獨立。設置噪聲N的標準差σ=0.01。本文實驗仿真部分使用凸優化工具箱UNLocBoX[19]中的FISTA得到凸優化問題的解，其中：步長μ采用工具箱的默認值1；最大迭代次數K=3×107；終止迭代閾值ε=10-5。用窮舉搜索法選擇最優的正則化參數α和β，本文實驗中，正則化參數α、β的取值集合為{0.01,0.02,0.05,0.1,0.2,0.5,1}。在相同的實驗環境下，分別將本文提出的JSR-TVGS算法和BR-TVGS算法、JVMR算法應用到同一真實數據集，以便對比分析。

在本文實驗中，用平均絕對誤差(Mean Absolute Error,MAE)評價算法性能，其中平均絕對誤差的計算方法為：

(18)

式中：X(k)是重構的信號；X是真實信號；Nx是信號長度。MAE越小，說明真實信號與重構信號越接近，重構誤差越小，重構算法的重構精度越高。為了使實驗結果更可信，對于每個采樣率r，本文進行了100次獨立隨機采樣實驗，最終對比的重構誤差是所有100次實驗的MAE的平均值。

3.1 加利福尼亞州每日平均PM2.5濃度數據

美國環境保護局公布的加利福尼亞州每日平均PM2.5濃度數據集[20]是從2015年1月1日開始的200天內在93個觀測點收集的，每天收集每個觀測點的數據一次。數據大小為93×100。數據的圖域模型如圖1所示。可以看出圖域模型中頂點的空間分布及頂點之間的關聯關系與實際的情況相符，圖信號處理工具適用于該數據的處理。

圖1 加利福尼亞洲每日平均PM2.5濃度圖網絡

在該真實數據上的實驗仿真結果如圖2所示。可以看出：(1) 存在高斯白噪聲的情況下，對于不同的采樣率，利用JSR-TVGS算法都能重構出誤差較小的PM2.5濃度數據。這說明本文算法對于時變圖信號的重構是有效的。(2) 隨著采樣率的提高，本文提出的JSR-TVGS算法的重構誤差降低。這是因為用于重構的觀測信號信息越充分，重構誤差越小。這與實際情況相符，說明了JSR-TVGS算法的合理性。(3) 在采樣率相同的情況下，與其他兩種算法相比，JSR-TVGS算法的平均絕對誤差更小，重構精度更高。

圖2 每日平均PM2.5濃度數據在不同采樣率下 的平均重構誤差

3.2 溫度傳感器網絡數據

溫度傳感器網絡數據[21]是從實驗室中分布的54個傳感器收集的2004年2月28日09:26到11:06間的數據，傳感器每隔30 s采集一次數據。除掉一個故障的傳感器，所選數據的大小為53×200。溫度傳感器網絡數據圖域模型如圖3所示。可以看出圖域模型中頂點的空間分布及頂點之間的關聯關系與實際的情況相符，圖信號處理工具適用于該數據的處理。

圖3 溫度傳感器網絡數據圖域模型

在該真實數據上的實驗仿真結果如圖4所示。可以看出：(1) 存在高斯白噪聲的情況下，對于不同的采樣率，利用JSR-TVGS算法都能重構出誤差較小的溫度傳感器網絡數據。這說明本文算法對于時變圖信號的重構是有效的。(2) 隨著采樣率的提高，JSR-TVGS算法的重構誤差降低。雖然采樣率大于0.5之后，這種現象不太明顯，但誤差基本保持較小。這是因為用于重構的觀測信號信息越充分，重構誤差越小。采樣率為0.5時，重構溫度傳感器網絡數據的觀測信息已足夠充分，再增加采樣率不會明顯降低重構誤差。溫度傳感器網絡數據較平滑，不需要過高的采樣率就能重構出理想的信號。這些與實際情況相符，說明了JSR-TVGS算法的合理性。(3) 在采樣率相同的情況下，與其他兩種算法相比，JSR-TVGS算法的平均絕對誤差更小，重構精度更高。

圖4 溫度傳感器網絡數據在不同采樣率下的平均重構誤差

4 結 語

本文基于時差信號在圖域中比信號本身更平滑的特點以及時變圖信號在時域中的平滑性，提出一種利用聯合平滑性的時變圖信號重構算法。該算法把時變圖信號重構問題轉化為凸優化問題，并用快速迭代收縮閾值算法求解，得到重構的時變圖信號。當我們重構一個大規模頂點集的長期跟蹤的數據時，使用本文算法重構信號是快速有效的。實驗結果表明了本文算法重構時變圖信號的有效性及合理性，且與相關的時變圖信號重構算法相比，本文算法重構精度更高。未來的研究重點是將本文算法應用到具體場景中，進一步提高重構精度。