基于冗余緊框架的?2/?1極小化塊稀疏壓縮感知

張楓,王建軍

(西南大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,重慶 400715)

1 引言

壓縮感知[1-3](compressed sensing)作為一種新的采樣理論,它利用信號(hào)的稀疏特性,在遠(yuǎn)小于Nyquist采樣率的條件下,用隨機(jī)采樣獲取信號(hào)的離散樣本,通過非線性重建算法完美地恢復(fù)信號(hào).壓縮感知理論一經(jīng)提出,就引起了學(xué)者廣泛關(guān)注.目前已在壓縮成像[4],醫(yī)學(xué)成像[5],模式識(shí)別[6],圖像處理[7]等領(lǐng)域得到了廣泛應(yīng)用.

在壓縮感知中,主要考慮以下模型:y=Ax+w,其中,A∈Rm×n是測量矩陣,y∈Rm是已知的線性測量,x∈Rn是待重構(gòu)的未知信號(hào),w∈Rn是噪聲(‖w‖2≤ε).壓縮感知的核心思想是依賴于信號(hào)是否是稀疏的或者近似稀疏的,即信號(hào)x的非零元素的個(gè)數(shù)是否遠(yuǎn)小于x的長度.然而,在現(xiàn)實(shí)中常見的自然信號(hào)不一定都具有稀疏特性,甚至這類信號(hào)在某些正交基上都不能夠進(jìn)行稀疏表示.自然地,上述信號(hào)重構(gòu)過程不能直接應(yīng)用于自然信號(hào)的重構(gòu).研究表明,一些自然信號(hào)在某些緊框架D∈Rn×N(n≤N,DD?=In)[8-9]上能夠稀疏表示,即x=Dα,其中α ∈RN是(近似)稀疏的.從數(shù)學(xué)的角度講,上述問題可以寫成以下形式

其中D?表示矩陣D的共軛轉(zhuǎn)置,‖D?x‖0表示向量D?x中非零元素的個(gè)數(shù),若‖D?x‖0≤k,那么就稱向量D?x為k-稀疏信號(hào).由于問題(1)是一個(gè) NP-hard問題,即在多項(xiàng)式時(shí)間內(nèi),計(jì)算機(jī)無法有效求解.所以一種更為實(shí)際的和易于處理的凸優(yōu)化方法被提出

定義 1.1對(duì)于任意k-稀疏信號(hào)v(‖v‖0≤k),若存在 0<δk<1,使得

那么稱矩陣A滿足k階D-限制性等容性質(zhì)(D-RIP),最小的δk稱為D-限制性等容常數(shù)(D-RIC).

進(jìn)一步,他們指出當(dāng)測量矩陣A滿足D-限制性等容性質(zhì)且δ2k<0.08時(shí)通過求解有約束優(yōu)化問題(2)可以實(shí)現(xiàn)信號(hào)的魯棒重構(gòu).之后,文獻(xiàn)[11]將上述條件作了進(jìn)一步改善,得到δ2k<0.4931.已知問題(2)可以轉(zhuǎn)換為以下無約束優(yōu)化問題

文獻(xiàn)[8]提出,若A滿足D-限制性等容性質(zhì)(D-RIP),D是一個(gè)緊框架,當(dāng)D-RIP常數(shù)δ2k<0.1907并且時(shí),問題(3)的解滿足

其中‖D?x?(D?x)k‖1是最佳k-項(xiàng)?1逼近誤差.C1,C2是兩個(gè)數(shù)值型常數(shù)并且C1由 D-RIP 常數(shù)和‖D?D‖1,1:=sup{‖D?Dv‖1:v∈RN,‖v‖1≤1} 共同量化,C2僅取決于D-RIP常數(shù).

然而現(xiàn)實(shí)世界中的自然信號(hào)其結(jié)構(gòu)千變?nèi)f化,一種常見的結(jié)構(gòu)方式是自然信號(hào)在某些冗余字典下是塊稀疏的,即其非零元素以塊的形式出現(xiàn),例如彩色圖像處理[7]和 DNA-微列陣[12]等.從數(shù)學(xué)的角度看,給定分塊τ={τ1,τ2,τ3,···,τd},對(duì)于任意向量α∈RN都可以被描述為

其中α[i]表示向量α的第i個(gè)子塊,而αi則表示向量α的第i個(gè)分量元素.如果向量α最多有k個(gè)非零塊,即‖α‖2,0≤k,則稱向量α為塊k-稀疏信號(hào).特別地,當(dāng)d=1時(shí),等價(jià)于傳統(tǒng)的帶字典的壓縮感知問題.相應(yīng)地,測量矩陣A∈Rm×n和冗余字典D∈Rn×N也可以分別被描述為

