李 坤 王會敏

(紹興文理學(xué)院 數(shù)理信息學(xué)院，浙江 紹興 312000)

0 引言

壓縮感知是Donoho[1]和Candese等[2]提出的一種新采樣理論，該理論指出可壓縮的信號可通過遠低于Nyquist-Shannon Sampling Theorem[3]的標(biāo)準(zhǔn)進行采樣，原始信號仍然能夠被精確地恢復(fù).在壓縮感知中，利用一個觀測矩陣對高維信號進行線性壓縮觀測得到少數(shù)的觀測值，進而形成線性觀測模型，根據(jù)少數(shù)的觀測值和已知的觀測矩陣，通過構(gòu)造和求解有效的優(yōu)化問題，最終實現(xiàn)精確或者是高概率地重構(gòu)原始信號.當(dāng)原始的高維信號是稀疏信號，即信號的非零元素的個數(shù)遠遠小于信號的維數(shù)時，可以顯著減少估計所需的測量數(shù)量.

現(xiàn)實世界中自然信號的結(jié)構(gòu)千變?nèi)f化，常見的稀疏結(jié)構(gòu)有塊稀疏[4-5]、圖稀疏[6]、樹稀疏[7]等.其中最為普遍的是塊稀疏信號，該信號的非零元素以塊的形式出現(xiàn).現(xiàn)有研究表明，充分利用塊稀疏結(jié)構(gòu)，可以進一步降低壓縮感知中的數(shù)據(jù)采樣率，提高數(shù)據(jù)重構(gòu)效率.近年來，塊稀疏信號的應(yīng)用涉及多個領(lǐng)域，包括DNA微陣列[8]、稀疏通信均衡通道[9]、雷達成像[10]、腦磁圖、多寬帶信號[11]、數(shù)據(jù)挖掘、糾錯編碼等領(lǐng)域.

許多研究表明，在處理塊稀疏信號時，混合l2/l1范數(shù)最小化的方法優(yōu)于標(biāo)準(zhǔn)的l1范數(shù)最小化.Huang等[12]利用一個稱為強群稀疏性的概念發(fā)展了混合l2/l1范數(shù)最小化的理論，證明了混合l2/l1范數(shù)最小化對于恢復(fù)強群稀疏信號是非常有效的.Stojnic等[13]通過混合l2/l1范數(shù)最小化得到了恢復(fù)塊稀疏信號的最優(yōu)高斯測量值.Eldar等[14]表明，在l1范數(shù)情況下，如果測量矩陣有相同的有限等距常數(shù)，那么在無噪聲的情況下，混合l2/l1范數(shù)方法可以完全恢復(fù)任何塊稀疏信號.

本文基于混合l2/l1范數(shù)最小化，考慮了觀測模型y=Φx+ξ+d，其中Φ是高斯矩陣，‖ξ‖2,0≤ηm，得到稀疏噪聲和有界噪聲兩個結(jié)果：

1 預(yù)備知識

設(shè)Φ∈Rm×n是一個高斯矩陣，y∈Rm為觀測值，x∈Rn是塊稀疏向量.設(shè)I={d1,d2,...,dn} 是分塊指標(biāo)集，向量x∈Rn的結(jié)構(gòu)如下

(1.1)

其中card(S)表示S包含的塊數(shù)，則矩陣Φ∈Rm×n對U?Rn具有(η,b)魯棒性.

2 主要結(jié)果

在測量矩陣Φ一定的條件下，有唯一一個塊稀疏信號服從y=Φx，可以通過求解混合l2/l1范數(shù)最小化問題：

(2.1)

如果測量值y有損壞，(2.1)變成了以下噪聲版本：

(2.2)

其中ε表示噪聲誤差.與標(biāo)準(zhǔn)的l0范數(shù)最小化問題類似，(2.2)是混合l2/l0范數(shù)最小化問題，是NP-hard問題.基于壓縮感知的研究，通常使用混合l2/l1范數(shù)代替混合l2/l0范數(shù)，求解混合l2/l1范數(shù)最小化問題.

(2.3)

(2.3)是一個凸優(yōu)化問題，可以重新定義為一個凸二階錐來有效地求解.

本文在以上基礎(chǔ)考慮，若觀測矩陣Φ∈Rm×n是正態(tài)矩陣且獨立同分布.考慮以下觀測模型:

y=Φx+ξ+d

其中，x∈Rn為塊K-稀疏信號，ξ∈Rm為塊-ηm稀疏噪聲向量，d∈Rm為噪聲向量.以下是本文的主要結(jié)果.

3 主要引理及證明

為了證明定理2.1，在[15]引理3.3，引理3.4的基礎(chǔ)上，將k-稀疏信號推廣至塊K-稀疏信號，得到了相關(guān)引理.

引理3.1[15]設(shè)S={z1,...,zm}是通過N(0,1)采樣得到，并且是獨立同分布的，下列不等式

(3.1)

為了做到這一點，首先證明在球面上足夠細的網(wǎng)中，所有塊K-稀疏單位向量以很高的概率滿足(3.1)，對于網(wǎng)外的點，(3.1)偏差不能很大.在引理3.2的基礎(chǔ)上，定義以下事實：令v是一個固定的向量，參數(shù)τ>0，

根據(jù)卡方隨機變量的性質(zhì)，則有:

