陳 暄 潘春平 龍 丹
1(浙江工業(yè)職業(yè)技術(shù)學(xué)院 浙江 紹興 312000)2(浙江大學(xué) 浙江 杭州 310058)
隨著無線傳感網(wǎng)中技術(shù)的快速發(fā)展,早期使用Nyquist處理信號的方法由于其存在效率低、資源消耗高和硬件成本昂貴等缺點(diǎn)已經(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ù)最小的貪婪算法。前者計(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ù)的壓縮感知平面近場聲全息法,實(shí)驗(yàn)說明算法具有較好的效果,但存在需要在感知矩陣、全息面測量聲壓和稀疏向量共同構(gòu)成的約束條件下才能建立模型的問題,提高了計(jì)算量。文獻(xiàn)[15]提出采用新的近似l0范數(shù)的函數(shù),并結(jié)合牛頓算法實(shí)現(xiàn)圖像重構(gòu),取得了較好的效果,但是沒有對采用簡單的分式函數(shù)近似估計(jì)l0范數(shù)進(jìn)行證明。文獻(xiàn)[16]在分塊圖像中使用l1范數(shù)來估計(jì)混合高斯脈沖噪聲,取得了較好的結(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)行比較,實(shí)驗(yà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ù),重點(diǎn)分析和證明了該逼近函數(shù)的單調(diào)性和最優(yōu)解序列的收斂性。最后通過該平滑漸進(jìn)近函數(shù)求解信號重構(gòu)問題。
一般來說,求解壓縮傳感的信號重構(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ò)大,造成計(jì)算速度慢,重構(gòu)效果差的問題。
定義1當(dāng)x∈RN,t>0,則:
(3)
證明過程如下:
(4)
對于任意的x和t而言:
(5)
因?yàn)椋?/p>
F(x)+0=F(x)
(6)
式(6)化簡為:
(7)
證明完畢。
通過定理1可以將式(1)改寫為如下:
minFt(x)
(8)
s.t.Ax=y(t→+∞)
當(dāng)具有連續(xù)的實(shí)數(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是一個凸問題。
因?yàn)?
Ft(x)+▽Ft(x)TΔx
(13)
所以,Ft(x)在D上是凸函數(shù),而實(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)
因?yàn)楱?Ft(x)為對角矩陣,因此得到:
(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,測量值y,閾值ε為10-6,步長h;
步驟3令tk=t0+kh,求解式(9)的最優(yōu)解x*(tk);
設(shè)定:
表1 數(shù)值結(jié)果
續(xù)表1
表2 數(shù)值結(jié)果
圖1 原始信號
圖2 頻域信號
圖3 本文算法重構(gòu)
3.2.1 經(jīng)典的壓縮算法對比
圖4 運(yùn)行時間對比
圖5 迭代次數(shù)對比
圖6 信躁比對比
圖7 重構(gòu)概率對比
3.2.2 與l1范數(shù)算法比較
為了進(jìn)一步驗(yàn)證本文算法的性能,將本文算法和最新的幾種關(guān)于l1范數(shù)算法(算法所需要的參數(shù)遵循各自文獻(xiàn)中的參數(shù))進(jìn)行對比, 在統(tǒng)一的壓縮比下,比較效果如圖8所示。在圖8(a)中可以發(fā)現(xiàn),本文算法率先完成圖像信號的匹配度,這說明本文算法的性能確實(shí)有了很大的提高。(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種算法對比效果比較
針對最小l1范數(shù)不可導(dǎo)的問題,提出并構(gòu)造了基于平滑漸進(jìn)的l1范數(shù)函數(shù)。通過一系列證明推理說明該函數(shù)具有漸近的單調(diào)性和最優(yōu)解序列收斂性,從而進(jìn)一步說明了本文算法能夠在一定程度改進(jìn)信號重構(gòu)效果。