楊 杰 趙 磊 郭文彬,2

1.北京郵電大學(xué) 北京 100786 2.通信網(wǎng)信息傳輸與分發(fā)技術(shù)重點實驗室 石家莊 050000

隨著信息技術(shù)的高速發(fā)展,各領(lǐng)域中所產(chǎn)生的數(shù)據(jù)維度正在以前所未有的速度增長,例如社交網(wǎng)絡(luò)數(shù)據(jù)、金融交易數(shù)據(jù)和城市交通流量數(shù)據(jù)等.

然而,傳統(tǒng)的數(shù)據(jù)表征方法無法適用于具有復(fù)雜關(guān)聯(lián)特征的網(wǎng)絡(luò)數(shù)據(jù)集.所以,圖網(wǎng)絡(luò)[1]——一種非規(guī)則域中用于表征關(guān)聯(lián)數(shù)據(jù)的模型應(yīng)運而生.如何更好地分析這些基于圖網(wǎng)絡(luò)表征的數(shù)據(jù)集,從而更加高效地挖掘數(shù)據(jù)集的深度信息成為當(dāng)下研究的熱點問題之一.

近年來,隨著圖信號處理的興起和發(fā)展,圖網(wǎng)絡(luò)中的信號(數(shù)據(jù))分析與處理引起了研究者們的廣泛關(guān)注.圖信號處理是將傳統(tǒng)的信號處理理論衍生至基于圖網(wǎng)絡(luò)表征的非規(guī)則域信號處理理論[2].目前,圖信號處理的理論研究主要包括圖濾波器(組)的設(shè)計[3]、圖信號采樣/恢復(fù)[4]、圖信號壓縮[5]和圖拓?fù)鋵W(xué)習(xí)[6]等.相關(guān)的應(yīng)用研究有傳感網(wǎng)絡(luò)中的異常數(shù)據(jù)檢測[7]及修復(fù)[8],基于圖數(shù)據(jù)的機(jī)器學(xué)習(xí)等[9-10].然而,目前該研究領(lǐng)域中仍然存在著許多亟待探索和解決的理論問題和應(yīng)用瓶頸[11].例如,圖信號處理中尚未出現(xiàn)類似于奈奎斯特采樣定理的統(tǒng)一采樣理論[12].相關(guān)的挑戰(zhàn)還包括圖信號的大規(guī)模分布式計算[13]、異構(gòu)網(wǎng)絡(luò)中的圖信號處理[14]、如何融合多尺度下的圖信號特征而進(jìn)行信號多分辨分析[15],以及如何分析張量圖網(wǎng)絡(luò)中的多層圖數(shù)據(jù)之間的關(guān)聯(lián)性[16]等.隨著圖信號處理的不斷發(fā)展,必將成為有效應(yīng)對數(shù)據(jù)泛濫現(xiàn)象和降低數(shù)據(jù)冗余的重要工具,并為網(wǎng)絡(luò)數(shù)據(jù)的高效處理提供理論支撐.

由于存在圖網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)復(fù)雜多變以及數(shù)據(jù)維度帶來的計算消耗大的問題,如何利用盡可能少的采樣節(jié)點信號和網(wǎng)絡(luò)拓?fù)湫畔⒏痈咝Ш屯陚涞乇碚魑床蓸庸?jié)點信號,從而為網(wǎng)絡(luò)數(shù)據(jù)的傳輸和處理提供高效的技術(shù)支撐是圖信號處理中的核心問題[17].在圖信號重構(gòu)的相關(guān)研究中,由于帶限圖信號重構(gòu)問題可作為其他類型圖信號重構(gòu)問題的源問題進(jìn)行相關(guān)推廣;如何設(shè)計高效的帶限圖信號重構(gòu)算法是一個重要的研究課題,它為設(shè)計平滑圖信號重構(gòu)算法和實際網(wǎng)絡(luò)數(shù)據(jù)重構(gòu)方法提供了理論基礎(chǔ).

