王 文，李 永

(西安電子科技大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西安陜西 710126)

1 壓縮感知基礎(chǔ)知識(shí)

隨著現(xiàn)代科學(xué)技術(shù)的發(fā)展，人們對(duì)信息的需求給信號(hào)采樣、傳輸和存儲(chǔ)造成了較大壓力［1］。傳統(tǒng)的采樣理論基本思想是先采樣再進(jìn)行壓縮，但其存在諸多缺點(diǎn)。針對(duì)這些問(wèn)題Donoho，Candes及Tao等人提出了壓縮感知理論［2－4］，其基本思想是在信號(hào)采樣的同時(shí)就進(jìn)行壓縮，然后從觀測(cè)向量b中重構(gòu)出原始信號(hào)A x=b，其中b是長(zhǎng)度為m的觀測(cè)向量，Am×n(m?n)是觀測(cè)矩陣，求解上述問(wèn)題就需要列出x中所有非零位置的Ckn種線性組合，而上述問(wèn)題的數(shù)值計(jì)算很不穩(wěn)定且是一個(gè)NP難的非凸優(yōu)化問(wèn)題。為求解上述問(wèn)題，Candes，Tao和 Donoho等人證明，當(dāng)觀測(cè)矩陣A滿足約束等距性質(zhì)(RIP)時(shí)，上述問(wèn)題可轉(zhuǎn)化為1－范數(shù)問(wèn)題

為更容易地求解式(1)，可通過(guò)選取適當(dāng)?shù)膮?shù)μ，將之轉(zhuǎn)化為與其同解的無(wú)約束問(wèn)題

可看出，式(1)和式(2)是線性規(guī)劃問(wèn)題。但在實(shí)際問(wèn)題中，需重構(gòu)的信號(hào)規(guī)模較大，且通常均是病態(tài)的。所以，求解線性規(guī)劃問(wèn)題的一般方法不能較好地求解，故尋求其的解決方案是壓縮感知理論的核心內(nèi)容。

近年來(lái)已提出了多種求解上述問(wèn)題的算法，大致可分為兩類:其一是不改變目標(biāo)函數(shù)，即求解0－范數(shù)問(wèn)題，例如匹配追蹤(MP)［5］、正交匹配追蹤(OMP)［6］、稀疏自適應(yīng)匹配追蹤(SAMP)［7］、正則化正交匹配追蹤(ROMP)［8］等;其二是將目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)化，即將0－范數(shù)問(wèn)題轉(zhuǎn)化為其他范數(shù)問(wèn)題，如基追蹤法(BP)［9］、投影梯度法 (GPSR)［10］、軟閾值算法(FPC)［11］、坐標(biāo)下降法(CGD)［12］、交替方向法(YALL1)［13］、可分離稀疏重構(gòu)法(SpaRSA)［14］、內(nèi)點(diǎn)法(l1 －ls)［15］和非單調(diào) Barzilai－Borwein(BB)梯度法(NBBL1)［16］等。其中，NBBL1算法將 BB梯度法與非單調(diào)線搜索方法相結(jié)合應(yīng)用到壓縮感知問(wèn)題中，獲得了較好地實(shí)驗(yàn)效果。基于上述思想的啟發(fā)，本文通過(guò)將BB梯度法與另一種非單調(diào)線搜索法相結(jié)合而提出了一種新算法來(lái)求解式(2)，該算法在未增加復(fù)雜度的同時(shí)得到了更好的理論和實(shí)驗(yàn)效果。

2 非單調(diào)線搜索BB梯度法

選取NBBL1算法的方向作為新算法方向，采用一種新改進(jìn)的非單調(diào)線搜索法求步長(zhǎng)，并給出了新算法的具體步驟。

2.1 NBBL1算法方向的選取

引理1［16］若dk是定義的方向，對(duì)于 λk＞0，則有以下兩式成立

