楊立山 游康勇 郭文彬

?

基于擴散算子的帶限圖信號加權(quán)重建策略

楊立山 游康勇 郭文彬*

(北京郵電大學(xué)信息與通信工程學(xué)院 北京 100876)

圖信號處理技術(shù)將經(jīng)典信號處理的概念和算法延展到圖結(jié)構(gòu)信號的處理領(lǐng)域。對于帶限圖信號，可以通過分析信號之間的關(guān)聯(lián)性，重建出未采樣的信號。該文分析了未采樣信號的構(gòu)成架構(gòu)，提出一個基于擴散算子的未采樣信號迭代重建算法。在每次迭代過程中，將已采樣信號的重建殘差擴散至所有未采樣的信號節(jié)點，并進一步通過初步估計結(jié)果與重建殘差的加權(quán)處理，提升算法的收斂速度。采用合成數(shù)據(jù)和真實數(shù)據(jù)進行仿真驗證，實驗結(jié)果顯示所提出的算法具有低重建誤差和快速收斂的特點。

帶限圖信號處理；圖信號擴散算子；下采樣與重建

1 引言

近些年來，隨著傳感器技術(shù)的發(fā)展與工業(yè)信息化革命，在氣象預(yù)測、智能交通等監(jiān)控網(wǎng)絡(luò)內(nèi)部署了大量傳感器設(shè)備。由于傳感器設(shè)備空間分布的不規(guī)則性，其所采集的大規(guī)模數(shù)據(jù)也呈現(xiàn)空間分布的不規(guī)則性，從而限制了PCA, SVD等經(jīng)典規(guī)則域算法的應(yīng)用。因此，面對不規(guī)則域下的數(shù)據(jù)處理問題，需要新的算法、思維和處理模式，促進圖信號處理技術(shù)的快速發(fā)展[1,2]。

圖信號處理技術(shù)中大規(guī)模數(shù)據(jù)之間的關(guān)系被映射為2維平面的圖結(jié)構(gòu)，圖中的節(jié)點代表單個數(shù)據(jù)元素，節(jié)點之間的連接邊表示數(shù)據(jù)元素之間的關(guān)聯(lián)關(guān)系，所有節(jié)點的信號總稱為圖信號。圖信號可以理解為一個具有空間關(guān)聯(lián)關(guān)系的矢量信號，由于信號間的關(guān)系復(fù)雜并且量級龐大，利用小規(guī)模信號集表征原始信號是非常必要的。圖信號采樣與重建的實質(zhì)從圖信號節(jié)點集合中選取合適的部分節(jié)點，利用部分節(jié)點的數(shù)據(jù)，根據(jù)圖拓撲結(jié)構(gòu)以及圖信號的特點，實現(xiàn)對原始數(shù)據(jù)的表征與恢復(fù)。目前關(guān)于圖信號采樣與重建問題的研究有以下幾個方面。文獻[3]分析和利用圖結(jié)構(gòu)的鄰接矩陣，建立了基于優(yōu)化理論的采樣與非迭代重建理論，給出了能夠?qū)崿F(xiàn)無失真重建的條件。文獻[4]采用數(shù)據(jù)匯聚的思想，將圖結(jié)構(gòu)中的節(jié)點通過圖鄰接矩陣匯聚至單個節(jié)點，從而實現(xiàn)對圖結(jié)構(gòu)的采樣。與上述兩個方面不同，本文重點研究基于圖結(jié)構(gòu)的拉普拉斯矩陣以及凸集映射的采樣信號迭代重建策略。Persenson[5]建立了基于Paley-Wiener函數(shù)的圖信號采樣理論基礎(chǔ)，提出了采樣信號唯一集的概念，給出了信號無失真重建的充分條件。關(guān)于采樣圖信號的重建問題，現(xiàn)有重建算法的核心思想是將經(jīng)典信號處理中的Papoulis-Gerchberg算法[6,7]引入到不規(guī)則域，采用凸集映射的思想迭代重建信號。文獻[8,9]提出了一個最小均方迭代重建算法(Iterative Least Square Reconstruction, ILSR)，將已采樣的圖信號交替投影至頂點域下采樣子空間和圖譜域低通濾波子空間，尋找能夠同時滿足兩個空間限制條件的信號。Wang等人[10,11]提出了局部集的概念及其劃分方法，利用局部集的劃分選取合適節(jié)點構(gòu)成下采樣集，并在此概念的基礎(chǔ)上提出了兩個迭代重建算法(Iterative Propagating Reconstruction, IPR和Iterative Weighting Reconstruction, IWR)。這兩個算法設(shè)定的前提是將圖拓撲結(jié)構(gòu)劃分成若干個互不相連的子集，單個子集稱之為局部集。與ILSR相比，IPR最主要的特點是建立了采樣信號重建殘差的傳播機制。在每次迭代重建過程中，重建殘差從已采樣的節(jié)點傳播到位于同一局部集中的未采樣節(jié)點，然后將組合后的圖信號投影至圖譜域低通濾波子空間。得益于采樣信號重建殘差的傳播，IPR能夠得到比ILSR更快的重建收斂速度。但是，IPR將采樣節(jié)點的重建殘差直接賦予同一局部集合內(nèi)的非采樣節(jié)點，不僅忽略了局部集合外的節(jié)點對局部集合內(nèi)節(jié)點影響，而且無法反映真實圖信號重建殘差之間的差異性，從而影響重建收斂速度。另外，現(xiàn)階段的研究缺少未采樣信號構(gòu)成要素的分析。