基于Papoulis-Gerchberg 信號重構(gòu)算法[18],Narang 等[19]提出一種基于空域迭代圖濾波的信號重構(gòu)方法(Iteration least square reconstruction,ILSR).該方法通過將采樣信號和每次迭代后產(chǎn)生的采樣信號殘差進(jìn)行累加后,再進(jìn)行圖譜域帶限濾波處理,從而達(dá)到重構(gòu)目的.在ILSR 重構(gòu)算法的基礎(chǔ)上,Wang 等[20]提出了基于迭代加權(quán)策略的信號重構(gòu)算法(Iteration weighting reconstruction,IWR)和基于迭代傳播策略的信號重構(gòu)算法(Iteration propagating reconstruction,IPR),兩種算法優(yōu)于ILSR 算法的原因在于對采樣節(jié)點進(jìn)行了殘差濾波處理.在IWR 算法中,Wang 等[20]首先將采樣信號的殘差擴(kuò)大相應(yīng)的權(quán)重,然后進(jìn)行圖濾波處理;而在IPR 算法中,首先是基于預(yù)先劃分好的局部集將采樣節(jié)點的信號殘差傳遞給相鄰的未采樣節(jié)點,然后進(jìn)行圖濾波處理.由于兩種算法在每步迭代中加入了對于采樣信號殘差的處理,增大了未采樣信號在插值過程中的增量,進(jìn)而提高了重構(gòu)的效率和精度.為了進(jìn)一步地提高對于殘差信號的估計精度,Yang 等[21]提出了基于擴(kuò)散算子的迭代重構(gòu)算法(Iteration graph reconstruction based diffusion operator,IGDR).IGDR 算法修正了IWR 和IPR算法中由于采樣信號殘差在局部集內(nèi)均勻傳遞而導(dǎo)致的過平滑現(xiàn)象,在每步迭代中基于局部擴(kuò)散算子和全局?jǐn)U散算子對信號采樣進(jìn)行了聯(lián)合處理,使得迭代濾波得到的未采樣信號為圖帶限濾波信號和殘差擴(kuò)散信號的總和.不同于IWR、IPR 和IGDR 算法聚焦于迭代殘差信號的處理方法,Brugnoli 等[22]同樣在ILSR 算法的基礎(chǔ)上提出了基于最優(yōu)參數(shù)的Papoulis-Gerchberg 信號迭代重構(gòu)算法(Optimal Papoulis-Gerchberg iterative reconstruction,OPGIR),該算法通過在每步迭代中設(shè)置松弛參數(shù)的最優(yōu)解而達(dá)到較高的迭代效率.

不同于基于空域濾波的重構(gòu)算法研究,為了完善圖信號譜域理論框架及提升圖信號的譜域特征分析能力,基于圖傅里葉變換的圖譜域重構(gòu)算法同樣是近年來的研究熱點.

Tseng 等先后提出基于壓縮感知的硬閾值截斷圖譜域重構(gòu)算法[23]和基于圖傅里葉變換的圖譜域重構(gòu)算法[24].在硬閾值截斷圖譜域重構(gòu)算法中,作者首先將圖信號重構(gòu)問題轉(zhuǎn)化為圖譜域中的稀疏優(yōu)化問題,然后采用經(jīng)典壓縮感知理論中的基追蹤算法和正交匹配算法或迭代硬閾值截斷法分別進(jìn)行求解.通過上述方法估計出未采樣圖信號在圖譜域中的頻率分量,最后基于圖傅里葉逆變換將估計的頻率分量轉(zhuǎn)換為空域圖信號.在正交匹配算法的基礎(chǔ)上作者又提出了基于圖傅里葉變換的信號重構(gòu)算法;在正交匹配算法中,完整頻率分量是通過逐步重構(gòu)出每個圖頻率分量值而實現(xiàn)的.而在基于圖傅里葉變換的信號重構(gòu)算法中,作者通過重構(gòu)出小于截止圖頻率內(nèi)的頻率分量值實現(xiàn)信號重構(gòu).該算法實質(zhì)上是將ILSR 算法轉(zhuǎn)化到圖頻域進(jìn)行處理.然而,兩種方法并沒有針對低通帶限圖信號的譜域特性進(jìn)行更深入的分析,只是將空域重構(gòu)算法轉(zhuǎn)化到變換域進(jìn)行.

本文首先基于圖傅里葉變換的分塊矩陣形式和圖帶限信號特性分析得出圖帶限分量的恒等不變性.基于該特性,本文將重構(gòu)問題建模為一個最小二乘模型.本文所提出的重構(gòu)模型是根據(jù)圖高頻部分的恒等關(guān)系,相比于基于圖低頻段相似性的ILSR重構(gòu)模型,更加能夠準(zhǔn)確地表征信號的圖譜域帶限特性,提高了重構(gòu)精度.此外,由于根據(jù)重構(gòu)模型而設(shè)計的迭代算法采用擬牛頓法進(jìn)行求解,在避免海森矩陣求解的同時高效利用了模型的二階梯度信息,相比于ILSR 和O-PGIR 提高了迭代效率.而在基于殘差信號的重構(gòu)算法中,本文根據(jù)殘差信號同樣具備圖帶限分量的恒等不變性,設(shè)計了一種基于殘差譜移位的重構(gòu)算法.相比于IWR/IPR 和IGDR 算法,本文算法具有較好的重構(gòu)性能.此外,由于本文提出的圖帶限分量的恒等不變性不需要考慮帶限頻率所在的頻段,所以針對分段帶限圖信號的重構(gòu)問題同樣適用,并且具有良好的重構(gòu)性能.