文獻(xiàn)［16］中已證，其說(shuō)明當(dāng)dk≠0時(shí)，式(3)是下降方向，?θ∈(0，h］，xk+ θdk是下降點(diǎn)。

2.2 NNBBL1算法步長(zhǎng)的選取

NBBL1算法中采用文獻(xiàn)［18］中的非單調(diào)線搜索法，在求最大值函數(shù)的過(guò)程中，會(huì)舍去一些目標(biāo)函數(shù)值，而這些值可能對(duì)最優(yōu)步長(zhǎng)的選取有幫助，且M值的選取也會(huì)影響算法的效果［19］。

基于這樣的考慮，本文采用一種新的改進(jìn)的非單調(diào)線搜索法求步長(zhǎng)［17］，并結(jié)合NBBL1算法中的方向提出一種新的非單調(diào)線搜索法BB梯度法(NNBBL1)。首先介紹新的改進(jìn)的非單調(diào)線搜索法，對(duì)于光滑函數(shù)φ(x)，選取C0=φ(x0)，Q0=1，τ＞0，0≤ηmin≤ηmax＜1＜ρ，η∈

其中，hk是滿足式(6)最小的正整數(shù)，Qk+1=ηkQk+1，Ck+1=(ηkQkCk+φ(xk+1))/Qk+1，ηk是決定非單調(diào)程度的因子。也可將式(4)轉(zhuǎn)化為

將上述非單調(diào)線搜索法應(yīng)用到式(2)，取δk，ηk為常數(shù)，記為δ，η。則式(6)和 式(7)為

其中，hk是滿足式(8)最小的正整數(shù)，Qk+1=ηQk+1，Ck+1=(ηQkCk+F(xk+1))/Qk+1，Δk=gTkdk+

2.3 基于新非單調(diào)線搜索法的NNBBL1算法

算法的具體步驟如下:

第1步 初始化各個(gè)參數(shù)。任選初始點(diǎn)x0，C0=F(x0)，Q0=1，0≤ηmin≤ηmax＜1＜ρ，η∈［ηmin，ηmax］，δmax＜1，0 ＜δmin＜(1 －ηmax)δmax，ε＞0，τ＞0＞0，δ＞0，非負(fù)整數(shù)k:=0。

第3步 新非單調(diào)線搜索獲取步長(zhǎng)。計(jì)算Qk+1和Ck+1。選取 δmin≤δ＜ δmax/Qk+1，更新步長(zhǎng) αk=ρhk≤τ，使得滿足式(8)。

第4步 更新迭代:xk+1=xk+αkdk，得到新的點(diǎn)，令k:=k+1，返回第2步。

由C0=F(x0)，則 Ck是 F(x1)，…，F(xiàn)(xk)的凸組合，故Ck+1是Ck和F(xk+1)的凸組合，這就意味著Ck包含之前算過(guò)的所有目標(biāo)函數(shù)值。類似文獻(xiàn)［17］可證明，滿足式(6)的 δ是存在的。定理1說(shuō)明滿足式(8)的初始步長(zhǎng)是存在的。綜上所述，本文所提出的算法是可行有效的。

3 算法的收斂性分析

為證明算法的全局收斂性，本文要求f滿足以下假設(shè)。

定理2 設(shè)αk是滿足式(8)的最大步長(zhǎng)，則有

證明 對(duì)于?k∈N，k≥0，有F(xk)≤Ck，則Ck有下界，由式(8)得C2≤C1+ δα1Δ1，…，Ck+1≤Ck+ δαkΔk，…。將上述不等式左右分別相加得

定理3 設(shè){xk}是由NNBBL1算法產(chǎn)生的迭代序列，{dk}是由式(3)產(chǎn)生的方向序列K，則存在一個(gè)子序列，滿足

在文獻(xiàn)［16］中已證明，對(duì)于?k∈N，k≥0，λk＞0，h∈(0，1］，則xk是問(wèn)題(2)的穩(wěn)定點(diǎn)充要條件是dk=0。而F(x)是凸函數(shù)，則局部最優(yōu)解就是全局最優(yōu)解。

4 實(shí)驗(yàn)結(jié)果分析及討論

通過(guò)兩類Matlab實(shí)驗(yàn)來(lái)證明該算法在重構(gòu)信號(hào)方面的優(yōu)勢(shì)，實(shí)驗(yàn)運(yùn)行平臺(tái)的配置如下:處理器 Intel(R)Core(TM)i3 CPU M 380@2.53 GHz;內(nèi)存 2.00 GB 。在不同的Matlab版本測(cè)試下，結(jié)果不會(huì)發(fā)生較大變化。本文實(shí)驗(yàn)在Matlab R2011b中進(jìn)行。

4.1 第一類實(shí)驗(yàn)

實(shí)驗(yàn)取 n=2 048，m=512，k=64，k表示原始信號(hào)中非零元的個(gè)數(shù)。其中非零元的位置均是隨機(jī)選取的，A是與高斯矩陣獨(dú)立同分布的隨機(jī)矩陣，b=A x0+ω，其中 ω∈Rn是高斯白噪聲，且 ωN(0，σ2I)，取 μ =2－8，σ =1e－3，ε =1e－4，h=0.8，λmin=1e－30，λmax=1e+30，為使 λk＞0，取 λk=min{λmin，max{λk，λmin}}。在線搜索過(guò)程中，選取初始步長(zhǎng)x0=0，=0.8，ρ=0.5，δ=1e－4，η=0.4。相對(duì)誤差定義為其中表示重構(gòu)信號(hào)表示原始信號(hào)。當(dāng)相鄰兩點(diǎn)的相對(duì)誤差充分小，即時(shí)，則停止迭代。原始信號(hào)，觀測(cè)向量及重構(gòu)信號(hào)如圖1所示。

圖1 NNBBL1算法的有效性

比較圖1(a)和圖1(c)可看出，所有的藍(lán)點(diǎn)均被紅點(diǎn)包圍，這說(shuō)明原始信號(hào)幾乎被精確重構(gòu)。上述實(shí)驗(yàn)表明，該算法對(duì)一維信號(hào)的重構(gòu)效果良好，且相對(duì)誤差較小。

4.2 第二類實(shí)驗(yàn)

取n=4 096，m=1 024，采用4種不同的稀疏度對(duì)各種算法進(jìn)行比較。取第一類實(shí)驗(yàn)中的初始參數(shù)及=5，不同的是，實(shí)驗(yàn)中取 x0=ATb，對(duì) NNBBL1，NBBL1和GPSR的3種算法進(jìn)行了不同角度的對(duì)比和分析，如圖2和表1、表2所示。

圖2 針對(duì)不同壓縮比、不同算法的目標(biāo)函數(shù)值下降速度比較

如圖2所示，在初始及終止條件相同的情況下從函數(shù)值下降角度分析，無(wú)論針對(duì)哪種信號(hào)，NNBBL1算法總是下降最快的，其次是NBBL1算法，最后是GPSR算法。從圖中橫軸可看出，NNBBL1算法所需迭代次數(shù)也是最少的。

為更進(jìn)一步說(shuō)明圖2所示結(jié)果，表1給出了更詳細(xì)的對(duì)比數(shù)據(jù)。由于獲取的信號(hào)是隨機(jī)產(chǎn)生的，表1和表2中采用10次實(shí)驗(yàn)的平均值作為記錄值。而NNBBL1和NBBL1算法的相對(duì)誤差幾乎一樣，但明顯比GPSR算法小，不再羅列。

表1 針對(duì)不同稀疏度，不同算法實(shí)現(xiàn)相同精度所需要的時(shí)間和迭代次數(shù)對(duì)比

表1中羅列了4種信號(hào)的運(yùn)行時(shí)間和迭代次數(shù)。從表中可看出，隨著信號(hào)規(guī)模的增大，各種算法所需運(yùn)行的時(shí)間也明顯增加，但與算法NBBL1和算法GPSR相比，無(wú)論是哪種信號(hào)，NNBBL1總是用時(shí)最少，且所需迭代次數(shù)最少。

表2 不同初始點(diǎn)對(duì)算法的影響效果對(duì)比

表2取稀疏度k/n=0.05，研究選取不同初始點(diǎn)對(duì)算法效果的影響。當(dāng)初始點(diǎn)設(shè)為ATb時(shí)，達(dá)到最優(yōu)值所需的時(shí)間和迭代次數(shù)均為最少，其次是NBBL1算法，最后是GPSR算法。這說(shuō)明無(wú)論取哪個(gè)初始點(diǎn)，新算法均為最優(yōu)。

5 結(jié)束語(yǔ)

本文結(jié)合新非單調(diào)線搜索的Barzilai－Borwein梯度法應(yīng)用于壓縮感知問(wèn)題，經(jīng)數(shù)值試驗(yàn)結(jié)果證明，針對(duì)不同稀疏度的信號(hào)，該方法均是可行有效的。與NBBL1和GPSR等算法相較，新算法無(wú)論是從運(yùn)行時(shí)間或是迭代次數(shù)上均有不同程度的改進(jìn)。但將新非單調(diào)線搜索方法應(yīng)用到其他算法是否也有較好效果，仍需進(jìn)一步研究。

［1］石光明，劉丹華，高大化，等.壓縮感知理論及其研究進(jìn)展［J］.電子學(xué)報(bào)，2009，37(5):1070 －1081.

［2］Donoho D L.Compressed sensing［J］.IEEE Transactions on Information Theory，2006，52(4):1289 －1306.

［3］Candes E J，Romberg JK，Tao T.Stable signal recovery from incomplete and inaccurate measurements［J］.Communications on Pure and Applied Mathematics，2006，59(8):1207－1223.

［4］Candès E J，Romberg J，Tao T.Robust uncertainty principles:Exact signal reconstruction from highly incomplete frequency information［J］.IEEE Transactions on Information Theory，2006，52(2):489 －509.

［5］Mallat SG，Zhang Z.Matching pursuits with time－frequency dictionaries［J］.IEEE Transactions on Signal Processing，1993，41(12):3397 －3415.

［6］Tropp J A，Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit［J］.IEEE Transactions on Information Theory，2007，53(12):4655 －4666.

［7］Do T T，Gan L，Nguyen N，et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing［C］.2008 42nd Asilomar Conference on Signals，Systems and Computers，IEEE，2008:581 －587.

［8］Needell D，Vershynin R.Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit［J］.IEEE Journal of Selected Topics in Signal Processing，2010，4(2):310 －316.

［9］Chen SS，Donoho D L，Saunders M A.Atomic decomposition by basis pursuit［J］.SIAM Journal on Scientific Computing，1998，20(1):33 －61.

［10］Figueiredo M A T，Nowak R D，Wright SJ.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.

［11］Hale E T，Yin W，Zhang Y.Fixed－point continuation for?1－ minimization:Methodology and convergence［J］.SIAM Journal on Optimization，2008，19(3):1107 －1130.

［12］Yun S，Toh K C.A coordinate gradient descent method for?1－ regularized convex minimization［J］.Computational Optimization and Applications，2011，48(2):273 －307.

［13］Yang J，Zhang Y.Alternating direction algorithms for ?1 －problems in compressive sensing［J］，SIAM Journal on Scientific Computing，2011，33(3):250 －278.

［14］Wright S J，Nowak R D，F(xiàn)igueiredo M A T.Sparse reconstruction by separable approximation［J］.IEEE Transactions on Signal Processing，2009，57(7):2479 －2493.

［15］Kim S，Koh K，Lustig M，et al.An interior－ point method for large－scale ?1 － regularized leastsquares［J］.IEEE Journal of Selected Topics in Signal Processing，2007(1):606 －617.

［16］Xiao Y H，Wu SY，Qi L Q.Nonmonotone Barzilai－Borwein gradient algorithm for?1－regularized nonsmooth minimization in compressive sensing［J］.Journal of Scientiic Computing，2014(1):6 －10.

［17］Huang S，Wan Z，Chen X.A new nonmonotone line search technique for unconstrained optimization［J］.Journal of Computational and Applied Mathematics，2008，219(1):134 －144.

［18］Grippo L，Lampariello F，Lucidi S.A nonmonotone line search technique for Newton's method［J］.SIAM Journal on Numerical Analysis，1986，23(8):707 －716.

［19］Toint P L.An assessment of nonmonotone linesearch techniques for unconstrained optimization［J］.SIAM Journal of Science Computer，1996，17(3):725 － 739.