基于l1-l2范數(shù)極小化的稀疏信號重建條件

周 珺, 黃 尉

(合肥工業(yè)大學(xué) 數(shù)學(xué)學(xué)院,安徽 合肥 230601)

0 引 言

壓縮感知(compressed sensing,CS)是由Donoho、Candes、陶哲軒等人首先提出的一種新型的采樣理論[1-2],主要是利用信號的先驗(yàn)信息,考慮從較少的線性測量中恢復(fù)高維稀疏信號。一般考慮以下模型:

y=Aβ+z

(1)

其中,A∈Rn×m(n?m)為測量矩陣;z∈Rn為測量誤差。壓縮感知的目標(biāo)是基于y和A重建未知信號β∈Rm。值得注意的是,假設(shè)信號是稀疏的,在無噪情形下,若測量矩陣A滿足一定條件,則未知信號β可以被準(zhǔn)確恢復(fù)。

為了解決上述問題,一個自然的想法就是采用l0最小化去找到滿足Aβ=y可行解集合中最稀疏的解,但這是一個非凸和NP-難的問題,計算上是不可行的。因此,人們想到對l0最小化進(jìn)行凸松弛,利用l1最小化方法來解決上述問題, 即

(2)

特別地,與l1范數(shù)相比,l1-l2范數(shù)更接近l0范數(shù),從理論上說,l1-l2最小化模型優(yōu)于l1最小化模型[3-4]。因此,本文考慮用l1-l2極小化方法從欠定的線性測量中重建信號,現(xiàn)考慮如下約束優(yōu)化問題:

(3)

其中,B為取決于噪聲的類型。特別地,在無噪聲情形下(B={0})有:

(4)

其中, (3)式和(4)式是本文主要的研究模型。

本文主要研究了若測量矩陣A滿足一定條件,則通過l1-l2極小化方法可以使k-稀疏信號精確恢復(fù)。此條件弱于文獻(xiàn)[4]中給出的2k階限制等距性質(zhì)(restricted isometry property,RIP)條件。

1 預(yù)備知識

RIP由文獻(xiàn)[1]首先提出,是壓縮感知中使用最多的框架,主要是刻畫一個矩陣和標(biāo)準(zhǔn)正交矩陣的相似程度。

定義1(RIP)[1]假設(shè)A∈Rn×m是一個測量矩陣,1≤k≤m是一個整數(shù),若存在一個常數(shù)δk(0≤δk<1),對任意k-稀疏信號β,滿足:

(5)

則稱矩陣A滿足k階RIP。若δk是對每個k-稀疏信號均滿足(5)式的最小非負(fù)數(shù),則稱δk為k階限制等距常數(shù)(restricted isometry constant,RIC)。

定義2(ROC)[5]假設(shè)A∈Rn×m是一個測量矩陣,定義(k1,k2)階限制正交常數(shù)(restricted orthogonal constant,ROC)為最小非負(fù)數(shù)θk1,k2,使得對任意具有不相交支撐集的k1-稀疏矢量β1和k2-稀疏矢量β2滿足:

|〈Aβ1,Αβ2〉|≤θk1,k2‖β1‖2‖β2‖2。

引理1[6]令k1、k2≤m且λ≥0,假設(shè)信號β1、β2∈Rm有不相交支撐集,β1是k1-稀疏矢量,β2滿足‖β2‖1≤λk2且‖β2‖∞≤λ,則有:

顯然,引理1是對ROC定義的一般性推廣。

定義3[3]若矢量x∈Rm,則定義矢量x的最佳k項(xiàng)近似誤差為:

2 主要結(jié)論

2.1 稀疏信號的重建

定理1若信號β是k-稀疏的,測量矩陣A∈Rn×m滿足:

(6)

Ti={pl:(i-1)k+1≤l≤ik},

因此

特別地,

故

移項(xiàng)整理得:

(7)

又因?yàn)?/p>

|〈AhT01,AhTj〉|≤

因此

于是有:

|〈Ah,AhT01〉|≥|〈AhT01,AhT01〉|-

(8)

因?yàn)锳h=0,所以由(7)式和(8)式有:

假設(shè)信號β不是k-稀疏的,現(xiàn)考慮如下2種類型的噪聲情形:

(1)Bl2(ε)={z:‖z‖2≤ε}。

(2)BDS(ε)={z:‖ATz‖∞≤ε}。

定理2 若測量矩陣A∈Rn×m滿足:

證明(1) 證明Bl2(η)={z∈Rn:‖z‖2≤η}。證明過程與定理1相似,不同之處如下:

|〈Ah,AhT01〉|≤‖Ah‖2‖AhT01‖2≤

其他過程與定理1相同,可得:

‖hT01‖2≤

(9)

由(7)式和(9)式得:

(2) 證明BDS(η)={z∈Rn:‖ATz‖∞≤η} 。類似地,

且

(10)

由(7)式和(10)式得:

2.2 高斯噪聲情形

高斯噪聲情形作為一種特殊情形被很多學(xué)者關(guān)注[8-9],其觀察模型為:

y=Aβ+z,z～N(0,σ2In)。

假設(shè)σ是已知的,矩陣A中的列向量均為單位向量,定義如下2個噪聲類型:

則分別對應(yīng)有[9]:

這表明高斯變量z以高概率處于集合B1和B2中。顯然,由定理2可給出如下定理。

定理3若測量矩陣A∈Rn×m滿足:

則有如下結(jié)論:

3 結(jié) 論

本文主要考慮從很少的線性測量信號中恢復(fù)稀疏信號,基于RIP框架,得到了通過l1-l2極小化方法精確恢復(fù)稀疏信號的一個充分條件,同時,給出了有噪聲情形下的誤差估計。