其中A[i],D[i]分別表示矩陣A和D的第i個(gè)子塊(矩陣),而Ai,Di則分別表示矩陣A和D的第i個(gè)列向量.

然而使用原始的?1極小化方法來恢復(fù)此類塊稀疏信號(hào)不能充分利用信號(hào)的結(jié)構(gòu)性特征,即非零元素是以塊的形式出現(xiàn)的這一特性.為此,一些學(xué)者對(duì)傳統(tǒng)的壓縮感知方法進(jìn)行了針對(duì)性的改進(jìn).文獻(xiàn)[13]提出并研究了如下的?2/?1問題

定義 1.2對(duì)于任意塊k-稀疏信號(hào)v(‖v‖2,0≤k),若存在 0<δk|τ<1,使得

那么稱矩陣A滿足k階 Block D-限制性等容性質(zhì) (Block D-RIP),最小的δk|τ稱為Block D-限制性等容常數(shù)(Block D-RIC).

文獻(xiàn) [14]指出當(dāng)測量矩陣A滿足 Block D-限制性等容性質(zhì) (Block D-RIP)且δ2k|τ<0.4142時(shí),塊稀疏信號(hào)能夠通過求解有約束優(yōu)化問題(4)進(jìn)行魯棒重構(gòu).其后,文獻(xiàn)[15]將上述條件作了進(jìn)一步改善,得到了δ2k|τ<0.4931.類似地,問題(4)可以轉(zhuǎn)化為以下塊無約束優(yōu)化問題

假設(shè)A滿足Block D-限制性等容性質(zhì)(Block D-RIP),D是一個(gè)緊框架,本文研究表明,當(dāng) Block D-RIP 常數(shù)δ2k|τ<0.2 并且時(shí),問題(5)的解滿足

其中C1,C2是兩個(gè)數(shù)值型常數(shù)并且C1由D-RIP常數(shù)和

共同量化,C2僅取決于D-RIP常數(shù).

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

為了方便介紹后文,首先給出以下記號(hào).

?給定正整數(shù)d,記索引集T?{1,2,···,d}且|T|=k,Tc表示T在{1,2,···,d}中的補(bǔ)集.

?DT∈Rn×|T|表示從D中取出索引集T對(duì)應(yīng)的列所組成的矩陣,記

?記T1為包含的k個(gè)最大2范數(shù)塊的索引集,T2為包含的k個(gè)最大2范數(shù)塊的索引集,等.

接下來,為了證明主要定理,需要以下引理.

引理 2.1

證明由Tj的構(gòu)造,有

上式兩邊取2范數(shù),得

所以,有

引理2.2令測量y=Ax+w,h=?x,若,則問題(5)的解滿足

證明由實(shí)值凸的低階半連續(xù)函數(shù)的次微分的定義和是問題(5)的解可知,滿足問題(5)的子梯度最優(yōu)化條件,即

其中v∈RN,若,則,否則‖vi‖2≤1.因此存在v∈RN使得‖v‖2,∞≤1,進(jìn)一步,有

引理得證.

引理 2.3令D∈Rn×N為滿足DD?=In的矩陣,A∈Rm×n為滿足Block DRIP條件的矩陣.令索引集T?{1,2,···,d}恰有k個(gè)塊,測量

證明令T0為包含D?h的k個(gè)最大2范數(shù)塊的索引集,因?yàn)?所以取T=T0就能充分證明該引理.

因?yàn)锳滿足 Block D-RIP條件,不失一般性,假設(shè)存在

使得‖u‖2=‖c‖2=1,因此有

注意到D是一個(gè)緊框架,即DD?=In,故

因此

結(jié)合(6)式,(9)式-(10)式,有

引理得證.

引理2.4令D∈Rn×N為滿足DD?=In的矩陣,測量y=Ax+w,h=，若,則問題(5)的解滿足

將h=?x,y=Ax+w代入上式,由D是一個(gè)緊框架可知

由三角不等式,易知

整理后得(11)式,引理得證.

3 主要結(jié)果

定理 3.1令D∈Rn×N為滿足DD?=In的矩陣,A∈Rm×n為滿足Block DRIP(0<δ2k|τ<0.2)條件的矩陣,(D?x)k為由D?x的k個(gè)最大 2范數(shù)塊組成的向量,測量y=Ax+w,h=?x,若,則問題(5)的解滿足