本文針對從采樣信號中重建原始帶限圖信號的問題，充分利用帶限圖信號的平滑特性，構(gòu)建了恢復(fù)未采樣信號的分析框架，從均值與偏置的角度建立了采樣信號重建殘差的擴散模型，定義了局部均值和全局偏置擴散算子的概念，并在此基礎(chǔ)上提出了基于擴散算子的迭代重建算法。建立了采樣信號與未采樣信號之間的關(guān)聯(lián)關(guān)系，利用局部均值與全局偏置的協(xié)同處理機制消除了未采樣信號的重建殘差在局部區(qū)域內(nèi)的過度一致化，并進一步通過初步估計結(jié)果與重建誤差的加權(quán)處理，加速信號重建的收斂速度。仿真結(jié)果顯示，所提算法具有較低的迭代重建誤差和快速的重建收斂速度。

2 圖信號處理相關(guān)工作

圖1 明尼蘇達州路網(wǎng)圖

2.1 帶限圖信號的下采樣方法

2.2 帶限圖信號的重建方法

ILSR的迭代重建過程可表示為

文獻[10]提出了局部傳播算子的概念以及局部集的劃分方法，其給出的局部傳播重建算法(IPR)也是基于迭代凸集投影來重建圖信號。與ILSR的重建殘差處理機制不同，在每次迭代重建過程中，IPR將局部集內(nèi)采樣節(jié)點的重建殘差傳播至局部集內(nèi)的未采樣節(jié)點，然后再將合成的信號映射到圖譜域低通濾波子空間，其迭代重建過程可表示為

3 基于擴散算子的重建策略

本節(jié)建立了未采樣信號的分析架構(gòu)，定義了局部均值擴散算子和全局偏置算子的概念，構(gòu)建了采樣信號的重建殘差局部擴散與全局擴散策略，提出了基于擴散算子的加權(quán)重建算法。

3.1 重建殘差的擴散機制框架

采樣信號重建問題的實質(zhì)是依據(jù)圖拓撲結(jié)構(gòu)建立已知的采樣圖信號與待定的未采樣圖信號之間的關(guān)聯(lián)關(guān)系。鑒于原始信號與重建信號都具有圖譜域帶限的特性，可知重建殘差同樣呈現(xiàn)帶限的特點，也即，與重建殘差相關(guān)聯(lián)的節(jié)點之間的差異性較小。那么，可以利用這個關(guān)鍵特性，依據(jù)已知的采樣節(jié)點的重建殘差去估計未采樣節(jié)點的重建殘差，這也是本文研究的最主要動機。首先，依據(jù)未采樣節(jié)點圖信號各分量構(gòu)成方式的不同，將其分解為

