劉 艷,李 雷

(南京郵電大學(xué) 非結(jié)構(gòu)化數(shù)據(jù)計算理論與應(yīng)用研究中心，江蘇 南京 210046)

基于擬牛頓法的梯度追蹤算法研究

劉 艷,李 雷

(南京郵電大學(xué) 非結(jié)構(gòu)化數(shù)據(jù)計算理論與應(yīng)用研究中心，江蘇 南京 210046)

為了解決傳統(tǒng)迭代算法中需要計算正交投影的問題，將擬牛頓法與梯度追蹤算法(Gradient Pursuit)相結(jié)合，提出了基于擬牛頓法的梯度追蹤算法(Quasi-Newton Method based Gradient Pursuit,QNMGP)。擬牛頓法是解決無約束最優(yōu)化問題的有效方法，其避免了牛頓法需要求解Hesse矩陣的問題，降低了計算量，提高了收斂速度，新提出的算法通過限域擬牛頓法來求解更新方向，并將其運用到梯度追蹤算法中。為驗證新提出算法的可行性與有效性，基于MATLAB仿真平臺，從重構(gòu)時間、均方誤差和峰值信噪比三個方面對QNMGP算法與其他貪婪算法進(jìn)行了仿真對比實驗驗證。仿真實驗結(jié)果表明，在同等的測試環(huán)境下，新提出的QNMGP算法重構(gòu)效果遠(yuǎn)優(yōu)于其他算法，且在重構(gòu)時間上也具有一定的優(yōu)勢。

擬牛頓法；梯度追蹤；最優(yōu)化問題；重構(gòu)算法

1 概 述

壓縮感知[1-3](Compressive Sensing,CS)理論是近年來出現(xiàn)的一種新型壓縮采樣方法。該理論指出，如果信號可壓縮或者在某個變換域上是稀疏的，就能用一個與變換基不相關(guān)的觀測矩陣將高維信號投影到一個低維空間上，接著通過求解一個優(yōu)化問題就能夠從這些少量的投影中高概率地重構(gòu)出原信號。

假設(shè)b∈Rn為一個已知的向量，A為m×n維的觀測矩陣且滿足m

b=Ax+ε

(1)

由于貪婪迭代算法的迭代過程比較簡單，因此目前應(yīng)用比較廣泛，其主要是解決式(2)這類子空間優(yōu)化問題，但是此類算法都需要通過計算量很大的正交投影來估計信號，在一定程度上增加了重構(gòu)計算量，降低了收斂速度。

(2)

針對此類問題，ThomasBlumensath和MikeE.Davies提出了梯度追蹤(gradientpursuit)算法。該算法通過計算梯度來代替貪婪迭代算法中的正交投影，這在一定程度上可以減少計算量，提高收斂速度。

為此，將最優(yōu)化方法中的擬牛頓法[16-17]與梯度追蹤算法相結(jié)合，提出了基于擬牛頓法的梯度追蹤的重構(gòu)算法，并在重構(gòu)時間、均方誤差和峰值信噪比三個方面通過與其他算法的仿真對比證明了新提出算法的優(yōu)越性。

2 梯度追蹤算法

(3)

3 擬牛頓法相關(guān)知識

牛頓法是通過求解式(4)來確定搜索方向的，但在求解過程中需要計算2f(xk)，因此，牛頓法存在計算量大，同時會出現(xiàn)矩陣奇異的缺陷。

(4)

為了避免這些問題，Davidon提出了擬牛頓法[18]。該方法是假設(shè)通過某種方式已得到的目標(biāo)函數(shù)在xk點處的Hesse矩陣逆的近似Hk,并通過式(5)進(jìn)行線搜索產(chǎn)生下一迭代點，即用式(5)來替代式(4)。

-Hkf(xk)=dk

(5)

將目標(biāo)函數(shù)f(x)在xk+1點進(jìn)行泰勒展開，并取二階近似，即：

f(x)≈f(xk+1)+f(x-xk+1)+2f(xk+1)(x-xk+1)

(6)

兩邊關(guān)于x求梯度并令x=xk得到：

(7)

令

sk=xk+1-xk,yk=f(xk+1)-f(xk)

(8)

同時設(shè)Hesse矩陣可逆，則式(7)可以轉(zhuǎn)化為：

(9)

用n階方陣Hk+1表示2f(xk+1)逆的近似，將式(10)的“≈”改成“=”得：

yk=Hk+1sk

(10)

式(10)稱作擬牛頓方程。顯然,方程中變量的個數(shù)遠(yuǎn)大于方程的個數(shù)，因此不能唯一地求解出Hk+1，所以需要通過對Hk進(jìn)行修正來求解出Hk+1，令

Hk+1=Hk+ΔHk

(11)

當(dāng)Hk+1是正定矩陣時，dk=-Hkf(xk)是搜索方向。

(12)

當(dāng)k+1≤m時，有：

(13)

