馮曉艷,王金平

（寧波大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,浙江 寧波 315211）

壓縮感知[1-2]作為一種新的采樣理論,已廣泛應(yīng)用于各個(gè)領(lǐng)域,如圖像壓縮、信號(hào)處理、雷達(dá)系統(tǒng)以及醫(yī)學(xué)成像等[3-6].壓縮感知的主要目的是從模型

中恢復(fù)稀疏信號(hào)x.我們可以通過找到如下l0優(yōu)化問題的解,達(dá)到這一目的:

式中:y?Rm是測(cè)量向量;Φ?Rm×n(m?n)是感知矩陣;v?Rm是噪聲向量;||x||0是x的l0范數(shù),表示x的非零項(xiàng)個(gè)數(shù),對(duì)于任意向量x,定義其支撐集: supp(x)={i:xi≠0}.如果它是K-稀疏的,則有||x||0≤K.式(1)是單測(cè)量向量的稀疏恢復(fù),可以拓展到多測(cè)量向量的稀疏恢復(fù)問題.本文主要研究多測(cè)量向量問題[7-9].

多測(cè)量向量問題在腦磁圖掃描技術(shù)[10]、波達(dá)方向估計(jì)[11]等領(lǐng)域有著廣泛應(yīng)用.向量x的支撐集上面已給出,對(duì)于矩陣X=(X1,X2,…,Xp)?Rn×p,定義其行支撐集為:

這里Xi表示矩陣X的第i列,若測(cè)量矩陣Y?Rm×p,感知矩陣Φ?Rm×n是已知的,則多測(cè)量向量問題可以描述為:

這里|supp(X)|表示矩陣X的非零行數(shù).若|supp(X)|≤K,則稱矩陣X是K-行稀疏的.很顯然,當(dāng)p=1 時(shí),多測(cè)量向量(MMV)問題就變成了單測(cè)量向量(SMV)問題.

文獻(xiàn)[12-13]已證明,當(dāng)矩陣Φ滿足一定條件時(shí),通過恢復(fù)單測(cè)量向量的一些稀疏算法可以穩(wěn)定恢復(fù)未知信號(hào)x.在分析稀疏恢復(fù)算法的恢復(fù)性能時(shí),限制等距性(RIP)是使用較為廣泛的方法之一.對(duì)于感知矩陣Φ?Rm×n和任意正整數(shù)K,若存在一個(gè)常數(shù)δ? (0,1)滿足:

則稱Φ滿足K階的限制等距性,使得式(4)成立的最小常數(shù)δK稱為Φ的限制等距常數(shù)(RIC).

正交匹配追蹤算法(OMP 算法)是解決式(1)非常有效的一種貪婪算法,其對(duì)式(3)同樣有效.正交多匹配追蹤算法(OMMP 算法)[13](也被稱作gOMP 算法[14])作為OMP 算法的拓展,每次迭代從感知矩陣Φ中選擇與殘差相關(guān)性最大的N≥1 個(gè)列作為指標(biāo)集.由于每次迭代選擇多個(gè)正確的指標(biāo)集,所以相較于OMP 算法,OMMP 算法所需的迭代次數(shù)更少.在某些條件下,OMMP 算法可以找到式(3)中的最稀疏解X.多測(cè)量向量問題的OMMP 算法如下:

對(duì)一般的正整數(shù)N,為保證OMMP 算法準(zhǔn)確地恢復(fù)K-稀疏信號(hào),已有很多基于RIC 條件被陸續(xù)提出.Liu 等[14]提出,當(dāng)限制等距常數(shù)δ滿足:

時(shí),OMMP 算法可恢復(fù)任意K-稀疏信號(hào);Wang 等[15]證明了

是OMMP 算法經(jīng)K次迭代恢復(fù)任意K-稀疏信號(hào)的一個(gè)充分條件;該條件又被Satpathi 等[16]改善為:

Shen 等[17]將限制RIC 條件進(jìn)一步改善為:

Wen 等[18]提出了更加松弛的RIP 條件,即RIC 滿足:

時(shí),OMMP 算法可以在K次迭代準(zhǔn)確恢復(fù)K-稀疏信號(hào).文獻(xiàn)[18]中的RIC 針對(duì)單測(cè)量向量問題中的OMMP 算法.本文將此條件由單測(cè)量向量問題過渡到多測(cè)量向量問題,發(fā)現(xiàn)該結(jié)論仍然成立.

