李 坤 王會(huì)敏

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

0 引言

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

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

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

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

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

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

(1.1)

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

2 主要結(jié)果

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

(2.1)

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

(2.2)

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

(2.3)

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

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

y=Φx+ξ+d

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

3 主要引理及證明

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

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

(3.1)

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

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

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

(3.2)

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

引理3.3 對(duì)任意塊(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的一個(gè)元素，并將其表示為塊稀疏向量的和.對(duì)于任何x∈VS記為S，SC劃分為T1,T2,...,TJ，其中Ti對(duì)應(yīng)于VSC中第i個(gè)最大塊l2范數(shù)的指標(biāo)集.然后每個(gè)Ti被分為α2K個(gè)塊，對(duì)任意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-δ的概率成立.

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

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

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

通過(guò)上述不等式的差值和簡(jiǎ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表示對(duì)應(yīng)的y項(xiàng).由于，‖Φ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)

上述式子化簡(jiǎn)為:

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不是稀疏信號(hào)時(shí)，由(4.2)直接利用引理3.2即可得到定理2.2.

5 總結(jié)

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