帶限圖信號的最優采樣集設計

謝 煊, 馮 輝,*, 胡 波, 李 旦,2

(1. 復旦大學信息科學與工程學院智慧網絡與系統研究中心, 上海 200433;2. 上海市空間智能控制技術重點實驗室, 上海 200433)

0 引 言

我們生活在萬物互聯的時代,分布式的網絡信號廣泛存在于傳感器網絡、社交網絡等不規則的拓撲上。由于傳統的時間信號無法很好地描述網絡信號不同節點之間的相互關系,圖信號應運而生。圖信號將信號與圖的拓撲結構作為一個整體表達。以社交網絡為例,圖的拓撲關系可以表達用戶之間的好友關系,而圖上每個節點的信號可以表達每個用戶對某個商品的評價或對某個事件的態度等。

圖信號處理通過引入圖上的傅里葉變換將傳統信號處理理論進行了延伸與推廣。圖譜理論是圖傅里葉變換中最重要的理論基礎,其通過圖矩陣的特征值和特征向量研究圖信號的圖譜域特征。借助圖上的傅里葉變換,研究人員已經將經典信號處理中的采樣與重構及實際應用、濾波、平移等拓展至圖信號處理領域。此外,圖信號處理也被廣泛地應用于群體檢測、異常檢測、半監督學習和圖卷積神經網絡等。

現實世界的網絡中,相鄰節點的信號一般具有一定的平滑性。例如,傳感器網絡中距離較近的傳感器監測到的溫濕度、氣壓等差異值不會很大;社交網絡中有好友關系的人往往具有相似的興趣愛好或者觀點。這種圖信號在節點域上的平滑特性在圖譜域可以表示為帶限或近似帶限。在此情形下,可利用部分節點上的信號來重建或者估計所有節點的信號。根據節點信號的觀測是否有噪,可將圖信號的采樣集設計方法分為兩類:節點信號觀測無噪的采樣集設計和節點信號觀測有噪的采樣集設計。

本文主要研究觀測有噪的帶限圖信號的最優采樣集設計,其目的在于在給定采樣預算的情況下選擇出能使得信號估計誤差最小的采樣集。最優采樣集設計可以通過實驗設計或非實驗設計的方法獲得。前者主要基于對估計子性能的組合優化建模,可以納入信號的先驗知識,但通常是NP-hard的組合優化問題,需要近似求解。近似求解的方法主要分為兩種:一種是貪婪算法求解;另一種是將原始問題松弛成凸優化問題進行求解。后者主要包括隨機采樣和基于拓撲重要性的采樣。

實際中,考慮到人力物力的成本、數據傳輸帶寬等約束,對傳感器網絡、交通網絡等的采樣與估計往往是分多階段進行的。在已有工作中,最優采樣集都是為單階段采樣設計的,即假設采樣一次性完成,每個節點只允許被采樣一次。由于觀測噪聲的存在,對某些重要節點進行多階段觀測可能會帶來更好的信號估計性能。因此,無論從應用場景還是信號估計性能的角度出發,多階段采樣與估計都有更高的研究價值。

在本文的初步工作文獻[17]中提出了多階段采樣的初步建模并通過松弛-量化的方法對多階段采樣集設計的問題進行了求解。本文對松弛-量化方法的性能在理論上進行了分析，證明了該方法是漸近最優的,同時也給出了松弛最優解與量化解目標函數值之差的界。此外,由于原始優化問題的目標函數中存在求逆操作,松弛-量化的方法得到的采樣集在采樣預算過少時有可能使得目標函數中的求逆操作無法進行,所以本文還通過擾動分析給出了保證目標函數有意義的采樣預算的下界。

與具有規則拓撲的傳統時域信號不同,圖信號拓撲上的不規則性使得其不同節點對于信號估計的重要性會有所不同?，F有的基于實驗設計的采樣集設計方法,往往更多關注于優化問題的求解而沒有對影響節點在采樣與估計中的重要性的因素進行討論與分析。本文定性分析了不同節點采樣比例的分配對采樣集設計優化問題的目標函數值的影響,得到了評價帶限圖信號的各個節點在采樣與估計中重要性的指標,并給出了其物理意義。對于大規模的圖信號,求解優化問題的計算量往往是難以負擔的,基于對節點在采樣與估計中的重要性的分析,本文還為該場景下的采樣集設計提供了復雜度較低的近似解。