3.2 局部均值擴散算子

引入局部均值擴散算子的目的是實現(xiàn)采樣節(jié)點重建殘差的局部擴散，將采樣節(jié)點的重建殘差視為局部區(qū)域內(nèi)的均值，其實質(zhì)是依托帶限圖信號的平滑性，充分利用節(jié)點之間差異化較小的特性，為未采樣節(jié)點重建殘差的估計提供有效的基礎(chǔ)。

3.3 全局偏置擴散算子

可以從兩個角度理解全局偏置擴散過程，從采樣節(jié)點的角度來看，單個采樣節(jié)點的重建殘差分量以某種方式擴散至所有未采樣節(jié)點；從未采樣節(jié)點的角度來看，單個未采樣節(jié)點的全局偏置部分則是所有采樣節(jié)點的重建殘差分量擴散到該節(jié)點上的重建殘差分量之和。

3.4 擴散算子以及加權(quán)重建算法

上述定義中，擴散算子由局部均值擴散算子和全局偏置擴散算子構(gòu)成，擴散算子將采樣信號的重建殘差在圖拓撲結(jié)構(gòu)內(nèi)擴散，其中局部均值擴散算子將采樣信號的重建殘差擴散至與該節(jié)點局部區(qū)域內(nèi)的未采樣節(jié)點，全局偏置擴散算子則將采樣信號的重建殘差擴散至所有未采樣節(jié)點?；谏鲜鰯U散過程分析，根據(jù)凸集映射的思想，本文提出基于擴散算子的圖信號迭代重建算法(Iterative Graph diffusion operator based Weighted Signal Reconstruction, IGSR-W)。首先將初始的采樣信號投影至圖譜域低通濾波子空間，獲取已知采樣節(jié)點的重建殘差，完成重建算法的初始過程。在每次迭代過程中，利用擴散算子將采樣節(jié)點的重建殘差擴散至所有未采樣節(jié)點，然后將擴散后的信號投影至圖譜域低通濾波子空間，賦予重建信號圖譜域帶限特性，使其與原始信號的特性相匹配，完成重建信號的第1步估計；而后進一步利用局部均值與全局偏置擴散部分，并與第1步估計的重建信號進行加權(quán)處理，最后將加權(quán)后的信號投影至圖譜域低通濾波子空間，從而完成迭代過程中重建信號的估計。上述重建過程可歸納為

4 仿真結(jié)果

本次仿真采用美國明尼蘇達州路網(wǎng)圖[11]作為圖結(jié)構(gòu)，其節(jié)點表示道路交叉口，邊表示交叉口之間的道路，如圖1所示，其節(jié)點數(shù)目為2642。該路網(wǎng)圖主要用于驗證本文提出的IGSR-W算法與現(xiàn)有算法的重建性能，對比分析所有算法在不同圖譜域截止頻率上的重建誤差性能，并采用3種典型的圖結(jié)構(gòu)對比分析所有算法的重建效果，驗證所提出算法的魯棒性和適用性。另外，為了對比驗證加權(quán)處理的性能，在以下仿真實驗中，采用IGSR(Iterative Graph diffusion operator based Signal Reconstruction)表示未進行加權(quán)處理的重建方式，即僅利用式(16)中的過程。由于IPR需要以局部分割作為基礎(chǔ)，本次仿真采用基于節(jié)點度的分割方式構(gòu)成下采樣集合，依次選取度最大的節(jié)點以及其鄰居節(jié)點構(gòu)成局部集合，每個局部集合中選取一個節(jié)點作為采樣節(jié)點。下采樣集合中含有873個節(jié)點。首先需要模擬生成仿真實驗中與明尼蘇達路網(wǎng)圖相適應(yīng)的帶限信號，本文主要利用圖傅里葉變換、圖譜域截取與圖傅里葉反變換進行生成，其具體過程如下所示：