當(dāng)k+1>m時，有：

(14)

限域擬牛頓法步驟如下：

(1)給定初始點x0，k=0，設(shè)置正整數(shù)m。

(2)設(shè)初始矩陣為H0=I，求出目標(biāo)函數(shù)f(x)在xk處的梯度f(xk)。

(3)求解方程組-Hkf(xk)=dk，得到dk。

(7)令sk=xk+1-xk,yk=f(xk+1)-f(xk)，利用式(13)、式(14)更新次H0求解Hk+1。

(8)k=k+1，返回步驟(3)。

4 QNMGP算法

擬牛頓法是基于擬牛頓條件利用目標(biāo)函數(shù)的梯度構(gòu)造目標(biāo)函數(shù)Hesse矩陣的近似，此類算法不僅具有下降性，同時還擁有二次終止性、收斂速度快等優(yōu)點。將擬牛頓法的思想與梯度追蹤算法相結(jié)合，形成基于擬牛頓法的梯度追蹤算法(Quasi-Newton Method based Gradient Pursuit,QNMGP)。

(15)

令

(16)

(17)

(18)

QNMGP算法步驟如下：

1)設(shè)置初始誤差r0=y,xn=0,Tn是空集,H0=1。

2)令n=1,n=n+1。

(1)gn=〈rn-1,A〉；

(3)Tn=Tn-1∪in；

(11)rn=rn-1-βncn。

3)輸出rn,xn，當(dāng)滿足‖rn-rn-1‖≤10-6停止。

擬牛頓法在計算復(fù)雜度方面要小于牛頓法，加快了重構(gòu)時間，同時該算法具有二次有限終止性以及最速下降法的下降性等一系列優(yōu)良性質(zhì)；因此，擬牛頓法與梯度追蹤法的結(jié)合從理論上優(yōu)于其他的追蹤算法。

5 實驗與仿真

為了說明提出算法的優(yōu)越性，用Matlab進(jìn)行仿真。選取圖片“house”作為實驗素材，壓縮比M/N=0.5，分別用NP,OMP,GP,CGP與QNMGP進(jìn)行比較，實驗效果如圖1所示。

圖1 不同算法重構(gòu)效果圖

由圖1可知，QNMGP算法重構(gòu)出的圖像相較于NP,OMP,GP,CGP四種算法重構(gòu)出的圖像更加清晰。為了更加準(zhǔn)確地說明QNMGP具有較好的重構(gòu)性能，表1顯示了五種重構(gòu)算法在重構(gòu)時間、均方誤差以及峰值信噪比方面的比較。

表1 各算法重構(gòu)性能比較

由表1可知，在重構(gòu)時間方面，QNMGP低于CGP和NP，因此說明QNMGP在重構(gòu)時間方面具有一定的優(yōu)勢。在均方誤差方面，QNMGP遠(yuǎn)遠(yuǎn)低于其他四種算法，NP的最大，由均方誤差越小重構(gòu)性能越好可知，QNMGP重構(gòu)效果是最好的。從峰值信噪比看，QNMGP為31.589 9，其余四種重構(gòu)算法均比QNMGP低，由峰值信噪比越高重構(gòu)效果越好可知，QNMGP重構(gòu)效果最好。

表2顯示了在壓縮比為0.1至0.7時各算法的峰值信噪比。

表2 不同壓縮比下各算法重構(gòu)的峰值信噪比

從表中可以發(fā)現(xiàn)，在同一壓縮比時，QNMGP的峰值信噪比均高于其他四種算法，因此其重構(gòu)誤差也均低于其他四種算法，因此可以說明新提出的QNMGP重構(gòu)效果最好。

6 結(jié)束語

為了解決傳統(tǒng)迭代算法中需要計算正交投影的問題，將擬牛頓法和梯度追蹤法相結(jié)合，基于Matlab仿真平臺對QNMGP與NP,OMP,GP,CGP四種算法分別從重構(gòu)時間、均方誤差和峰值信噪比三個方面進(jìn)行了仿真對比實驗。結(jié)果表明，QNMGP的重構(gòu)效果遠(yuǎn)高于其他幾種算法，在重構(gòu)時間上也具有一定的優(yōu)勢。此外，還對不同壓縮比下圖像重構(gòu)的峰值信噪比進(jìn)行了對比分析，實驗及其結(jié)果表明，在同一壓縮比下，QNMGP均高于其他算法，表明QNMGP在重構(gòu)方面具有較好的性能。

[1] 石光明,劉丹華,高大化,等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報,2009,37(5):1070-1081.

[2] 尹宏鵬,劉兆棟,柴 毅,等.壓縮感知綜述[J].控制與決策,2013,28(10):1441-1445.

[3]DonohoDL.Compressedsensing[J].IEEETransactiononInformationTheory,2006,52(4):1289-1306.

[4]CandesE.Compressivesampling[C]//Proceedingsoftheinternationalcongressofmathematicians.Madrid,Spain:[s.n.],2006:1433-1452.

