基于平滑漸進(jìn)l1范數(shù)的壓縮感知信號(hào)的重構(gòu)算法

陳 暄 潘春平 龍 丹

1(浙江工業(yè)職業(yè)技術(shù)學(xué)院 浙江 紹興 312000)2(浙江大學(xué) 浙江 杭州 310058)

0 引 言

隨著無(wú)線傳感網(wǎng)中技術(shù)的快速發(fā)展，早期使用Nyquist處理信號(hào)的方法由于其存在效率低、資源消耗高和硬件成本昂貴等缺點(diǎn)已經(jīng)被放棄[1-2]。壓縮感知CS(Compressed Sensing)[3-5]理論能夠采用遠(yuǎn)低于Nyquist采樣條件，使用隨機(jī)方法獲得離散樣本。該理論已經(jīng)廣泛地使用在信息論、地球科學(xué)、無(wú)線通信和模式識(shí)別等領(lǐng)域。CS中的信號(hào)重構(gòu)是恢復(fù)原始信號(hào)的關(guān)鍵。目前常見(jiàn)的信號(hào)重構(gòu)算法主要分為基于l1范數(shù)的最小凸優(yōu)化算法和基于l0范數(shù)最小的貪婪算法。前者計(jì)算量比較龐大,但重建效果好,其代表有：基追蹤法BP(Basis Pursuit)[6]、梯度投影法GPSR(Gradient Projection For Sparse)[7]、凸集交替投影法POCS(Projection Onto Convex Sets)[8]、同倫算法HA(Homotopy Algorithm)[9]和最小角度回歸法LARS(Least Angle Regression)[10]等。后者具有精度差、計(jì)算速度快的特點(diǎn),其代表有：匹配追蹤法MP(Matching Pursuit)[11]、正交匹配追蹤法OMP(Orthogonal Matching Pursuit)[12]、分段正交匹配追蹤法STOMP(Stagewise Orthogonal Orthogonal Matching Pursuit)[13]等。文獻(xiàn)[14]提出基于平滑l0范數(shù)的壓縮感知平面近場(chǎng)聲全息法,實(shí)驗(yàn)說(shuō)明算法具有較好的效果，但存在需要在感知矩陣、全息面測(cè)量聲壓和稀疏向量共同構(gòu)成的約束條件下才能建立模型的問(wèn)題，提高了計(jì)算量。文獻(xiàn)[15]提出采用新的近似l0范數(shù)的函數(shù),并結(jié)合牛頓算法實(shí)現(xiàn)圖像重構(gòu)，取得了較好的效果，但是沒(méi)有對(duì)采用簡(jiǎn)單的分式函數(shù)近似估計(jì)l0范數(shù)進(jìn)行證明。文獻(xiàn)[16]在分塊圖像中使用l1范數(shù)來(lái)估計(jì)混合高斯脈沖噪聲，取得了較好的結(jié)果，但提高了算法復(fù)雜度，去躁效果不明顯。文獻(xiàn)[17]提出在l1范數(shù)中的基于柔化神經(jīng)網(wǎng)絡(luò)的低秩矩陣分解方法,該方法能夠有效降低噪聲比，但算法消耗了更多的時(shí)間。文獻(xiàn)[18]提出了基于l1和l2范數(shù)的稀疏重構(gòu)算法用于稀疏模型重構(gòu)，取得的較好的效果，但沒(méi)有與其他重構(gòu)算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果稍顯不足。文獻(xiàn)[19]提出了基于l1范數(shù)的圖像分辨算法，提高了圖像清晰度，但增加了算法的復(fù)雜度。

綜上所述，壓縮傳感中信號(hào)重構(gòu)最理想的方法是采用基于最小l0范數(shù)的重構(gòu),這是一個(gè)NP問(wèn)題。因此轉(zhuǎn)換為求解l1最小范數(shù)問(wèn)題來(lái)進(jìn)行解決,但是由于最小l1范數(shù)并不是可導(dǎo)的,影響重構(gòu)的效果。本文構(gòu)造了基于l1范數(shù)的光滑逼近函數(shù),重點(diǎn)分析和證明了該逼近函數(shù)的單調(diào)性和最優(yōu)解序列的收斂性。最后通過(guò)該平滑漸進(jìn)近函數(shù)求解信號(hào)重構(gòu)問(wèn)題。

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

一般來(lái)說(shuō)，求解壓縮傳感的信號(hào)重構(gòu)的時(shí)候,采用求解最小的l0范數(shù)問(wèn)題,思路如下:

(1)

s.t.Ax=y

文獻(xiàn)[20-21]證明了基于最小的l0范數(shù)進(jìn)行信號(hào)重構(gòu)等價(jià)于使用求解最小l1范數(shù)的信號(hào)重構(gòu)。因此通常采用求解最小l1范數(shù)問(wèn)題去解決信號(hào)重構(gòu)的問(wèn)題,因此模型如下:

(2)

s.t.Ax=y

顯然,式(2)是一個(gè)凸規(guī)劃問(wèn)題[22]。雖然可以轉(zhuǎn)換為線性規(guī)劃問(wèn)題，但存在求解過(guò)程規(guī)模擴(kuò)大，造成計(jì)算速度慢，重構(gòu)效果差的問(wèn)題。

2 基于平滑漸進(jìn)的l1范數(shù)信號(hào)重構(gòu)算法研究

定義1當(dāng)x∈RN,t>0,則:

(3)

證明過(guò)程如下:

(4)

對(duì)于任意的x和t而言：

(5)

因?yàn)椋?/p>

F(x)+0=F(x)

(6)

式(6)化簡(jiǎn)為:

(7)

證明完畢。

通過(guò)定理1可以將式(1)改寫(xiě)為如下:

