郭 曉,李向利

基于NSGPBB算法的壓縮感知稀疏信號(hào)重構(gòu)

郭 曉,李向利

(桂林電子科技大學(xué)數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,廣西桂林 541004)

為了更好地重構(gòu)原始信號(hào),提出一種帶有交替BB步長(zhǎng)的非單調(diào)梯度投影算法(NSGPBB)。將無約束凸優(yōu)化問題轉(zhuǎn)化為在閉凸集上的邊界約束二次規(guī)劃問題,并證明了該算法的收斂性。數(shù)值實(shí)驗(yàn)結(jié)果表明,該算法是有效的,且收斂速度快于梯度投影算法。

壓縮感知;譜梯度投影算法;稀疏重構(gòu);二次規(guī)劃;交替BB步長(zhǎng)

其中:x∈Rn為原始信號(hào),在正交基下可稀疏或可壓縮;y∈Rm為低維測(cè)量向量;τ為非負(fù)參數(shù);‖x‖1=

在壓縮感知[1]中,一般考慮無約束凸優(yōu)化問題:為L(zhǎng) 1范數(shù);‖·‖2為Euclidean范數(shù);A為m ×n(m?n)感知矩陣,A=ΦΨ,隨機(jī)觀測(cè)矩陣Φ為m ×n隨機(jī)高斯矩陣,Ψ為n×n正交變換基矩陣。當(dāng)y包含噪聲或x僅僅可壓縮但不精確稀疏時(shí),測(cè)量向量y=Ax+ζ,ζ為高斯白噪聲。在一定條件下,式(1)可等價(jià)于以下2個(gè)凸約束優(yōu)化問題:

其中ξ、ζ為非負(fù)實(shí)參數(shù)。式(2)為二次約束線性規(guī)劃問題,式(3)為二次規(guī)劃問題。

為了求解以上優(yōu)化問題,近年來學(xué)者們提出了許多相關(guān)算法,如稀疏重構(gòu)梯度投影(GPSR)算法[2],內(nèi)點(diǎn)(IP)算法[3],迭代壓縮/閾值化(IST)算法[4],同倫(HM)算法[5]以及加權(quán)最小L1范數(shù)法[6]等。在信號(hào)處理中,這些算法都能有效地恢復(fù)信號(hào)。

譜梯度投影(SPG)算法[7]是求解邊界約束優(yōu)化問題的有效方法,并已應(yīng)用于問題(3)。文獻(xiàn)[8]提出了一種求解無約束優(yōu)化問題的非單調(diào)Wolfe線搜索算法,該算法具有較好的數(shù)值效果。文獻(xiàn)[9]利用文獻(xiàn)[8]中的非單調(diào)Wolfe線搜索給出了求解邊界約束優(yōu)化問題的梯度投影(NSPG)算法。文獻(xiàn)[10]證明了交替使用BB步長(zhǎng)[11]比單獨(dú)使用某一個(gè)BB步長(zhǎng)的數(shù)值效果更好。鑒于此,結(jié)合非單調(diào)Wolfe線搜索和交替BB步長(zhǎng),提出一種新的梯度投影算法,并將該算法應(yīng)用到恢復(fù)稀疏信號(hào)中。

1 壓縮感知信號(hào)重構(gòu)模型與算法

1.1 邊界約束二次規(guī)劃(BCQP)模型

受文獻(xiàn)[12]的啟發(fā),為了更方便地求解問題(1),將其轉(zhuǎn)化為一個(gè)閉凸集上的二次規(guī)劃問題。將向量x分解為正負(fù)2部分,即x=u-v,u≥0,v≥0。向量u,v分別滿足ui=(xi)+,v=(-xi)+,i=1,2,…,n。操作符(·)+定義為(xi)+=max{0,xi}?！瑇‖1=1Tnu+1Tnv。其中1Tn=[1,1,…,1]T為長(zhǎng)度為n的1向量,因此,式(1)可寫成BCQP問題:

若令u←u+θ,v←v+θ,其中θ≥0為轉(zhuǎn)換向量,式(1)中L1范數(shù)項(xiàng)的值不變,因此,式(4)可寫成標(biāo)準(zhǔn)的BCQP問題:

其中:

問題(5)可看作帶凸集約束的非線性規(guī)劃問題:

其中:

因此,可將重構(gòu)壓縮感知稀疏信號(hào)問題(1)直接轉(zhuǎn)換為求解問題(6)。

1.2 非單調(diào)梯度投影算法

帶凸集約束非線性規(guī)劃問題的一般性GLP(goldstein-lavitin-polyak,簡(jiǎn)稱GLP)梯度投影算法[9],其迭代公式為:

其中:投影算子p(·):Rn→Ω定義為

gk為F(z)在zk點(diǎn)的梯度,且在Ω上是Lipschitz連續(xù)的;λk為滿足廣義Armijo線性搜索條件的步長(zhǎng)。