主檢查員會以PPT的方式介紹哥倫比亞概況、INVIMA背景、GMP認證依據(jù)、缺陷的分類、如何進行整改以及認證通過的標準。期間，還會穿插介紹一下哥倫比亞的風(fēng)光，并推薦一些景點。受檢方也可以準備一個PPT，介紹一下公司的背景以及GMP的執(zhí)行情況。

(1)首先產(chǎn)生一個2642行1列的隨機信號，其每一行元素對應(yīng)明尼蘇達州路網(wǎng)圖上每個節(jié)點；

(2)通過圖傅里葉變換將圖信號變換至圖譜域，設(shè)定圖譜域截止頻率，將高于圖截止頻率的分量設(shè)置為零；

(3)通過圖傅里葉反變換將圖譜域信號變換至頂點域。

上述步驟中，第1步產(chǎn)生仿真所需的初始信號，并使其單個元素對應(yīng)于明尼蘇達州路網(wǎng)圖上的單個節(jié)點；第2步與第3步則利用圖傅里葉變換，使得初始信號中元素之間的關(guān)聯(lián)關(guān)系與明尼蘇達州路網(wǎng)圖上對應(yīng)節(jié)點之間的邊相符合，并且使該信號滿足圖譜域帶限的特性。需要說明的是，基于目前的研究工作可知，所研究的圖信號僅需要其滿足圖譜域帶限特性，并無其他限制條件。此外，采用山東電網(wǎng)作為圖結(jié)構(gòu)，并將山東電力消耗數(shù)據(jù)作為真實世界的數(shù)據(jù)對比分析了所有算法的實際應(yīng)用性能。

4.1 重建性能

本節(jié)仿真實驗的目的是驗證IGSR-W算法中加權(quán)因子對算法性能的影響，并且對比分析所提算法與現(xiàn)有算法的性能表現(xiàn)。采用0.45作為本次仿真的圖譜域截止頻率(歸一化圖譜域頻率的變化范圍為0至2)。首先，鑒于加權(quán)因子的變化范圍為0至1，設(shè)置加權(quán)因子的參數(shù)值為0, 0.2, 0.4, 0.6, 0.8和1.0，分析加權(quán)因子對IGSR-W算法的魯棒性。如圖2(a)所示，縱坐標為相對誤差，橫坐標為迭代次數(shù)，IGSR-W算法在不同的加權(quán)因子下都具有穩(wěn)定的表現(xiàn)，且其加權(quán)因子為0.6時獲得最快收斂速度。因此，將設(shè)置加權(quán)因子的參數(shù)值為0.6，以此分析所提算法與現(xiàn)有算法之間的重建性能表現(xiàn)。重建性能的對比如圖2(b)所示，縱坐標為相對誤差，橫坐標為迭代次數(shù)。從圖中可以看出，IGSR-W和IGSR比ILSR和IPR擁有較快的信號重建收斂速度，與前文闡述的理論分析相同；得益于加權(quán)處理，IGSR-W在IGSR的基礎(chǔ)上進一步提升了算法的收斂速度。

4.2 圖譜域截止頻率

由于現(xiàn)有算法都是基于迭代收斂，交替投影至下采樣子空間和低通濾波子空間。因此，圖譜域截止頻率也是一個非常關(guān)鍵的影響因素。本節(jié)是為了驗證重建算法對于圖譜域截止頻率的魯棒性，觀察其在不同的圖譜域截止頻率下是否能夠保持穩(wěn)定性。設(shè)置圖譜域的截止頻率的變化范圍為0.40至0.50?；谏弦还?jié)仿真實驗的結(jié)果，設(shè)置加權(quán)因子為0.60。如圖3所示，橫坐標為圖譜域截止頻率，縱坐標為相對誤差，圖中曲線為ILSR, IPR, IGSR和IGSR-W在不同的圖譜域截止頻率設(shè)定下第10次迭代重建的重建誤差。從圖中可以看出，隨著圖譜域截止頻率的變化，所有重建算法具有相類似的增長變化，其相對誤差都隨著圖譜域截止頻率的增大而增大。由于采用了重建殘差的局部均值和全局偏置擴散，IGSR和IGSR-W比ILSR和IPR在第10次迭代重建的誤差擁有較低的重建誤差。由于采用了加權(quán)處理，IGSR-W在IGSR的基礎(chǔ)上提升了算法性能，并且在各個圖譜域截止頻率上都保持穩(wěn)定。