在單測(cè)量信號(hào)恢復(fù)中,信噪比(SNR)和最小平均比(MAR)根據(jù)文獻(xiàn)[19]定義如下:

受此啟發(fā),在多測(cè)量向量問題中把它們分別命名為多向量信噪比(MSNR)和多向量最小平均比(MMAR),并定義為:

有了這兩個(gè)新定義,我們將證明在MSNR 和MMAR 滿足一定條件下,若限制等距常數(shù)δ滿足:

則OMMP 算法每次迭代可以確?；謴?fù)至少一個(gè)正確的指標(biāo)集.

1 預(yù)備知識(shí)

首先介紹文中出現(xiàn)的一些基礎(chǔ)符號(hào)的含義,以及用到的引理.

對(duì)任意矩陣A?Rn×p和B?Rn×p,定義內(nèi)積

其中:AT表示矩陣A的轉(zhuǎn)置.由這種內(nèi)積誘導(dǎo)的范數(shù)是Frobenius 范數(shù),記為||?||F.對(duì)任意向量x和矩陣X,||x||2和||X||F分別表示x的l2范數(shù)和X的Frobenius 范數(shù),且

I和0 分別表示單位矩陣和零矩陣.T=supp(X)是X的支撐集,|T|表示集合T的基數(shù),Λ={1,2,…,n}且TΛ={i?T,i?Λ}.令Tc和Λc分別表示T和Λ的補(bǔ)集,即Tc={1,2,…,n}T,Λc={1,2,…,n}Λ.矩陣ΦΛ表示Φ的子矩陣,其中僅包含由Λ索引的列.類似地,XΛ?R|Λ|×p表示X的子矩陣,其中僅包含由Λ索引的行.如果ΦΛ是列滿秩矩陣,Φ?是其偽逆矩陣,則Φ?=分別表示ΦΛ的列空間上的投影和正交補(bǔ)投影.由PΛ的對(duì)稱性和冪等性可得表示矩陣Φ中任意一行的最大l2范數(shù).

下面介紹幾個(gè)有用的引理.

引理3[21]假設(shè)矩陣M?Rn×p,N?Rn×p,則

引理 4[22]矩陣A?Ra×a,B?Ra×a都是對(duì)稱矩陣,且AB≠0,則

2 主要結(jié)果

給出MMV 問題的OMMP 算法可以穩(wěn)定恢復(fù)K-稀疏信號(hào)的充分條件.首先給出以下引理.

引理5對(duì)于正整數(shù)N,k,l,0≤k≤l≤|T|-l,且N(k+1)+|T|-K≤m,集合Λ? {1,2,…,n}滿足|Λ|=Nk和|T∩Λ|=l,令集合W?Tc滿足|W|=N且W∩Λ=?.若Y=ΦX+V中的Φ滿足N(k+1)+|T|-l階的RIP 條件,則

在證明前需要說明,引理5 的靈感主要源自文獻(xiàn)[18],把文獻(xiàn)[18]中的p=1 延拓到一般的p,即MMV 問題.不同于文獻(xiàn)[18]中定義的向量定義矩陣EW=RN×p(式(15)).

首先證明

此處(a)是由式(9)所得,(b)是因?yàn)?/p>

通過計(jì)算可得:

為了書寫方便,令W={j1,j2,…,jN},并且定義矩陣E?RN×p為:

X(t)TΛ表示矩陣XTΛ的第t列,(EW)t表示EW的第t列.不難得到:

此外,還定義

則有:

因此有:

這里(a)是由式(18)～(20)所得,(b)和(c)分別由式(12)和式(15)所得.進(jìn)而有:

由式(26)可得:

最后一個(gè)等號(hào)是由式(14)的第一個(gè)等式得到.另一方面,有:

此處(a)是由引理2(|T∩Λ|=l,|W|=N,|Λ|=kN和|Λ∪((TΛ) ∪W)|=N(k+1)+|T|-l)得到;(b)由式(22)和式(23)得到;(c)由式(14)的第二個(gè)等式得到.

結(jié)合式(18)、(27)、(28)以及1-μ4＞0可得:

結(jié)合式(11)和式(29)可得:

引理5 的證明結(jié)束.

注釋1當(dāng)p=1 時(shí),引理5 中式(10)就變?yōu)槲墨I(xiàn)[18]中的

