帶限圖信號的最優(yōu)采樣集設(shè)計

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

(1. 復(fù)旦大學(xué)信息科學(xué)與工程學(xué)院智慧網(wǎng)絡(luò)與系統(tǒng)研究中心, 上海 200433;2. 上海市空間智能控制技術(shù)重點實驗室, 上海 200433)

0 引 言

我們生活在萬物互聯(lián)的時代,分布式的網(wǎng)絡(luò)信號廣泛存在于傳感器網(wǎng)絡(luò)、社交網(wǎng)絡(luò)等不規(guī)則的拓撲上。由于傳統(tǒng)的時間信號無法很好地描述網(wǎng)絡(luò)信號不同節(jié)點之間的相互關(guān)系,圖信號應(yīng)運而生。圖信號將信號與圖的拓撲結(jié)構(gòu)作為一個整體表達。以社交網(wǎng)絡(luò)為例,圖的拓撲關(guān)系可以表達用戶之間的好友關(guān)系,而圖上每個節(jié)點的信號可以表達每個用戶對某個商品的評價或?qū)δ硞€事件的態(tài)度等。

圖信號處理通過引入圖上的傅里葉變換將傳統(tǒng)信號處理理論進行了延伸與推廣。圖譜理論是圖傅里葉變換中最重要的理論基礎(chǔ),其通過圖矩陣的特征值和特征向量研究圖信號的圖譜域特征。借助圖上的傅里葉變換,研究人員已經(jīng)將經(jīng)典信號處理中的采樣與重構(gòu)及實際應(yīng)用、濾波、平移等拓展至圖信號處理領(lǐng)域。此外,圖信號處理也被廣泛地應(yīng)用于群體檢測、異常檢測、半監(jiān)督學(xué)習(xí)和圖卷積神經(jīng)網(wǎng)絡(luò)等。

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

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

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

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

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

最后,本文對所提出的最優(yōu)采樣集設(shè)計方法及近似解的性能進行了仿真驗證。實驗結(jié)果表明、使用本文中多階段的采樣集設(shè)計方法得到的觀測可以很好地估計信號并且對噪聲具有良好的魯棒性。而近似解能夠以最低的計算復(fù)雜度達到與對比算法相當(dāng)?shù)墓烙嬓阅堋?/p>

1 系統(tǒng)模型

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

=

(1)

(2)

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

=(+)

(3)

(4)

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

(5)

(6)

(7)

(8)

(9)

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

由于誤差的協(xié)方差為矩陣,不便于最小化,所以本文旨在設(shè)計最優(yōu)的使得信號估計的誤差協(xié)方差的某種標(biāo)量化形式最小。公式的標(biāo)量化主要有如下幾種形式:

-optimal:()=logdet()

(10)

(11)

-optimal:()=tr()

(12)

因此,多階段采樣集設(shè)計的優(yōu)化問題可以表達為

s.t.++…+=

(13)

0≤≤

∈

式中:3個約束分別對應(yīng)了個階段共采樣個觀測,每個節(jié)點最多采樣次和采樣次數(shù)為整數(shù)3個約束。

2 松弛-量化算法及分析

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

2.1 次優(yōu)解的求取

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

(14)

=1

上述優(yōu)化問題是一個凸優(yōu)化問題,可以使用標(biāo)準(zhǔn)工具包來求解。下文中,其最優(yōu)解用來表示。

為了從式(14)的解中獲得對應(yīng)的采樣集,需將的每一個元素量化成1的整數(shù)倍。與最常用的四舍五入的取整方法不同,本文使用隨機量化方法來保證量化的均值是無偏的。隨機量化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)

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

(19)

(20)

(21)

(22)

(23)

由切比雪夫不等式:

(24)

證畢

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

(25)

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

如果采樣預(yù)算滿足

(26)

2.3 松弛-量化解的性能

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

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

(27)

當(dāng)→∞,的可行域與M的可行域?qū)⒆兊孟嗤?即

(28)

所以接下來需要證明

(29)

由于問題為一個凸優(yōu)化問題,為其最優(yōu)解,因此對的任何量化都會帶來目標(biāo)函數(shù)值的增加。因此

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

(30)

(31)

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

(32)

由式(31)可得

(33)

(34)

證畢

3 節(jié)點采樣重要性與近似求解

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

3.1 節(jié)點采樣重要性

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

優(yōu)化問題的目標(biāo)函數(shù)可以表達為

(35)

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

(36)

(37)

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

3.2 近似解

(38)

初始化:歸一化系數(shù)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步的算法復(fù)雜度為(log 2),第2步到第7步的算法復(fù)雜度為()?？梢园l(fā)現(xiàn)該近似解法大大提升了算法的速度,可以應(yīng)用于難以求解優(yōu)化問題的大規(guī)模圖信號的采樣集設(shè)計中。在得到的近似解后,依舊可以通過將其量化為1的整數(shù)倍,本文將()稱為近似松弛-量化解(approximate relaxation-quantization solution,ARQS)。

4 仿真結(jié)果

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

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

(39)

4.1 量化方法性能分析

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

4.2 近似解性能驗證

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

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

4.3 多階段采樣性能

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

M1:隨機采樣個不同的節(jié)點。

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

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

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

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

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

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

5 結(jié) 論

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