圖2 參數(shù)分析與重建收斂曲線對比圖

圖3 圖頻域截止頻率變化對比圖

4.3 典型圖結(jié)構(gòu)

現(xiàn)實世界中的大部分網(wǎng)絡(luò)都可以劃歸為3種典型的圖結(jié)構(gòu)：Erdos-Renyi隨機圖(Erdos-Renyi Graph)、小世界圖(Small-world Graph)和無標度圖(Scale-free Graph)。Erdos-Renyi隨機圖是一種典型的隨機圖結(jié)構(gòu)，節(jié)點之間的連接關(guān)系由某個概率確定。本次仿真生成了40個節(jié)點Erdos-Renyi隨機圖，節(jié)點之間的連接概率為0.10。小世界圖是介于隨機圖與規(guī)則圖之間的典型圖結(jié)構(gòu)，圖中大部分的節(jié)點彼此不鄰接，但是大部分節(jié)點可以從任一其他節(jié)點經(jīng)過有限步數(shù)跳轉(zhuǎn)到達。采用Watts-Strogatz模 型[15]產(chǎn)生100個節(jié)點的小世界圖結(jié)構(gòu)。第3個典型的圖結(jié)構(gòu)是無標度圖，其最主要的特點是其節(jié)點的度分布服從冪律分布。采用Barabasi-Albert模型[16]產(chǎn)生200個節(jié)點的無標度圖結(jié)構(gòu)。3種典型結(jié)構(gòu)中的圖譜域截止頻率值均為0.50。為了有效驗證所有算法重建性能，消除隨機因素的影響，每種圖結(jié)構(gòu)的實驗結(jié)果為100次隨機圖結(jié)構(gòu)的平均值。首先，設(shè)置加權(quán)因子的參數(shù)值為0, 0.2, 0.4, 0.6, 0.8和1.0，分析IGSR-W算法的不同加權(quán)因子在3種典型圖結(jié)構(gòu)下的表現(xiàn)。如圖4(a)所示(鑒于線條過多，僅選取部分結(jié)果展示)，縱坐標為相對誤差，橫坐標為迭代次數(shù)，IGSR-W的不同加權(quán)因子在3種典型圖結(jié)構(gòu)下具有穩(wěn)定的性能，且在Erdos-Renyi隨機圖、小世界圖和無標度圖上具有最快收斂速度的加權(quán)因子分別為0.2, 0.2和0.8。因此，依次將相關(guān)的加權(quán)因子設(shè)置為0.2, 0.2和0.8，分析所提算法與現(xiàn)有算法之間的性能。如圖4(b)所示，對比3種圖結(jié)構(gòu)，算法在小世界圖結(jié)構(gòu)的重建性能為最佳。對比其他重建算法，IGSR-W在3種典型圖結(jié)構(gòu)上具有較低的迭代重建誤差。由此可見，IGSR-W重建算法不拘泥于某種特定的拓撲結(jié)構(gòu)，具有普適性的特點，其局部均值擴散算子與全局偏置擴散算子相輔相成，實現(xiàn)對采樣圖信號的快速與穩(wěn)定的重建。

圖4 基于典型圖結(jié)構(gòu)的性能對比圖

4.4 真實世界數(shù)據(jù)

