基于OMMP 算法的多測量向量問題的重構

馮曉艷,王金平

（寧波大學 數學與統計學院,浙江 寧波 315211）

壓縮感知[1-2]作為一種新的采樣理論,已廣泛應用于各個領域,如圖像壓縮、信號處理、雷達系統以及醫學成像等[3-6].壓縮感知的主要目的是從模型

中恢復稀疏信號x.我們可以通過找到如下l0優化問題的解,達到這一目的:

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

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

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

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

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

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

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

對一般的正整數N,為保證OMMP 算法準確地恢復K-稀疏信號,已有很多基于RIC 條件被陸續提出.Liu 等[14]提出,當限制等距常數δ滿足:

時,OMMP 算法可恢復任意K-稀疏信號;Wang 等[15]證明了

是OMMP 算法經K次迭代恢復任意K-稀疏信號的一個充分條件;該條件又被Satpathi 等[16]改善為:

Shen 等[17]將限制RIC 條件進一步改善為:

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

時,OMMP 算法可以在K次迭代準確恢復K-稀疏信號.文獻[18]中的RIC 針對單測量向量問題中的OMMP 算法.本文將此條件由單測量向量問題過渡到多測量向量問題,發現該結論仍然成立.

在單測量信號恢復中,信噪比(SNR)和最小平均比(MAR)根據文獻[19]定義如下:

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

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

則OMMP 算法每次迭代可以確?；謴椭辽僖粋€正確的指標集.

1 預備知識

首先介紹文中出現的一些基礎符號的含義,以及用到的引理.

對任意矩陣A?Rn×p和B?Rn×p,定義內積

其中:AT表示矩陣A的轉置.由這種內積誘導的范數是Frobenius 范數,記為||?||F.對任意向量x和矩陣X,||x||2和||X||F分別表示x的l2范數和X的Frobenius 范數,且

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

下面介紹幾個有用的引理.

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

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

2 主要結果

給出MMV 問題的OMMP 算法可以穩定恢復K-稀疏信號的充分條件.首先給出以下引理.

引理5對于正整數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 的靈感主要源自文獻[18],把文獻[18]中的p=1 延拓到一般的p,即MMV 問題.不同于文獻[18]中定義的向量定義矩陣EW=RN×p(式(15)).

首先證明

此處(a)是由式(9)所得,(b)是因為

通過計算可得:

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

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

此外,還定義

則有:

因此有:

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

由式(26)可得:

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

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

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

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

引理5 的證明結束.

注釋1當p=1 時,引理5 中式(10)就變為文獻[18]中的

當p=1 且N=1 時,該結論變成文獻[23]中

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

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

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

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

時終止迭代.

用數學歸納法證明該結論.

假設OMMP 算法在前k次迭代中至少選擇一個正確索引,則有l=|T∩Λk|≥k.假設T?Λk(即l≤|T|-1)以及算法1 至少迭代(k+1)次,否則結論顯然成立.接著需要證明(Λk+1Λk)∩T≠?.由于Λ0=?,所以k=0時歸納假設|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.由歸納假設,

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

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

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

因此有:

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

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

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

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

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

注釋2當N=1 且p=1 時,MMV 問題的OMMP 算法就變成了SMV 問題的OMP 算法,對應的條件變成文獻[19]中的

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

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

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

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

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

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

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

注釋3在p=1 且沒有噪聲的情況下,OMMP算法在K次迭代準確地恢復稀疏信號x的充分條件是

很顯然

即定理3 的條件更松弛.

3 結論

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

則OMMP 算法可以準確恢復K-行稀疏矩陣X.