索秋月 林基明,2 王俊義

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

0 引 言

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

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

受以上研究的啟發(fā)，本文提出利用聯(lián)合平滑性的時(shí)變圖信號(hào)重構(gòu)算法(Joint Smooth Reconstruction of Time-Varying Graph Signals，JSR-TVGS)。在2個(gè)公開的真實(shí)數(shù)據(jù)集上分別進(jìn)行實(shí)驗(yàn)，結(jié)果表明：與僅利用時(shí)差信號(hào)平滑性的批量重構(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 圖信號(hào)處理相關(guān)知識(shí)

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

LG=D-W

(1)

(2)

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

2 利用聯(lián)合平滑性的重構(gòu)算法

2.1 時(shí)差信號(hào)平滑性

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

圖信號(hào)在t時(shí)刻的變差可以表示[1]為：

(3)

(4)

進(jìn)而把時(shí)差信號(hào)的平滑性定義為：

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

(5)

時(shí)變圖信號(hào)的觀測(cè)矩陣可以表示為：

Y=J°X+N

(6)

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

(7)

式中：v表示頂點(diǎn)；St表示在時(shí)刻被采樣的頂點(diǎn)的集合。

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

(8)

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

2.2 時(shí)變圖信號(hào)的聯(lián)合變差

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

JFT{X}=U-1XV-1

(9)

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

(10)

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

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

(11)

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

2.3 本文算法簡(jiǎn)介

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

(12)

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

(13)

(14)

β(LT?IN)z

(15)

1) 對(duì)任意的頂點(diǎn)vt∈V,i=1,2,…,N,一定存在一個(gè)時(shí)刻t∈{1,2,…,T}使Jv,t=1。

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

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

(16)

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

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

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

(17)

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

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

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

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

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

步驟3初始化設(shè)置。迭代次數(shù)k初始值為1，時(shí)差算子Dh；正則化參數(shù)α、β；步長(zhǎng)μ；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)的時(shí)變圖信號(hào)X(k)；否則令k=k+1，并跳轉(zhuǎn)到步驟4。

3 實(shí)驗(yàn)與結(jié)果分析

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

在本文實(shí)驗(yàn)中，用平均絕對(duì)誤差(Mean Absolute Error,MAE)評(píng)價(jià)算法性能，其中平均絕對(duì)誤差的計(jì)算方法為：

(18)

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語

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