采用山東電網(wǎng)2015年的電力消耗數(shù)據(jù)[17]作為真實世界的數(shù)據(jù)，驗證所提出的重建算法與現(xiàn)有的重建算法。圖結(jié)構(gòu)如圖5(a)所示，圖結(jié)構(gòu)的節(jié)點為山東省17個地級市，節(jié)點之間的邊為地級市之間的電力連接線。采用局部集合分割方式構(gòu)成采樣集合，其含有7個節(jié)點。關(guān)于真實系統(tǒng)中的圖譜域截止頻率和加權(quán)因子的選定，可以將存儲的歷史數(shù)據(jù)或者抓取的快照數(shù)據(jù)(snapshot data)投影至圖譜域進行觀測，從而獲取合適的參數(shù)值。因此，本次仿真設(shè)定的圖譜域截止頻率為0.55，設(shè)置加權(quán)因子為0.2。重建性能如圖5(b)所示，橫坐標為迭代次數(shù)，縱坐標為相對誤差。從仿真結(jié)果中可以看出，與ILSR和IPR相比，IGSR和IGSR-W具有更快的迭代收斂速度；由于引入加權(quán)處理方式，IGSR-W比IGSR具有更快的收斂速度。

5 討論與分析

當IGSR-W算法不進行加權(quán)處理，IGSR-W算法退化為IGSR算法；當IGSR-W算法中不進行加權(quán)處理、局部均值擴散控制因子和全局偏置擴散控制因子為零時，也就是在重建過程中不進行采樣節(jié)點重建殘差的擴散，IGSR-W算法退化為ILSR算法；當IGSR-W算法中不進行加權(quán)處理且全局偏置擴散控制因子為零時，也就是在重建過程中采樣節(jié)點的重建殘差值僅擴散至與其有連接關(guān)系的鄰居節(jié)點，IGSR-W算法退化為IPR算法。因此，IGSR-W具有統(tǒng)一性與模塊化的優(yōu)越特點。

此外，由于引入局部均值擴散過程和全局偏置擴散過程，IGSR-W要比ILSR和IPR消耗更多的計算資源。但是，采用集中式的數(shù)據(jù)采樣方式，原始信號的重建過程通常是在一個被認為計算資源與能量資源無限的數(shù)據(jù)處理中心完成，從而彌補了IGSR-W所引起的不足。

6 結(jié)束語

本文針對采樣的帶限圖信號重建問題，提出了未采樣信號的構(gòu)成框架，定義了局部均值擴散算子和全局偏置擴散算子的概念，提出了基于擴散算子的加權(quán)重建算法。最后采用實驗方法，驗證了所提出算法的有效性。之后的研究者，可以根據(jù)實際系統(tǒng)的需要，依托未采樣信號的3層關(guān)聯(lián)體系，設(shè)計不同的局部均值擴散算子和全局偏置擴散算子，靈活實現(xiàn)圖信號的采樣與重建過程。此外，本文采用從歷史數(shù)據(jù)或抓取的數(shù)據(jù)中獲取加權(quán)因子，其最優(yōu)的獲取方式將在后續(xù)研究中繼續(xù)展開。

圖5 真實世界數(shù)據(jù)的性能對比圖

[1] SHUMAN D I, NARANG S K, and FROSSARD P. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[J]., 2013, 30(3): 83-98. doi: 10.1109/MSP.2012.2235192.

[2] SANDRYHAILA A and MOURA J M F. Big data analysis with signal processing on graphs: Representation and processing of massive data sets with irregular structure[J]., 2014, 31(5): 80-90. doi: 10.1109/MSP.2014.2329213.

[3] CHEN Siheng, VARMA R, SANDRYHAILA A,. Discrete signal processing on graphs: Sampling theory[J]., 2015, 63(24): 6510-6523. doi: 10.1109/ TSP.2015.2469645.

[4] MARQUES A G, SEGARRA S, LEUS G,. Sampling of graph signals with successive local aggregations[J]., 2016, 64(7): 1832-1843. doi: 10.1109/TSP.2015.2507546.

[5] PESENSON I. Sampling in Paley-Wiener spaces on combinatorial graphs[J]., 2008, 360(10): 5603-5627. doi: 10.1090 /S0002-9947-08-04511-X.

[6] PAPOULIS A. A new algorithm in spectral analysis and band-limited extrapolation[J]., 1975, 22(9): 735-742. doi: 10.1109/TCS.1975. 1084118.

