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

陳 暄 潘春平 龍 丹

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

0 引 言

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

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

1 預(yù)備知識

一般來說，求解壓縮傳感的信號重構(gòu)的時候,采用求解最小的l0范數(shù)問題,思路如下:

(1)

s.t.Ax=y

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

(2)

s.t.Ax=y

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

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

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

(3)

證明過程如下:

(4)

對于任意的x和t而言：

(5)

因為：

F(x)+0=F(x)

(6)

式(6)化簡為:

(7)

證明完畢。

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

minFt(x)

(8)

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

當(dāng)具有連續(xù)的實數(shù)時,式(5)的求解非常難?？梢酝ㄟ^離散化t得到:

minFt(x)

(9)

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

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

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

證明如下：

因此得到：

(10)

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

(11)

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

證明如下:假設(shè)集合D={x|Ax=y},其中,A是一個N×M矩陣,x∈RN,y∈RM對于?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是一個凸問題。

因為:

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

(13)

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

RN×M是一個正定矩陣。

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

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

(14)

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

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*,同時結(jié)合一階求導(dǎo)必要條件,得到:

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

(16)

因為▽2Ft(x)為對角矩陣,因此得到:

(17)

又因為Ft(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,測量值y,閾值ε為10-6,步長h；

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

3 實驗說明

3.1 算法實例說明及重構(gòu)效果對比

設(shè)定：

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

續(xù)表1

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

圖1 原始信號

圖2 頻域信號

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

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

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

圖4 運(yùn)行時間對比

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

圖6 信躁比對比

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

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

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

(a) 匹配度比較

(b) 相對誤差比較

(c) 峰值信躁比PSNR比較

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

4 結(jié) 語

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