minFt(x)

(8)

s.t.Ax=y(t→+∞)

當(dāng)具有連續(xù)的實(shí)數(shù)時(shí),式(5)的求解非常難。可以通過(guò)離散化t得到:

minFt(x)

(9)

s.t.Ax=y(tk→+∞)

能夠求解該公式是否成立，是本文所需要描述的主要對(duì)象。

定理2存在集合S={x|Ft(x)≤Fk(x)}具有一定的界限,當(dāng)x*(tk)是t=tk時(shí),式(9)獲得最優(yōu)解,所以x*就是式(1)的最優(yōu)解,因此在{x*(tk)}中存在子序列收斂于x*。

證明如下：

因此得到：

(10)

所以,對(duì)于?i≥max{I1,I2}存在:

(11)

定理3式(9)是一個(gè)凸規(guī)劃問(wèn)題。

證明如下:假設(shè)集合D={x|Ax=y},其中,A是一個(gè)N×M矩陣,x∈RN,y∈RM對(duì)于?x(1),x(2)∈D并且?λ∈[0,1]

A[λx(1)+(1-λ)x(2)]=λAx(1)+(1-λ)Ax(2)=

λy+(1-λ)y=y

(12)

因此,λx(1)+(1+λ)x(2)∈D

所以,D是一個(gè)凸問(wèn)題。

因?yàn)?

Ft(x)+▽Ft(x)TΔx

(13)

所以,Ft(x)在D上是凸函數(shù),而實(shí)際上：

RN×M是一個(gè)正定矩陣。

所以,Ft(x) 在D上是嚴(yán)格凸函數(shù),證明完畢。

定理4假設(shè)x*(tk)是t=tk的式(1)的最優(yōu)解,x*是式(2)的全局最優(yōu)解,因此,對(duì)于任何一個(gè)tk>0且k→+∞,則有:

(14)

證明:選擇目標(biāo)函數(shù)Ft(x)在x=x*(tk)處的泰勒展開(kāi)為:

Ft(x)=Ft(x*(tk))+▽Ft(x*(tk))T(x-x*(tk))+

▽Ft(x*(tk))(x-x*(tk))+

o(x-x*(tk))T(x-x*(tk))

(15)

令x=x*,同時(shí)結(jié)合一階求導(dǎo)必要條件,得到:

o(x-x*(tk))T(x-x*(tk))

(16)

因?yàn)楱?Ft(x)為對(duì)角矩陣,因此得到:

(17)

又因?yàn)镕t(x)關(guān)于t進(jìn)行單調(diào)遞減,因此得到Ft(x*(tk))-Ft+1(x*(tk))<0,由于x*是式(2)的全局最優(yōu)解,因此得到Ft(x)-Ft(x*(tk))<0。

F(x*(tk)+F(x*(tk)-Ft(x*(tk)))≤

(18)

證明完畢。

綜上所述，根據(jù)定理2,求解式(9)的算法如下:

步驟1輸入矩陣A和t0,測(cè)量值y,閾值ε為10-6,步長(zhǎng)h；

步驟3令tk=t0+kh,求解式(9)的最優(yōu)解x*(tk)；

3 實(shí)驗(yàn)說(shuō)明

3.1 算法實(shí)例說(shuō)明及重構(gòu)效果對(duì)比

設(shè)定：

表1 數(shù)值結(jié)果

續(xù)表1

表2 數(shù)值結(jié)果

圖1 原始信號(hào)

圖2 頻域信號(hào)

圖3 本文算法重構(gòu)

3.2 本文算法與其他重構(gòu)算法的對(duì)比

3.2.1 經(jīng)典的壓縮算法對(duì)比

圖4 運(yùn)行時(shí)間對(duì)比

圖5 迭代次數(shù)對(duì)比

圖6 信躁比對(duì)比

圖7 重構(gòu)概率對(duì)比

3.2.2 與l1范數(shù)算法比較

為了進(jìn)一步驗(yàn)證本文算法的性能,將本文算法和最新的幾種關(guān)于l1范數(shù)算法(算法所需要的參數(shù)遵循各自文獻(xiàn)中的參數(shù))進(jìn)行對(duì)比, 在統(tǒng)一的壓縮比下，比較效果如圖8所示。在圖8(a)中可以發(fā)現(xiàn)，本文算法率先完成圖像信號(hào)的匹配度,這說(shuō)明本文算法的性能確實(shí)有了很大的提高。(b)中發(fā)現(xiàn)，本文算法的相對(duì)誤差明顯小于其他3種算法,這說(shuō)明算法的自身的精度高,降低了誤差比例。(c)的PSNR的值是4種算法中最高的,進(jìn)一步說(shuō)明了本文算法的重構(gòu)效率是良好的。從(d)中的運(yùn)行時(shí)間來(lái)看,4種算法的運(yùn)行時(shí)間都有不同程度的增加,但從整體上看本文算法的運(yùn)行時(shí)間要稍微優(yōu)于其他3種算法。

(a) 匹配度比較

(b) 相對(duì)誤差比較

(c) 峰值信躁比PSNR比較

(d) 運(yùn)行時(shí)間比較圖8 4種算法對(duì)比效果比較

4 結(jié) 語(yǔ)

針對(duì)最小l1范數(shù)不可導(dǎo)的問(wèn)題,提出并構(gòu)造了基于平滑漸進(jìn)的l1范數(shù)函數(shù)。通過(guò)一系列證明推理說(shuō)明該函數(shù)具有漸近的單調(diào)性和最優(yōu)解序列收斂性,從而進(jìn)一步說(shuō)明了本文算法能夠在一定程度改進(jìn)信號(hào)重構(gòu)效果。