通過(guò)1-2最小化恢復(fù)信號(hào)的充分條件

武思琪,宋儒瑛

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

0 引言

(1)

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

(2)

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

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

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

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

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

(3)

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

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

(4)

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

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

(5)

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

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

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

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

(6)

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

引理1[5]對(duì)向量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)

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

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

則

(8)

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

引理4[8]當(dāng)k=0，即T=?，x是一個(gè)給定的信號(hào)，滿足|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é)果

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

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

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

(9)

則每個(gè)h-稀疏向量x∈n是

的唯一解.

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

(10)

為了說(shuō)明式(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個(gè)最大絕對(duì)值項(xiàng)的一個(gè)指標(biāo)集S:=S0.現(xiàn)將集合{1,…,n}中S0的補(bǔ)集S0c劃分為S0c=S1∪S2∪…，其中

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

S2：(S0∪S1)c中g(shù)的h個(gè)最大絕對(duì)值項(xiàng)的指標(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é)合起來(lái)，且兩邊同時(shí)除以‖gS0‖2，得到

對(duì)于i≥1，gSi的h個(gè)絕對(duì)值項(xiàng)的大小不超過(guò)gSi-1的h個(gè)絕對(duì)值項(xiàng)的大小，所以由引理2可以推導(dǎo)出

從而得到

由引理4得證.

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

(13)

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

的唯一解.

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

(14)

為了說(shuō)明式(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劃分為T(mén)c=T0∪T1∪…，其中

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

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

?

(15)

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

(16)

對(duì)于i≥1，gTj的h個(gè)絕對(duì)值項(xiàng)的大小不超過(guò)gTj-1的h個(gè)絕對(duì)值項(xiàng)的大小，所以由引理2推導(dǎo)出

從而推出

由引理3得證.

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

(17)

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

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

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

(18)

為了說(shuō)明式(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)，

其中

接下來(lái)的證明過(guò)程依照定理2和備注1即可得證.

3 結(jié)論