Zhang等[8]根據(jù)如下非單調(diào)Wolfe線搜索選擇步長(zhǎng)λk:

其中:dk為搜索方向;0＜δ＜σ＜1。給定Q0=1, C0=F(z0),ηk∈[0,1]為給定常數(shù),則

結(jié)合非單調(diào)線搜索(7)和交替BB步長(zhǎng),求解問題(6)的NSGPBB算法步驟為:

1)初始化。z0∈Ω,0＜σ1＜σ2＜1,0＜αmin＜α0＜αmax＜∞,δ∈(0,1),C0=F(z0),Q0=1, k∶=0。

2)計(jì)算dk=p(zk-αkgk)-zk,λ=1。

3)令z+=zk+λkdk。

4)若

則令λk=λ,zk+1=zk+λkdk,sk=zk+1-zk,lk=gk+1-gk,轉(zhuǎn)步驟5);否則λk=σλk,σ∈[σ1,σ2],轉(zhuǎn)步驟3)。

5)若滿足停止準(zhǔn)則,則算法停止,否則由式(9)、(10)計(jì)算Qk+1、Ck+1,并令k=k+1。

步驟2)中的αk選擇算法:

a)若k=0,則令τ1∈(0,1)并給定非負(fù)整數(shù)M。

否則,αk=α1k,ρk+1=1.1ρk。

2 算法的收斂性分析

為了分析算法的收斂性,定義

gα(z)=p(z-αg(z))-z,α∈[αmin,αmax]。若z為約束穩(wěn)定點(diǎn),由文獻(xiàn)[13]可知,gα(z)=0,即‖dk‖=0。若〈g(zk),dk〉≤0,由文獻(xiàn)[8]中的引理知,F(zk)≤Ck。

引理1[10]對(duì)z∈Ω,有

引理2 若λk滿足式(10),則對(duì)所有的k＞0,

其中L為g(z)的Lipschitz常數(shù)。

證明 若λk=1滿足式(10),則式(11)成立,否

則,存在σ∈[σ1,σ2],使得不滿足式(12),即

另一方面,

由不等式(13)、(14)可得

故式(12)得證。

引理3[9]若序列{zk}由NSGPBB算法產(chǎn)生,則

定理1 若序列{zk}由NSGPBB算法產(chǎn)生,則{zk}的每個(gè)極限點(diǎn)均為問題(6)的約束穩(wěn)定點(diǎn)。

證明(反證法) 假設(shè){zk}的極限點(diǎn)z-不是約束穩(wěn)定點(diǎn),則‖dk‖＞η,η為一個(gè)很小的正數(shù)。由引理1,對(duì)所有的k＞0,有＜-ε,ε＞0。

由式(10)和引理3可知:

則有

由式(9)和ηk∈[0,1]得

由式(11)可直接推出:

由引理1、2可知:

則

又因?yàn)?/p>

故

由F(zk)有下界可知,F(z0)-F(zk+1)＜∞,而當(dāng)k→∞時(shí),有F(z0)-F(zk+1)→∞,矛盾,即

因此定理成立。

3 數(shù)值試驗(yàn)

為了驗(yàn)證該算法恢復(fù)原始信號(hào)的有效性,將NSPGBB算法與SPG算法[7]、修正譜共軛梯度投影(SCG)算法[14]、NSPG算法[9]進(jìn)行數(shù)值實(shí)驗(yàn)比較。數(shù)值實(shí)驗(yàn)運(yùn)行環(huán)境:硬件為2 GHz處理器、2 GB內(nèi)存的筆記本電腦,軟件為Matlab7.12(R2011a)。實(shí)驗(yàn)數(shù)據(jù)設(shè)置:原始信號(hào)x的長(zhǎng)度為n=4096,A為m× n高斯隨機(jī)矩陣,觀測(cè)向量y的長(zhǎng)度為m=1024,x中包含160個(gè)隨機(jī)±1元素。參數(shù)初始化:噪聲參數(shù)ζ= 0.01,τ=0.08‖ATy‖∞,任意向量a的無窮范數(shù)定義為‖a‖∞=max|ai|,i=1,2,…,n,η=0.80,αmin=10-10,αmax=1010,ρ1=0.5,σ=0.5,δ=0.25,M= 2。用最小均方誤差E評(píng)價(jià)重構(gòu)信號(hào)的質(zhì)量:

其中:x為原始信號(hào);z為恢復(fù)信號(hào)。E值越小,信號(hào)重構(gòu)的質(zhì)量越高。算法的終止條件為:

圖1為4種算法的信號(hào)恢復(fù)效果,圖2為4種算法的收斂曲線。從圖1可看出,4種算法均能很好地恢復(fù)含有噪聲的信號(hào)。分別從運(yùn)行時(shí)間、迭代步數(shù)和最小均方誤差3項(xiàng)指標(biāo)比較4種算法的性能,算法的數(shù)值結(jié)果如表1所示。從表1可看出,4種算法恢復(fù)信號(hào)的質(zhì)量相似,即E值相差不大,但NSPGBB算法無論在迭代步數(shù)還是CPU運(yùn)行時(shí)間上都比其他3種算法更有優(yōu)勢(shì),這表明NSPGBB算法能更快地恢復(fù)原始信號(hào)。圖2的收斂曲線進(jìn)一步驗(yàn)證了這個(gè)結(jié)論。

