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

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

0 引 言

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

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

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

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

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

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

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

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

1 系統(tǒng)模型

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

=

(1)

(2)

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

=(+)

(3)

(4)

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

(5)

(6)

(7)

(8)

(9)

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

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

-optimal:()=logdet()

(10)

(11)

-optimal:()=tr()

(12)

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

s.t.++…+=

(13)

0≤≤

∈

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

2 松弛-量化算法及分析

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

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

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

(14)

=1

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

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

(15)

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

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

2.2 量化的擾動(dòng)分析

令

(16)

(17)

(18)

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

(19)

(20)

(21)

(22)

(23)

由切比雪夫不等式:

(24)

證畢

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

(25)

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

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

(26)

2.3 松弛-量化解的性能

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

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

(27)

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

(28)

所以接下來需要證明

(29)

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

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

(30)

(31)

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

(32)

由式(31)可得

(33)

(34)

證畢

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

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

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

依舊以-optimal為例,本節(jié)將通過分析式(14)中的目標(biāo)函數(shù)來定性分析圖的拓?fù)淙绾斡绊懝?jié)點(diǎn)對信號估計(jì)的重要性。

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

(35)

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

(36)

(37)

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

3.2 近似解

(38)

初始化:歸一化系數(shù)Z=K1: 將{uT1u1,uT2u2,…,uTNuN}使用快速排序從大到小進(jìn)行排列,排序后的序號集為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è)計(jì)中。在得到的近似解后,依舊可以通過將其量化為1的整數(shù)倍,本文將()稱為近似松弛-量化解(approximate relaxation-quantization solution,ARQS)。

4 仿真結(jié)果

圖2 實(shí)驗(yàn)中選用的圖信號的拓?fù)銯ig.2 Topologies of graph signals in the experiment

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

(39)

4.1 量化方法性能分析

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

4.2 近似解性能驗(yàn)證

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

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

4.3 多階段采樣性能

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

M1:隨機(jī)采樣個(gè)不同的節(jié)點(diǎn)。

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

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

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

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

圖6 不同拓?fù)湎鹿?jié)點(diǎn)采樣重要性分布Fig.6 Sampling importance distribution of vertices on different topologies

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

5 結(jié) 論

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