最后,本文對所提出的最優采樣集設計方法及近似解的性能進行了仿真驗證。實驗結果表明、使用本文中多階段的采樣集設計方法得到的觀測可以很好地估計信號并且對噪聲具有良好的魯棒性。而近似解能夠以最低的計算復雜度達到與對比算法相當的估計性能。

1 系統模型

本節將首先介紹圖信號的基本概念及帶限圖信號的模型。然后,基于圖信號估計子的形式,給出旨在最小化信號估計誤差的最優采樣集設計的優化問題。

=

(1)

(2)

接下來首先對各個階段采樣矩陣已知情況下的圖信號估計方法進行推導。假設對圖信號的采樣分個階段進行,若在階段采樣個節點,則該階段的觀測信號可以表示為

=(+)

(3)

(4)

例如,對于一個有5個節點的圖,階段采樣觀測其第1,3,4號節點上的信號,則

(5)

(6)

(7)

(8)

(9)

通過該變形可以發現,估計的誤差協方差取決于被選擇的次數,而與每個階段分配的采樣預算無關。因此,在下文中,為了減少優化問題的變量個數,我們將直接對={,,…,}進行求解。

由于誤差的協方差為矩陣,不便于最小化,所以本文旨在設計最優的使得信號估計的誤差協方差的某種標量化形式最小。公式的標量化主要有如下幾種形式:

-optimal:()=logdet()

(10)

(11)

-optimal:()=tr()

(12)

因此,多階段采樣集設計的優化問題可以表達為

s.t.++…+=

(13)

0≤≤

∈

式中:3個約束分別對應了個階段共采樣個觀測,每個節點最多采樣次和采樣次數為整數3個約束。

2 松弛-量化算法及分析

第1節中所述的多階段采樣集的優化問題為一個難解的組合優化問題。本節首先通過松弛-量化的方法來求得次優解。然后對所求得的次優解的性能進行理論分析。

2.1 次優解的求取

令=[,,…,],其中=為第個節點被采樣的比例,對整數約束∈進行松弛,可以得到松弛的優化問題:

(14)

=1

上述優化問題是一個凸優化問題,可以使用標準工具包來求解。下文中,其最優解用來表示。

為了從式(14)的解中獲得對應的采樣集,需將的每一個元素量化成1的整數倍。與最常用的四舍五入的取整方法不同,本文使用隨機量化方法來保證量化的均值是無偏的。隨機量化Q∶→Q()的定義如下:∈[0,1]被等分成-1個間隔,即量化點為{1,2,…,1}。對于∈{0,1,…,-1},∈[,(+1))的量化值()是一個隨機變量,定義為

(15)

對每個∈[,(+1)),都有E[()]=,所以()為的一個無偏的量化。

本文稱·()為式(13)的松弛-量化解(relaxation-quantization solution,RQS)。

2.2 量化的擾動分析

令

(16)

(17)

(18)

若已知是非奇異的,那么根據文獻[26],與距其最近的奇異矩陣在范數意義下的相對距離滿足:

(19)

(20)

(21)

(22)

(23)

由切比雪夫不等式:

(24)

證畢

當足夠大時,任意∈[,(+1)]可以近似認為是均勻分布的,即～[-12,12]。由于E[()]=,所以有

(25)

大多數情況,并不需要式(23)中的概率為1,它可以根據實際需要被設置為(0<<1)。的值決定了不同的的下界,可得如下推論。

如果采樣預算滿足

(26)

2.3 松弛-量化解的性能

首先,可以得到如下不等式:

|()-(·())|≤
|()-(M)|+
|(M)-(·())|

(27)

當→∞,的可行域與M的可行域將變得相同,即

(28)

所以接下來需要證明

(29)

由于問題為一個凸優化問題,為其最優解,因此對的任何量化都會帶來目標函數值的增加。因此

|(M)-(·())|=
(·())-(M)|=
-logdet(+Δ)+logdet()