圖1 4種算法的信號(hào)恢復(fù)效果Fig.1 Recovery effect of four algorithms

圖2 4種算法的收斂曲線Fig.2 Convergence curve of four algorithms

表1 4種算法的數(shù)值結(jié)果Tab.1 Numerical results of four algorithms

4 結(jié)束語

針對(duì)大規(guī)模稀疏信號(hào)的重構(gòu)問題,結(jié)合非單調(diào)Wolfe線搜索和交替BB步長(zhǎng),提出了一種交替BB步長(zhǎng)非單調(diào)梯度投影算法,并證明了該算法是全局收斂的。與梯度投影算法相比,該算法的優(yōu)點(diǎn)在于交替使用BB步長(zhǎng)加快了線性搜索。數(shù)值實(shí)驗(yàn)結(jié)果表明,該算法能夠有效地恢復(fù)原始信號(hào),且與其他譜梯度投影算法相比,收斂速度更快。

[1] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[2] Figueiredo M A T,Nowak R D,Wright S J.Gradient projection for sparse reconstruction:application to compressed sensing and other inverse problems[J].IEEE Journal of Selected Topics in Signal Processing,2007,1 (4):586-597.

[3] Kim S J,Koh K,Lustig M,et al.An efficient method for compressed sensing[C]//IEEE International Conference on Image Processing,2007:117-120.

[4] Elad M.Why simple shrinkage is still relevant for redundant representations[J].IEEE Transactions on Information Theory,2006,52(12):5559-5569.

[5] Malioutov D M,Cetin M,Willsky A S.Homotopy continuation for sparse signal representation[C]//IEEE International Conference on Acoustics,Speech,and Signal Processing,2005:733-736.

[6] Candes E,Braun N,Wakin M.Sparse signal and image recovery from compressive samples[C]//IEEE International Symposium on Biomedical Imaging:From Nano to Macro,2007:976-979.

[7] Birgin E G,Martínez J M,Raydan M.Nonmonotone spectral projected gradient methods on convex sets[J]. SIAM Journal on Optimization,2000,10(4):1196-1211.

[8] Zhang Hongchao,Hager W W.A nonmonotone line search technique and its application to unconstrained optimization[J].SIAM Journal on Optimization,2004,14 (4):1043-1056.

[9] 畢亞倩,劉新為.求解界約束優(yōu)化的一種新的非單調(diào)譜投影梯度法[J].計(jì)算數(shù)學(xué),2013,35(4):419-430.

[10] Frassoldati G,Zanni L,Zanghirati G.New adaptive stepsize selections in gradient methods[J].Journal of Industrial and Management Optimization,2008,4(2): 299-312.

[11] Barzilai J,Borwein J M.Two-point step size gradient methods[J].IMA Journal of Numerical Analysis, 1988,8(1):141-148.

[12] Calamai P H,MoréJ J.Projected gradient methods for linearly constrained problems[J].Mathematical Programming,1987,39(1):93-116.

[13] Bertsekas D P.Nonlinear Programming[M].Belmont: Athena Scientic,1995,239-240.

[14] Zhang Benxin,Zhu Zhibin.A modified spectral conjugate gradient projection algorithm for total variation image restoration[J].Applied Mathematics Letters, 2014,27:26-35.

編輯:張所濱

Compressed sensing sparse signal reconstruction based on NSGPBB algorithm

Guo Xiao,Li Xiangli
(School of Mathematics and Computational Science,Guilin University of Electronic Technology,Guilin 541004,China)

To solve a key problem of sparse signal reconstruction,a nonmonotone gradient projection algorithm with the alternation of Barzilai-Borwein rules(NSGPBB)is proposed for bound-constrainted quadratic programming(BCQP)on a convex set.Global convergence of this method is proved.The numerical results show that the method is effective and faster than other spectral gradient projection algorithms.

compressed sensing;spectral gradient projection;sparse reconstruction;quadratic programming;alternation of Barzilai-Borwein rules

O224

A

1673-808X(2015)05-0427-04

2015-06-05

廣西自然科學(xué)基金(2014GXNSFAA118003);廣西教育廳科研項(xiàng)目(ZD2014050)

李向利(1977-),女,陜西寶雞人,副教授,博士,研究方向?yàn)樽顑?yōu)化理論與算法。E-mail:lixiangli@guet.edu.cn

郭曉,李向利.基于NSGPBB算法的壓縮感知稀疏信號(hào)重構(gòu)[J].桂林電子科技大學(xué)學(xué)報(bào),2015,35(5):427-430.