通過混合l2/l1范數最小化實現塊稀疏信號恢復

李 坤 王會敏

(紹興文理學院 數理信息學院，浙江 紹興 312000)

0 引言

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

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

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

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

1 預備知識

設Φ∈Rm×n是一個高斯矩陣，y∈Rm為觀測值，x∈Rn是塊稀疏向量.設I={d1,d2,...,dn} 是分塊指標集，向量x∈Rn的結構如下

(1.1)

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

2 主要結果

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

(2.1)

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

(2.2)

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

(2.3)

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

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

y=Φx+ξ+d

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

3 主要引理及證明

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

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

(3.1)

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

根據卡方隨機變量的性質，則有:

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

(3.2)

引理3.2證明了高斯矩陣對塊K-稀疏向量具有魯棒性.本文最終目的是證明高斯矩陣對‖x-x*‖也具有魯棒性.在接下來的引理中，使用參數，將塊(1+α2)K-稀疏向量的特征值的上界和下界轉移到圓錐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的特征值轉移到VS上A的特征值.為此，首先選擇VS的一個元素，并將其表示為塊稀疏向量的和.對于任何x∈VS記為S，SC劃分為T1,T2,...,TJ，其中Ti對應于VSC中第i個最大塊l2范數的指標集.然后每個Ti被分為α2K個塊，對任意i≥1都有‖xTi‖2≥‖xTi+1‖2.

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

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

(3.3)

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

則有:

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

(3.4)

根據Ti的定義和柯西-施瓦茨不等式的應用，有:

得到‖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是由其行的η個分數組成，于是有以下不等式成立:

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

于是產生以下界限:

通過上述不等式的差值和簡單化，且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項.由于，‖Φ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， 且假設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中已損壞數據指數的集合， 這意味著如果

也就是:

得到的結果:

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

5 總結

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