基于NSGPBB算法的壓縮感知稀疏信號重構

郭 曉,李向利

基于NSGPBB算法的壓縮感知稀疏信號重構

郭 曉,李向利

(桂林電子科技大學數學與計算科學學院,廣西桂林 541004)

為了更好地重構原始信號,提出一種帶有交替BB步長的非單調梯度投影算法(NSGPBB)。將無約束凸優化問題轉化為在閉凸集上的邊界約束二次規劃問題,并證明了該算法的收斂性。數值實驗結果表明,該算法是有效的,且收斂速度快于梯度投影算法。

壓縮感知;譜梯度投影算法;稀疏重構;二次規劃;交替BB步長

其中:x∈Rn為原始信號,在正交基下可稀疏或可壓縮;y∈Rm為低維測量向量;τ為非負參數;‖x‖1=

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

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

為了求解以上優化問題,近年來學者們提出了許多相關算法,如稀疏重構梯度投影(GPSR)算法[2],內點(IP)算法[3],迭代壓縮/閾值化(IST)算法[4],同倫(HM)算法[5]以及加權最小L1范數法[6]等。在信號處理中,這些算法都能有效地恢復信號。

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

1 壓縮感知信號重構模型與算法

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

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

若令u←u+θ,v←v+θ,其中θ≥0為轉換向量,式(1)中L1范數項的值不變,因此,式(4)可寫成標準的BCQP問題:

其中:

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

其中:

因此,可將重構壓縮感知稀疏信號問題(1)直接轉換為求解問題(6)。

1.2 非單調梯度投影算法

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

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

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

Zhang等[8]根據如下非單調Wolfe線搜索選擇步長λk:

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

結合非單調線搜索(7)和交替BB步長,求解問題(6)的NSGPBB算法步驟為:

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

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

3)令z+=zk+λkdk。

4)若

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

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

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

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

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

2 算法的收斂性分析

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

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

引理1[10]對z∈Ω,有

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

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

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

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

另一方面,

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

故式(12)得證。

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

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

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

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

則有

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

由式(11)可直接推出:

由引理1、2可知:

則

又因為

故

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

因此定理成立。

3 數值試驗

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

其中:x為原始信號;z為恢復信號。E值越小,信號重構的質量越高。算法的終止條件為:

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

圖1 4種算法的信號恢復效果Fig.1 Recovery effect of four algorithms

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

表1 4種算法的數值結果Tab.1 Numerical results of four algorithms

4 結束語

針對大規模稀疏信號的重構問題,結合非單調Wolfe線搜索和交替BB步長,提出了一種交替BB步長非單調梯度投影算法,并證明了該算法是全局收斂的。與梯度投影算法相比,該算法的優點在于交替使用BB步長加快了線性搜索。數值實驗結果表明,該算法能夠有效地恢復原始信號,且與其他譜梯度投影算法相比,收斂速度更快。

[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] 畢亞倩,劉新為.求解界約束優化的一種新的非單調譜投影梯度法[J].計算數學,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

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

李向利(1977-),女,陜西寶雞人,副教授,博士,研究方向為最優化理論與算法。E-mail:lixiangli@guet.edu.cn

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