當(dāng)p=1 且N=1 時(shí),該結(jié)論變成文獻(xiàn)[23]中

引理中條件N(k+1)+|T|-k≤m是為了確保假設(shè)Φ滿足N(k+1)+|T|-l階的RIP 條件.

有了引理1,可以證明定理1.

定理1對(duì)正整數(shù)k和N滿足0≤k≤|T|-1和N(k+1)+|T|-k≤m,假設(shè)矩陣Φ滿足N(k+1)+|T|-l階的RIP 條件,即

則OMMP 算法在前(k+1) 次迭代中每次迭代至少可以識(shí)別一個(gè)T中的索引,直到T中所有索引都被識(shí)別,或OMMP 算法在滿足條件:

時(shí)終止迭代.

用數(shù)學(xué)歸納法證明該結(jié)論.

假設(shè)OMMP 算法在前k次迭代中至少選擇一個(gè)正確索引,則有l(wèi)=|T∩Λk|≥k.假設(shè)T?Λk(即l≤|T|-1)以及算法1 至少迭代(k+1)次,否則結(jié)論顯然成立.接著需要證明(Λk+1Λk)∩T≠?.由于Λ0=?,所以k=0時(shí)歸納假設(shè)|T|＞|Λk∩T|≥k成立.因此,第一次迭代的證明包含k=0 的情況.

讓

滿足

則要證(Λk+1Λk)∩T≠?,只需證

由式(33)知,只需證

即可.

由算法1 的第4 和5 行可知:

令

接著證明

顯然,存在i0?TΛk和j0?W滿足:

因此

此處(a)是由Cauchy-Schwarz 不等式所得,(b)由引理2 和可得.下面給出β1的下界.由算法1 的第3 行知,|Λk|=kN.由歸納假設(shè),

由式(32)和|W|=N,結(jié)合引理1 和引理5,以及式(39)可得:

第二個(gè)不等式是因式(43)中k≤l以及引理1 得到.又由l=|T∩Λk|,故有:

這里(a)和(c)是將式(6)直接代入即可,(b)是由于

因此有:

將式(44)和式(46)結(jié)合可得:

由式(42),要想式(41)成立,只要使

這等價(jià)于式(31).由歸納假設(shè),結(jié)論成立.定理中當(dāng)k=|T|-1時(shí),結(jié)合引理1 可以得到定理2.

定理2對(duì)于正整數(shù)N滿足1≤N≤(m-1)/K,假設(shè)矩陣Φ滿足RIP 條件

則OMMP 算法在k0(1≤k0＜K)次迭代終止之前至少檢索到T中的k0個(gè)索引,或者在K次迭代中恢復(fù)T只要

注釋2當(dāng)N=1 且p=1 時(shí),MMV 問題的OMMP 算法就變成了SMV 問題的OMP 算法,對(duì)應(yīng)的條件變成文獻(xiàn)[19]中的

很顯然,我們的條件比該條件更松弛.

考慮OMMP 算法迭代k0(0＜k0＜K)次后可能會(huì)終止,此時(shí)該算法在式(48)和式(49)的條件下不能保證恢復(fù)T.因此將再給出一個(gè)定理,在給出新定理前,先給出引理6.

引理6假設(shè)V=0,對(duì)于正整數(shù)k,N,并且有1≤k≤|T|-1和1≤N≤(m-1)/K,矩陣Φ滿足RIP 條件

證明用反證法證明這個(gè)引理.設(shè)T?,令Γ=T∪.定義

由定理2 和引理6,可以直接得出定理3.

定理 3假設(shè)噪聲V=0,對(duì)于正整數(shù)N(1≤N≤(m-1)/K),矩陣Φ滿足RIP 條件

則OMMP 算法可以在K次迭代中恢復(fù)X.

注釋3在p=1 且沒有噪聲的情況下,OMMP算法在K次迭代準(zhǔn)確地恢復(fù)稀疏信號(hào)x的充分條件是

很顯然

即定理3 的條件更松弛.

3 結(jié)論

本文將OMMP 算法中的SMV 問題擴(kuò)展到MMV 問題,并證明了在MSNR 和MMAR 的條件下,若矩陣Φ滿足RIP 條件

則OMMP 算法可以準(zhǔn)確恢復(fù)K-行稀疏矩陣X.