設(shè)u∈Rn為塊K-稀疏單位向量.對于任何t，存在v0,v1,...,vt與u有相同的塊支集，一個單位向量d也與u有相同的塊支集，于是有:

(3.2)

引理3.2證明了高斯矩陣對塊K-稀疏向量具有魯棒性.本文最終目的是證明高斯矩陣對‖x-x*‖也具有魯棒性.在接下來的引理中，使用參數(shù)，將塊(1+α2)K-稀疏向量的特征值的上界和下界轉(zhuǎn)移到圓錐VS={x∈RN|Δ+‖xS‖2,1≥‖xSC‖2,1}上，其中card(S)=K.

引理3.3 對任意塊(1+α2)K-稀疏向量x，A∈Rm×n滿足L‖x‖2≤‖Ax‖2，1≤U‖x‖2.如果S?[m]，且card(S)=K，則A滿足：

其中x∈VS={x∈RN|Δ+‖xS‖2,1≥‖xSC‖2,1}.

證明：思路是將塊K-稀疏向量上A的特征值轉(zhuǎn)移到VS上A的特征值.為此，首先選擇VS的一個元素，并將其表示為塊稀疏向量的和.對于任何x∈VS記為S，SC劃分為T1,T2,...,TJ，其中Ti對應(yīng)于VSC中第i個最大塊l2范數(shù)的指標(biāo)集.然后每個Ti被分為α2K個塊，對任意i≥1都有‖xTi‖2≥‖xTi+1‖2.

下面證明集合VS中向量特征值的上界和下界.根據(jù)范數(shù)的三角形不等式，有:

由于VS∪T1和VTi至多是塊(1+α2)K-稀疏的，則:

(3.3)

‖xTi‖2≥‖xTi+1‖2，因此

則有:

利用稀疏特征值的界，得到

(3.4)

根據(jù)Ti的定義和柯西-施瓦茨不等式的應(yīng)用，有:

得到‖x‖2的上界:

‖x‖2≤‖xS∪T1‖2+‖x(S∪T1)C‖2

所以:

代入(3.4)，得到

整理‖Ax‖2,1的下界，有:

得到引理:

T?[m]且card(T)≤ηm，則下列不等式:

以1-δ的概率成立.

證明：矩陣Φ對于所有塊(1+α2)K稀疏向量具有(η,1)和(1-η,1)魯棒性.由引理3.3知，對任何矩陣A是由其行的η個分?jǐn)?shù)組成，于是有以下不等式成立:

且矩陣A是Φ的子矩陣，故下列不等式成立:

于是產(chǎn)生以下界限:

通過上述不等式的差值和簡單化，且T?[m]，card(T)≤ηm，得到:

‖(Φx)TC‖2,1-‖(Φx)T‖2,1

≥m‖x‖2((G(η-ε)-B(η+ε)-2ε)-

≥m‖x‖2((G(η-ε)-B(η+ε)-2ε)-

4 主要定理的證明

利用引理3.2，3.3，3.4，開始證明本文的主要定理2.1.

令Φg和Φb分別表示Φ未損壞的行和已損壞的行，yg和yb表示對應(yīng)的y項.由于，‖Φx-y‖2,1=‖Φgx-yg‖2,1+‖Φbx-yb‖2,1，故:

0≥‖Φx*-y‖2,1-‖Φx-y‖2,1

=(‖Φgx*-yg‖2,1-‖Φgx-yg‖2,1)+

(‖Φbx*-yb‖2,1-‖Φbx-yb‖2,1)

≥‖Φg(x*-x)‖2,1-2‖Φgx-yg‖2,1+

(‖Φbx*-yb‖2,1-‖Φbx-yb‖2,1)

≥‖Φg(x*-x)‖2,1-2‖Φgx-yg‖2,1-

‖Φb(x*-x)‖2,1

(4.1)

上述式子化簡為:

2‖Φgx-yg‖2,1≥‖Φg(x*-x)‖2,1-

‖Φb(x*-x)‖2,1

(4.2)

令x*=x+h， 且假設(shè)S是x的塊支集， 則

λ≥‖x*‖2,1=‖h+x‖2,1≥‖x‖2,1+‖hSC‖2,1-‖hS‖2,1，于是有(λ-‖x‖2,1)+‖hS‖2,1≥‖hSC‖2,1.

令Δ=(λ-‖x‖2,1)，T是引理3.4中已損壞數(shù)據(jù)指數(shù)的集合， 這意味著如果

也就是:

得到的結(jié)果:

當(dāng)x不是稀疏信號時，由(4.2)直接利用引理3.2即可得到定理2.2.

5 總結(jié)

對于塊稀疏向量，可以在不知道原始信號中非零系數(shù)的位置坐標(biāo)的情況下精確地恢復(fù)原始信號，重構(gòu)過程更簡單、更準(zhǔn)確.本文利用高斯矩陣的性質(zhì)得到了塊K-稀疏信號最小恢復(fù)誤差.若信號含有有界噪聲，可直接得到‖Φx‖2,1的上下界；若信號含有塊稀疏噪聲，需要將x限制在錐VS={x∈RN|Δ+‖xS‖2,1≥‖xSC‖2,1}上，利用矩陣的塊-RIP性質(zhì)，得到‖Φx‖2,1的上下界.