證明由引理2.1和引理2.4,有

由于 1?3β2>0(0<δ2k|τ<0.2),故

由 (8)式和 (14)式,有

由(13)式-(15)式知,(12)式成立.

4 數(shù)值實(shí)驗(yàn)

為了驗(yàn)證理論結(jié)果,本文分別做了兩組實(shí)驗(yàn):(a)設(shè)計(jì)滿足定理3.1條件的算法;(b)理論誤差上界對(duì)比實(shí)驗(yàn).實(shí)驗(yàn)在CPU為Inter(R)Core(TM)i3,內(nèi)存為2GB的臺(tái)式電腦上進(jìn)行,運(yùn)行軟件為MATLAB(R2014a).實(shí)驗(yàn)中,測量矩陣A∈R128×256服從標(biāo)準(zhǔn)高斯分布,字典D∈R256×1024由傅里葉變換矩陣和單位矩陣合并而成,并且滿足DD?=In,測量誤差w∈R128服從正態(tài)分布,取正則化參數(shù)λ=1e?3,從而滿足,待重構(gòu)的信號(hào)為x∈R256,在字典D下的塊稀疏信號(hào)α∈R1024中的非零塊位置隨機(jī)產(chǎn)生.為了克服實(shí)驗(yàn)結(jié)果的偶然性,所有實(shí)驗(yàn)將獨(dú)立重復(fù)地進(jìn)行100次.在本文中,將冗余字典和Block-IRLS算法[16-18]相結(jié)合提出D-Block-IRLS算法:輸入:分塊τ={τ1,τ2,···,τd},測量矩陣A,字典D,觀測信號(hào)y,塊稀疏度估計(jì)k.

輸出:重構(gòu)信號(hào)x.

(a)選擇適當(dāng)?shù)膽土P參數(shù)λ(0<λ<1).

(b)初始化迭代向量α(0),使其滿足ADα(0)=y.設(shè)置?0=1.

(c)開始迭代j=0.

(d)通過α(j)解決下面的線性問題

(e)當(dāng)α(j)滿足停機(jī)條件,將Dα(j)作為輸出賦值給x,同時(shí)結(jié)束算法,否則執(zhí)行下一步.

其中,r(α)表示將向量α的分塊取?2范數(shù)后,再由大到小依次排列形成的向量.而r(α)k+1表示向量r(α)的第k+1個(gè)分量值.

(g)j=j+1,并返回到第4步繼續(xù)執(zhí)行.

首先針對(duì)D-Block-IRLS算法,采用兩種分塊形式,均分256塊和非均分256塊.圖1分別研究了均勻分塊和非均勻分塊的情況下通過D-Block-IRLS算法得到的誤差‖?x‖2以及理論誤差上界與塊稀疏度k的關(guān)系.由圖可知,無論是均勻分塊還是非均勻分塊通過D-Block-IRLS算法得到的誤差都遠(yuǎn)小于理論誤差上界,換言之,利用D-Block-IRLS算法來重構(gòu)塊稀疏信號(hào)可以滿足實(shí)驗(yàn)設(shè)計(jì)的需要并且從側(cè)面印證了本文理論分析的正確性.

圖1 D-Block-IRLS算法誤差與理論誤差上界對(duì)比

由文獻(xiàn) [8]知,當(dāng)D∈Rn×N為滿足DD?=In的矩陣,A∈Rm×n為滿足 DRIP(0<δ2k<0.1907)條件的矩陣,(D?x)k為由D?x的k個(gè)最大元素組成的向量,測量

現(xiàn)在分別用塊和非塊的方式來處理塊稀疏信號(hào)α,取

其他參數(shù)保持一致[9].圖2表明,無論是均勻分塊還是非均勻分塊,所獲理論誤差上界都明顯優(yōu)于(16)式的誤差上限.

5 小結(jié)

本文采用?2/?1極小化方法研究了基于冗余緊框架下的塊稀疏信號(hào)的恢復(fù),獲得了該方法魯棒重構(gòu)原始信號(hào)的充分條件和誤差上界估計(jì),所獲結(jié)果表明,誤差上界可以通過正則化參數(shù)λ,k-項(xiàng)逼近和塊稀疏度來控制.仿真實(shí)驗(yàn)證明了理論結(jié)果的準(zhǔn)確性,該結(jié)果對(duì)于推動(dòng)壓縮感知的進(jìn)一步發(fā)展具有一定的理論價(jià)值和借鑒作用.