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

劉 艷,李 雷

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

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

劉 艷,李 雷

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

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

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

1 概 述

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

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

b=Ax+ε

(1)

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

(2)

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

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

2 梯度追蹤算法

(3)

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

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

(4)

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

-Hkf(xk)=dk

(5)

將目標(biāo)函數(shù)f(x)在xk+1點(diǎn)進(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í)設(shè)Hesse矩陣可逆，則式(7)可以轉(zhuǎn)化為：

(9)

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

yk=Hk+1sk

(10)

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

Hk+1=Hk+ΔHk

(11)

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

(12)

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

(13)

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

(14)

限域擬牛頓法步驟如下：

(1)給定初始點(diǎn)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矩陣的近似，此類算法不僅具有下降性，同時(shí)還擁有二次終止性、收斂速度快等優(yōu)點(diǎn)。將擬牛頓法的思想與梯度追蹤算法相結(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停止。

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

5 實(shí)驗(yàn)與仿真

為了說明提出算法的優(yōu)越性，用Matlab進(jìn)行仿真。選取圖片“house”作為實(shí)驗(yàn)素材，壓縮比M/N=0.5，分別用NP,OMP,GP,CGP與QNMGP進(jìn)行比較，實(shí)驗(yà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)時(shí)間、均方誤差以及峰值信噪比方面的比較。

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

由表1可知，在重構(gòu)時(shí)間方面，QNMGP低于CGP和NP，因此說明QNMGP在重構(gòu)時(shí)間方面具有一定的優(yōu)勢(shì)。在均方誤差方面，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時(shí)各算法的峰值信噪比。

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

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

6 結(jié)束語

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

[1] 石光明,劉丹華,高大化,等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào),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] 林婉娟,趙瑞珍,李 浩.用于壓縮感知信號(hào)重建的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] 齊煥芳,徐源浩.用于壓縮感知信號(hào)重建的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ù)控機(jī)床故障識(shí)別研究系統(tǒng)中的應(yīng)用[J].工業(yè)控制計(jì)算機(jī),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é)機(jī)制算法及其在路徑尋優(yōu)中的應(yīng)用[J].計(jì)算機(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

時(shí)間：2017-03-07

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

劉 艷(1991-)，女，碩士，研究方向?yàn)榉蔷€性分析及其應(yīng)用；李 雷，教授，研究方向?yàn)橹悄苄盘?hào)處理和非線性科學(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