基于圖譜域移位的帶限圖信號重構算法

楊 杰 趙 磊 郭文彬,2

1.北京郵電大學 北京 100786 2.通信網信息傳輸與分發技術重點實驗室 石家莊 050000

隨著信息技術的高速發展,各領域中所產生的數據維度正在以前所未有的速度增長,例如社交網絡數據、金融交易數據和城市交通流量數據等.

然而,傳統的數據表征方法無法適用于具有復雜關聯特征的網絡數據集.所以,圖網絡[1]——一種非規則域中用于表征關聯數據的模型應運而生.如何更好地分析這些基于圖網絡表征的數據集,從而更加高效地挖掘數據集的深度信息成為當下研究的熱點問題之一.

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

由于存在圖網絡的拓撲結構復雜多變以及數據維度帶來的計算消耗大的問題,如何利用盡可能少的采樣節點信號和網絡拓撲信息更加高效和完備地表征未采樣節點信號,從而為網絡數據的傳輸和處理提供高效的技術支撐是圖信號處理中的核心問題[17].在圖信號重構的相關研究中,由于帶限圖信號重構問題可作為其他類型圖信號重構問題的源問題進行相關推廣;如何設計高效的帶限圖信號重構算法是一個重要的研究課題,它為設計平滑圖信號重構算法和實際網絡數據重構方法提供了理論基礎.

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

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

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

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

1 基于譜移位的重構算法

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

2 基于殘差譜移位的重構算法

3 分段帶限圖信號重構算法

4 實驗仿真及分析

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

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

圖4 無噪環境下帶限圖信號重構性能對比Fig.4 Comparison of graph band-limited signals reconstruction performances in noiseless environment

表1 無噪情況下基于隨機采樣的 G1 重構效率Table 1 G1 reconstruction efficiency of random sampling in noiseless

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

圖5 含噪環境下帶限圖信號重構性能對比Fig.5 Comparison of graph band-limited signals reconstruction performances in noisy environment

表2 無噪情況下基于隨機采樣的 G2 重構效率Table 2 G2 reconstruction efficiency of random sampling in noiseless

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

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

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

5 結束語

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