[5] 林婉娟,趙瑞珍,李 浩.用于壓縮感知信號重建的NSL0算法[J].新型工業(yè)化,2011,1(7):78-84.

[6]ZhengD,WangY,WangLU,etal.Reconstructionalgorithmforcompressedsensingbasedonsmoothedl0normandgaussianconjugategradientmethod[J].JournalofComputationalInformationSystems,2015,11:16.

[7]MohimaniH,Babaie-ZadehM,JuttenC.Afastapproachforovercompletesparsedecompositionbasedonsmoothedl0norm[J].IEEETransactionsonSignalProcessing,2009,57(1):289-301.

[8] 齊煥芳,徐源浩.用于壓縮感知信號重建的SL_0改進(jìn)算法[J].電子科技,2015,28(4):27-30.

[9]WangJ,ZhangJ,ChenC,etal.Basicpursuitofanadaptiveimpulsedictionaryforbearingfaultdiagnosis[C]//Internationalconferenceonmechatronicsandcontrol.[s.l.]:IEEE,2014.

[10]YangJ,ZhangY,YinW.AfastalternatingdirectionmethodforTVL1-L2signalreconstructionfrompartialFourierdata[J].IEEEJournalofSelectedTopicsinSignalProcessing,2010,4(2):288-297.

[11]KirolosS,LaskaJ,WakinM,etal.Analog-to-informationconversionviarandomdemodulation[C]//ProceedingsoftheIEEEDallascircuitsandsystemsworkshop.Dallas:IEEE,2006.

[12]MonroDM.Matchingpursuitsbasisselection:US,US8184921[P].2012.

[13]KwonS,WangJ,ShimB.Multipathmatchingpursuit[J].IEEETransactionsonInformationTheory,2014,60(5):2986-3001.

[14]TroppJ.Greedisgood:algorithmicresultsforsparseapproximation[J].IEEETransactionsonInformationTheory,2004,50(10):2231-2342.

[15] 李 珅,馬彩文,李 艷,等.壓縮感知重構(gòu)算法綜述[J].紅外與激光工程,2013,42(S1):225-232.

[16] 劉明敏,劉棟良.基于BFGS的遺傳算法在數(shù)控機床故障識別研究系統(tǒng)中的應(yīng)用[J].工業(yè)控制計算機,2015,28(6):38-39.

[17] 解可新,韓 健,林友聯(lián).最優(yōu)化方法[M].天津:天津大學(xué)出版社,2004.

[18] 王宜舉,修乃華.非線性最優(yōu)化理論與方法[M].北京:科學(xué)出版社,2012.

[19]NocedalJ.Updatingquasi-Newtonmatriceswithlimitedstorage[J].MathematicsofComputation,1980,35(151):773-782.

[20]BlumensathT,DaviesME.Gradientpursuits[J].IEEETransactionsonSignalProcessing,2008,56(6):2370-2382.

[21] 喬現(xiàn)偉,喬 蕾.基于限域擬牛頓法的混沌類電磁學(xué)機制算法及其在路徑尋優(yōu)中的應(yīng)用[J].計算機應(yīng)用,2015,35(3):696-699.

Investigation on Gradient Tracking Algorithm with Quasi Newton Method

LIU Yan，LI Lei

(Unstructured Data Calculation Theory and Application Research Center,Nanjing University of Posts and Telecommunications,Nanjing 210046,China)

It’s necessary to compute the orthogonal projection in the traditional iteration algorithms.In order to solve this problem,the Quasi-Newton Method-based Gradient Pursuit (QNMGP) has been proposed,in which Quasi-Newton method is an effective one to solve unconstrained optimization problems without need of the Hesse matrix at the same time.The amount of calculation has been reduced and the convergence speed has been raised.The proposed algorithm can change the direction for solution of Quasi-Newton method in limitation domain and then be applied in the gradient tracking algorithm.Based on MATLAB simulation platform,experiment tests for verification,in which the proposed QNMGP is compared with other greedy algorithms on three performances like reconstruction time,mean square error and peak signal to noise ratio.The simulation results show that the proposed QNMGP algorithm is more effective than other algorithms in the same test environment and has advantage in reconstruction time.

Quasi-Newton method;gradient tracking;optimization problem;reconstruction algorithm

2016-06-02

2016-09-08

時間：2017-03-07

國家自然科學(xué)基金資助項目(61070234,61071167,61373137,61501251)；南京郵電大學(xué)引進(jìn)人才科研啟動基金資助項目(214191)

劉 艷(1991-)，女，碩士，研究方向為非線性分析及其應(yīng)用；李 雷，教授，研究方向為智能信號處理和非線性科學(xué)及其在通信中的應(yīng)用。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170307.0922.062.html

TP301.6

A

1673-629X(2017)04-0113-04

10.3969/j.issn.1673-629X.2017.04.025