(30)

(31)

則(·())與(M)之間的差滿足如下不等式:

(32)

由式(31)可得

(33)

(34)

證畢

3 節點采樣重要性與近似求解

本節旨在探索影響圖信號的節點在采樣與估計中的因素,并給出評價該重要性的指標及其物理意義。最后,基于節點重要性提出了低復雜度近似求解優化問題的方法,為大規模圖信號的多階段采樣集設計提供了可行的方案。

3.1 節點采樣重要性

依舊以-optimal為例,本節將通過分析式(14)中的目標函數來定性分析圖的拓撲如何影響節點對信號估計的重要性。

優化問題的目標函數可以表達為

(35)

(Gershgorin圓盤定理)令為×矩陣,其第行第列的元素為。對于∈{1,2，…,},令=∑≠||為的第行的非對角元素的絕對值之和。令(,)為一個以為圓心為半徑的圓,則稱(,)為一個Gershgorin圓盤(Gershgorin circle,GC)。矩陣的每一個特征值都至少落在的一個GC里。

(36)

(37)

圖1 GC及特征值分布示意圖Fig.1 GC and locations of eigenvalues

3.2 近似解

(38)

初始化:歸一化系數Z=K1: 將{uT1u1,uT2u2,…,uTNuN}使用快速排序從大到小進行排列,排序后的序號集為S={s1,s2,…,sN};2: for i=1,2,…,N do3: papproxsi=uTsiusi/Z;4: if papproxsi>T/M then5: papproxsi=T/M;6: end if7: Z=Z-papproxsi;8: end for

上述求解過程中第1步的算法復雜度為(log 2),第2步到第7步的算法復雜度為()。可以發現該近似解法大大提升了算法的速度,可以應用于難以求解優化問題的大規模圖信號的采樣集設計中。在得到的近似解后,依舊可以通過將其量化為1的整數倍,本文將()稱為近似松弛-量化解(approximate relaxation-quantization solution,ARQS)。

4 仿真結果

圖2 實驗中選用的圖信號的拓撲Fig.2 Topologies of graph signals in the experiment

對使用不同采樣集設計方法得到的節點進行信號估計,其性能使用歸一化均方誤差評價,計算方式如下:

(39)

4.1 量化方法性能分析

圖3 量化方法性能Fig.3 Performance of quantization method

4.2 近似解性能驗證

本節將對比不同帶寬下第32節中的近似解與優化問題的最優解(M)在目標函數值上的接近程度來評價其性能。實驗參數設置為=128,=5,=2。實驗結果如圖4所示。

圖4 近似解的性能Fig.4 Performance of approximate solution

4.3 多階段采樣性能

本節將本文的多階段采樣算法RQS和ARQS和其他文獻中的單階段采樣算法的性能進行對比。對比算法如下。

M1:隨機采樣個不同的節點。

M2:使用貪婪算法求解優化問題得到個不同的采樣節點,算法復雜度為()。

M3:求解松弛的凸優化問題,選取采樣比例最大的個節點,算法復雜度為()。

M4:選擇個節點使得其上的核函數能夠均勻地覆蓋整個圖信號,算法復雜度為((||+)+)+(),其中和均為與M4中特定算子有關的參數。

圖5 不同算法在不同信噪比下的信號估計性能Fig.5 Performance of signal estimation of different algorithms under different signal to noise ratios

圖6 不同拓撲下節點采樣重要性分布Fig.6 Sampling importance distribution of vertices on different topologies

圖7 不同帶寬下RQS節點采樣比例分配Fig.7 Sampling proportion on vertices of RQS for different bandwidths

5 結 論

本文研究了帶限圖信號的多階段最優采樣集的設計,提出了一種基于松弛-量化方法的最優采樣集設計方法,分析了該方法有效的條件和漸近性能。通過對最優采樣集設計的目標函數進行定性分析,展示了圖信號的拓撲對節點采樣重要性的影響,進而提出了松弛優化問題的低復雜度近似解,用于降低大規模圖信號采樣集設計的計算開銷。仿真結果表明,使用所提算法設計的采樣集在估計具有不規則拓撲的圖信號時比其他現有算法有更好的性能。