武思琪,宋儒瑛

(太原師范學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院，山西 晉中 030619)

0 引言

(1)

其中‖x‖0:=|supp(x)|，其中supp(x)={i:xi≠0}表示x的支撐集或簡稱為支撐；|supp(x)|表示supp(x)的基數(shù)，也就是集合supp(x)中元素的個數(shù).式(1)是最直接的稀疏信號重建方法，但這是一個NP-難問題，計算上是不可行的，因此Candes和Tao[1]想到用1范數(shù)對其松弛，即轉(zhuǎn)化為求解1最小化問題，這將求解0最小化所涉及的多個子問題的優(yōu)化問題轉(zhuǎn)化為凸優(yōu)化問題，從而更容易求解，但其需要更多的測量值.近年來，Yin等人[2]提出了用下面的1-2最小化問題來代替式(1)：

(2)

他們證明了當(dāng)測量矩陣A滿足良好的限制等距性時，式(2)也可以穩(wěn)定和魯棒地恢復(fù)稀疏信號，且1-2最小化方法的性能優(yōu)于包括1最小化方法在內(nèi)現(xiàn)存的其他方法[3,4].

壓縮感知中使用最多的是滿足限制等距性(RIP)的框架，它刻畫了一個矩陣和標(biāo)準(zhǔn)正交矩陣的相似程度.研究證明[5]如果一個矩陣A滿足RIP，那么這就足以使各種算法能夠成功地從噪聲測量值中恢復(fù)稀疏信號.另一個廣泛使用的框架是零空間特性，人們通常利用測量矩陣的零空間特性來建立基于限制等距性的充分條件，從而精確恢復(fù)稀疏信號[6,7].在實際應(yīng)用中，信號恢復(fù)通常會利用自身的先驗支撐信息來提高信號恢復(fù)的效率，文獻(xiàn)已經(jīng)證明了在1-2[3,8]、1[9,10]、p(0

1 預(yù)備知識

首先引入一些定義[5,8]和引理[5,8]來為文章的主要結(jié)果作鋪墊.

定義1[5]對所有h-稀疏信號x∈n(即至多有h個非零項)，若存在一個最小的常數(shù)δh∈(0,1)，使得

(3)

定義2[8]對所有集合S?{1,…,n}(|S|≤h)，若對任意x∈N(A)(N(A)是A的零空間)，且x≠0，使得

‖xS‖1+‖x‖2<‖xSc‖1

(4)

定義3[8]對所有集合T?{1,…,n}(0≤|T|=k

‖xS‖1+‖xTc‖2<‖x(S∪T)c‖1

(5)

注:當(dāng)k=0，即T=?時，定義3是1-2零空間特性.

在更現(xiàn)實的情形中，信號x不是完全稀疏的，但它是一個可壓縮信號(可以由一個稀疏信號很好地逼近).在這種情形中，我們引入部分支集已知的1-2穩(wěn)定零空間特性的定義.

定義4[8]對所有集合T?{1,…,n}(0≤|T|=k

‖xS‖1+‖xTc‖2≤μ‖x(S∪T)c‖1

(6)

成立，其中0<μ<1，則稱矩陣A∈m×n滿足部分支集已知的h階的1-2穩(wěn)定零空間特性(T是已知支撐集).

引理1[5]對向量x,r∈n，其中‖x‖0≤w且‖r‖0≤t，A∈m×n.若supp(x)∩supp(r)=?，且存在常數(shù)δw+t，滿足

|〈Αx,Αr〉|≤δw+t‖x‖2‖r‖2,

(7)

則稱δw+t是w+t階的限制等距常數(shù).

引理2[5]給定q>p>0，對向量x,r∈n，其中‖x‖0≤w且‖r‖0≤t，且supp(x)∩supp(r)=?，滿足

則

(8)

引理3[8]令k是一個給定的正整數(shù)，x是一個給定的信號，滿足|supp(x)|≤h.假設(shè)矩陣A滿足部分支集已知的h階的1-2零空間特性，則x是式(2)的唯一解.

引理4[8]當(dāng)k=0，即T=?，x是一個給定的信號，滿足|supp(x)|≤h.假設(shè)矩陣A滿足h階的1-2零空間特性，則x是式(2)的唯一解.

備注1[8]由于‖xS‖1+‖xTc‖2≤μ‖x(S∪T)c‖1<‖x(S∪T)c‖1，假設(shè)矩陣A滿足部分支集已知的h階的1-2穩(wěn)定零空間特性，則x是式(2)的唯一解.

2 主要結(jié)果

若信號是完全稀疏的，則通過式(2)可以精確恢復(fù)稀疏信號；若信號是不完全稀疏，而是一個可壓縮信號(可以由一個稀疏信號很好地逼近)，則通過式(2)可以穩(wěn)定恢復(fù)信號.

下面給出本文的三個主要定理，分別適用于一般信號精確恢復(fù)、具有部分先驗支撐信息的信號精確恢復(fù)及具有部分先驗支撐信息的信號穩(wěn)定恢復(fù).

定理1假設(shè)矩陣A∈m×n的2h階限制等距常數(shù)滿足

(9)

則每個h-稀疏向量x∈n是

的唯一解.

證明 根據(jù)定義2，對所有g(shù):=v-x∈N(A)和S?{1,…,n}(card(S)=h)，可以建立如下不等式：

(10)

為了說明式(10)，由式(4)得到

‖gS‖1+‖g‖2<‖gSc‖1?

‖gS‖1+‖gS‖1+‖g‖2<‖g‖1?

2‖gS‖1+‖gS‖2+‖gSc‖2<‖g‖1?

這遵從更強(qiáng)的條件：

其中

給定g∈N(A)，考慮向量g的h個最大絕對值項的一個指標(biāo)集S:=S0.現(xiàn)將集合{1,…,n}中S0的補(bǔ)集S0c劃分為S0c=S1∪S2∪…，其中

S1：S0c中g(shù)的h個最大絕對值項的指標(biāo)集；

S2：(S0∪S1)c中g(shù)的h個最大絕對值項的指標(biāo)集；

?

由于g∈N(A)，有Α(gS0)=Α(-gS1-gS2-…)，使得

(11)

根據(jù)引理1，得到

|〈Α(gS0),Α(-gSi)〉|≤δ2h‖gS0‖2‖gSi‖2.

(12)

由于‖gS0‖2>0，現(xiàn)在將式(11)和式(12)結(jié)合起來，且兩邊同時除以‖gS0‖2，得到

對于i≥1，gSi的h個絕對值項的大小不超過gSi-1的h個絕對值項的大小，所以由引理2可以推導(dǎo)出

從而得到

由引理4得證.

定理2假設(shè)矩陣A∈m×n的2h+k階限制等距常數(shù)滿足

(13)

則每個具有部分已知支撐集T的h-稀疏向量x∈n(card(T)=k

的唯一解.

證明 根據(jù)定義3，對所有g(shù):=v-x∈N(A)和S?{1,…,n}(card(S)=h)，可以建立如下不等式：

(14)

為了說明式(14)，由式(5)得到

‖gS‖1+‖gTc‖2<‖g(S∪T)c‖1?

‖gS‖1+‖gTc‖2+‖gS∪T‖1<‖g‖1?

這遵從更強(qiáng)的條件：

和

T?{1,…,n}(card(S)=h,card(T)=k)，

其中

給定g∈N(A)，T為向量g的部分已知支撐集.現(xiàn)將集合{1,…,n}中T的補(bǔ)集Tc劃分為Tc=T0∪T1∪…，其中

T0：Tc中g(shù)的h個最大絕對值項的指標(biāo)集；

T1：(T∪T0)c中g(shù)的h個最大絕對值項的指標(biāo)集；

?

(15)

根據(jù)引理1，得到

(16)

對于i≥1，gTj的h個絕對值項的大小不超過gTj-1的h個絕對值項的大小，所以由引理2推導(dǎo)出

從而推出

由引理3得證.

定理3假設(shè)矩陣A∈m×n的2h+k階限制等距常數(shù)滿足

(17)

則每個具有部分已知支撐集T的h-稀疏向量x∈n(card(T)=k

穩(wěn)定恢復(fù).

證明 根據(jù)定義4，對所有g(shù):=v-x∈N(A)和S?{1,…,n}(card(S)=h)，可以建立如下不等式：

(18)

為了說明式(18)，由式(6)得到

‖gS‖1+‖gTc‖2≤μ‖g(S∪T)c‖1?

‖gS‖1+‖gTc‖2+μ‖gS∪T‖1≤μ‖g‖1?

其中0<μ<1.

這遵從更強(qiáng)的條件：

和

T?{1,…,n}(card(S)=h,card(T)=k)，

其中

接下來的證明過程依照定理2和備注1即可得證.

3 結(jié)論