索秋月 林基明,2 王俊義

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

0 引 言

近年來，在社交網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、交通運輸網(wǎng)絡(luò)、傳感器網(wǎng)絡(luò)等領(lǐng)域產(chǎn)生海量數(shù)據(jù)，這些數(shù)據(jù)具有復(fù)雜的非歐幾里得特性。圖信號處理就是一種處理高維非歐幾里得數(shù)據(jù)的新工具，它用圖捕獲數(shù)據(jù)的拓?fù)浣Y(jié)構(gòu)。圖結(jié)構(gòu)中的頂點對應(yīng)數(shù)據(jù)中的每個元素，連接兩兩頂點的邊表示數(shù)據(jù)元素之間的關(guān)聯(lián)關(guān)系，從而從網(wǎng)絡(luò)中獲取的數(shù)據(jù)對應(yīng)圖結(jié)構(gòu)上的信號。圖信號處理工具把傳統(tǒng)的信號處理概念擴展到圖上，進而處理和分析不規(guī)則高維數(shù)據(jù)[1-3]。

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

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

1 圖信號處理相關(guān)知識

在圖信號處理(Graph Signal Processing)[1]中，一個無向、連通、加權(quán)圖表示為：G=(V，E，W)，其中：V={v1,v2,…,vN}是圖的N個頂點的集合；E={ei,j}是連接頂點的連邊集合，元素ei,j表示vi和vj有邊相連；W∈RN×N是圖的加權(quán)鄰接矩陣,也是對稱矩陣。元素wij是非負(fù)的，表示vi和vj邊的權(quán)重，定量地表示了圖上頂點信號之間的相似性，兩個頂點無邊相連時wij=0，且wij=0,i=1,2,…,N。假設(shè)圖上的時變圖信號是等時間間隔采樣的連續(xù)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 利用聯(lián)合平滑性的重構(gòu)算法

2.1 時差信號平滑性

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

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

(3)

(4)

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

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

(5)

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

Y=J°X+N

(6)

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

(7)

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

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

(8)

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

2.2 時變圖信號的聯(lián)合變差

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

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)可知，時變圖信號的聯(lián)合變差是圖域變差與時域變差的和，即時變圖信號的平滑性可在圖域和時域分開討論。

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

(11)

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

2.3 本文算法簡介

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

(12)

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

(13)

(14)

β(LT?IN)z

(15)

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

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

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

(16)

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

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

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

(17)

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

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

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

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

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

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

步驟4迭代。

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

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

3 實驗與結(jié)果分析

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

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

(18)

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

3.1 加利福尼亞州每日平均PM2.5濃度數(shù)據(jù)

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

圖1 加利福尼亞洲每日平均PM2.5濃度圖網(wǎng)絡(luò)

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

圖2 每日平均PM2.5濃度數(shù)據(jù)在不同采樣率下 的平均重構(gòu)誤差

3.2 溫度傳感器網(wǎng)絡(luò)數(shù)據(jù)

溫度傳感器網(wǎng)絡(luò)數(shù)據(jù)[21]是從實驗室中分布的54個傳感器收集的2004年2月28日09:26到11:06間的數(shù)據(jù)，傳感器每隔30 s采集一次數(shù)據(jù)。除掉一個故障的傳感器，所選數(shù)據(jù)的大小為53×200。溫度傳感器網(wǎng)絡(luò)數(shù)據(jù)圖域模型如圖3所示?？梢钥闯鰣D域模型中頂點的空間分布及頂點之間的關(guān)聯(lián)關(guān)系與實際的情況相符，圖信號處理工具適用于該數(shù)據(jù)的處理。

圖3 溫度傳感器網(wǎng)絡(luò)數(shù)據(jù)圖域模型

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

圖4 溫度傳感器網(wǎng)絡(luò)數(shù)據(jù)在不同采樣率下的平均重構(gòu)誤差

4 結(jié) 語

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