[7] GERCHBERG R W. Super-resolution through error energy reduction[J]., 1974, 21(9): 709-720. doi: 10.1080/713818946.

[8] NARANG S K, GADDE A, and SANOU E. Localized iterative methods for interpolation in graph structured data[C]. IEEE Global Conference on Signal and Information Processing, Texas, USA, 2013: 491-494. doi: 10.1109/ GlobalSIP.2013.6736922.

[9] ANIS A, GADDE A, and ORTEGA A. Towards a sampling theorem for signals on arbitrary graphs[C]. IEEE International Conference on Acoustics, Speech and Signal Processing, Florence, Italy, 2014: 3864-3868. doi: 10.1109/ ICASSP.2014.6854325.

[10] WANG X, LIU P, and GU Y. Local-set-based graph signal reconstruction[J]., 2015, 63(9): 2432-2444. doi: 10.1109/TSP.2015.2411217.

[11] WANG X, CHEN J, and GU Y. Generalized graph signal sampling and reconstruction[C]. IEEE Global Conference on Signal and Information Processing, Orlando, USA, 2015: 567-571. doi: 10.1109 /GlobalSIP.2015.7418259.

[12] GLEICH D. The MatlabBGL Matlab Library[OL]. http://www.cs.purdue.edu/homes/dgleich/packages/matlab -bgl/index.html.2016.9.

[13] SANDRYHAILA A and MOURA J. Discrete signal processing on graphs: Frequency analysis[J]., 2014, 62(12): 3042-3054. doi: 10.1109/TSP.2014.2321121.

[14] SANDRYHAILA A and MOURA J. Discrete signal processing on graphs: graph Fourier transform[C]. IEEE International Conference on Acoustics, Speech and Signal Processing, Vancouver, Canada, 2013: 6167-6170. doi: 10.1109/ICASSP.2013.6638850.

[15] WATTS D J and STROGATZ S H. Collective dynamics of ‘small-world’ networks[J]., 1998, 393(6684): 440-442. doi: 10.1038/30918.

[16] BARABASI A L and ALBERT R. Emergence of scaling in random networks[J]., 1999, 286(5439): 509-512. doi: 10.1126/science.286.5439.509.

[17] SHANDONG BUREAU OF STATSTICS. Shandong Statistical Yearbook (2015)[OL]. http://www.stats-sd.gov. cn.2016.8.

楊立山： 男，1986年生，博士生，研究方向為圖信號處理與壓縮感知、大數(shù)據(jù)處理.

游康勇： 男，1993年生，博士生，研究方向為壓縮感知技術(shù).

郭文彬： 男，1971年生，副教授，研究方向為信號處理、認知無線電及其關(guān)鍵技術(shù).

Graph Diffusion Operator Based Weighted ReconstructionStrategy for Band-limited Graph Signals

YANG Lishan YOU Kangyong GUO Wenbin

(,,100876,)

Signal processing on graphs extends signal processing concepts and methodologies from the classical signal processing theory to data indexed by general graphs. For a band-limited graph signal, the unsampled data can be reconstructed from the sampled data by exploiting the relationship of the graph signals. This paper proposes a concept of graph diffusion operator for signal processing on graphs, and uses the operator to reconstruct band-limited graph signals from the sampled data. In each iteration, the residuals of the sampled vertices are propagated to all the unsampled vertices, and the known information and initial estimated results are further exploited via weighted process, aiming at accelerating the convergence. An analysis framework is proposed for the unsampled graph signals. The simulation results of synthetic data and real-world data demonstrate the wonderful effectiveness of the proposed reconstruction strategy.

Band-limited graph signals processing; Graph diffusion operator; Downsampling and reconstruction

TN911.7

A

1009-5896(2017)12-2937-08

10.11999/JEIT170106

2017-02-08；

2017-09-11；

2017-10-27

通信作者：郭文彬 gwb@bupt.edu.cn

國家自然科學(xué)基金(61271181)

The National Natural Science Foundation of China (61271181)