1 基于譜移位的重構(gòu)算法

圖1 帶限圖信號Fig.1 Graph band-limited signals

2 基于殘差譜移位的重構(gòu)算法

3 分段帶限圖信號重構(gòu)算法

4 實驗仿真及分析

圖2 分段帶限圖信號Fig.2 Graph sperate band-limited signals

圖3 圖信號采樣Fig.3 Graph signals sampling

圖4 無噪環(huán)境下帶限圖信號重構(gòu)性能對比Fig.4 Comparison of graph band-limited signals reconstruction performances in noiseless environment

表1 無噪情況下基于隨機(jī)采樣的 G1 重構(gòu)效率Table 1 G1 reconstruction efficiency of random sampling in noiseless

為了對比噪聲環(huán)境中的算法的魯棒性,本文在采樣信號中分別加入信噪比為 20 dB 和 40 dB 的隨機(jī)高斯噪聲.信號重構(gòu)性能對比如圖5所示,本文提出的重構(gòu)算法和對比算法的抗噪魯棒性相同,然而BGSR-GFS 和BGSR-GFS-R 的迭代效率更高.無論是本文算法還是對比算法均沒有進(jìn)行噪聲抑制或消除的步驟,導(dǎo)致無法消除噪聲對于重構(gòu)性能的影響.

圖5 含噪環(huán)境下帶限圖信號重構(gòu)性能對比Fig.5 Comparison of graph band-limited signals reconstruction performances in noisy environment

表2 無噪情況下基于隨機(jī)采樣的 G2 重構(gòu)效率Table 2 G2 reconstruction efficiency of random sampling in noiseless

在第3 組仿真中,本文將針對分段帶限圖信號進(jìn)行重構(gòu)性能對比.本文將第1 組仿真實驗中的圖信號加入高頻分量.即隨機(jī)選取Q個連續(xù)的高頻分量后,再通過圖傅里葉逆變換得到分段帶限圖信號(G1和G2的Q值分別為10 和3).為了確保對比試驗的公平性,本文將對比算法中的低通圖濾波器調(diào)整為帶通圖濾波器.

如圖6所示,無論是基于隨機(jī)采樣或貪婪采樣,本文算法都具有良好的重構(gòu)精度和迭代效率.由于ILSR 和O-PGIR 算法都是利用圖信號的低頻分量相似性原則設(shè)計重構(gòu)算法,而沒有考慮到圖信號的高頻段分量的差異性,所以迭代效率十分有限.算法IPR 在ILSR 的基礎(chǔ)上,基于相鄰節(jié)點殘差信號等值傳遞的原則進(jìn)行迭代過程中增量的估計,而算法IGDR 在IPR 的基礎(chǔ)上增加了擴(kuò)散策略,進(jìn)一步提高了迭代效率;兩種基于殘差法的重構(gòu)策略實質(zhì)上都是利用了殘差信號低頻分量之間的相似性,同樣無法實現(xiàn)高效的信號重構(gòu).與上述4 種算法不同的是,由于本文提出的兩種算法同時考慮了圖低頻相似性和圖高頻差異性,通過圖譜域移位策略重構(gòu)分段帶限圖信號,具有較高的重構(gòu)精度和迭代效率.

圖6 分段帶限圖信號重構(gòu)性能對比Fig.6 Comparison of graph separate band-limited signals reconstruction performances

5 結(jié)束語

本文針對帶限圖信號的重構(gòu)問題,提出了基于圖帶限分量恒等特性的重構(gòu)模型.通過將該重構(gòu)模型轉(zhuǎn)化為最小二乘問題,本文提出了兩種基于圖譜域移位的重構(gòu)算法.此外,本文所提出的新算法同樣適用于分段帶限圖信號的重構(gòu)問題.最后,數(shù)值仿真表明,相比于其他重構(gòu)算法,本文算法的重構(gòu)性能更優(yōu).