基于優(yōu)化觀測矩陣的共軛梯度改進(jìn)算法

蘭明然，王友國，鄭丹青

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210046)

基于優(yōu)化觀測矩陣的共軛梯度改進(jìn)算法

蘭明然，王友國，鄭丹青

(南京郵電大學(xué) 理學(xué)院，江蘇 南京 210046)

測量矩陣的設(shè)計和信號的重構(gòu)是壓縮感知理論研究的核心問題?；谔荻认陆捣ǖ腝R分解觀測矩陣優(yōu)化使得信號在觀測過程中的主要信息得以保存，而共軛梯度法則在信號的重構(gòu)性能方面較理想。為此，將觀測矩陣優(yōu)化引入到共軛梯度重構(gòu)算法中，針對共軛梯度重構(gòu)算法，基于梯度下降法的QR分解優(yōu)化觀測矩陣，得到一個新的重構(gòu)算法，即基于優(yōu)化觀測矩陣的共軛梯度算法。改進(jìn)的算法中矩陣具有較大的列獨(dú)立性以及與稀疏矩陣間相關(guān)性較低的特性，同時具有較好的性能。利用Matlab仿真實驗來驗證共軛梯度法與觀測矩陣優(yōu)化結(jié)合的重構(gòu)算法的可行性及有效性。仿真結(jié)果表明，基于優(yōu)化觀測矩陣的共軛梯度算法在運(yùn)行時間上縮短了2～3倍，優(yōu)于其他一些重構(gòu)算法。

壓縮感知；觀測矩陣；共軛梯度法；梯度下降法；QR分解

0 引 言

傳統(tǒng)的奈奎斯特采樣定理要求信號采樣頻率不低于信號帶寬的兩倍，這樣才能不失真地實現(xiàn)重構(gòu)。近年來，Donoho等在信號分解以及泛函分析的基礎(chǔ)上，提出了一個全新的信號采樣理論—壓縮感知(Compressive Sensing,CS)[1-2]。該理論的核心思想：將采樣和壓縮合二為一，直接獲取有用信息，再以解決優(yōu)化問題的方式高概率重構(gòu)原信號。其理論的信息處理方式將大幅降低信息采集量、縮短信息采集時間和節(jié)約信息存儲空間。由于諸多優(yōu)點(diǎn)，該理論從誕生開始就迅速引起各科研和實用機(jī)構(gòu)的重視，并不斷發(fā)展。CS理論的重點(diǎn)是信號的準(zhǔn)確采樣及其精確重構(gòu)。因此觀測矩陣的合理構(gòu)造和信號重構(gòu)就成為研究重點(diǎn)。

研究表明，性能優(yōu)越的觀測矩陣具有相關(guān)性較小的性質(zhì)，它能夠影響到信號的重構(gòu)精度。文獻(xiàn)[3-4]提出并驗證了基于梯度下降法的QR分解觀測矩陣優(yōu)化的可行性和共軛梯度重構(gòu)算法的優(yōu)越性。對于文獻(xiàn)[4]中提出的共軛梯度法，若將觀測矩陣的優(yōu)化引入其中，是否能夠?qū)Y(jié)果有一個更優(yōu)的改善。基于此問題，做如下理論分析：

觀測矩陣的優(yōu)化是基于梯度下降法和QR分解相結(jié)合，將其應(yīng)用在經(jīng)典重構(gòu)算法OMP中，優(yōu)化后的矩陣具有較大的列獨(dú)立性以及與稀疏矩陣間相關(guān)性較低的特性，有較好的效果；而基于光滑L0范數(shù)(SL0)的共軛梯度重構(gòu)算法是一種比較嚴(yán)謹(jǐn)?shù)乃惴?，在此重?gòu)算法中，選取的觀測矩陣是跟其他重構(gòu)算法相同的，其重構(gòu)性能較好。

為此，將觀測矩陣優(yōu)化引入到共軛梯度重構(gòu)算法中。通過大量仿真實驗發(fā)現(xiàn)，在重構(gòu)圖像效果，綜合考慮運(yùn)行時間上的重構(gòu)算法，基于優(yōu)化觀測矩陣的共軛梯度算法，并不劣于共軛梯度方法，且運(yùn)行時間大大縮短兩到三倍，進(jìn)而驗證了提出算法是可行及有效的。

1 壓縮感知信號重構(gòu)模型

壓縮感知，是給定一個可壓縮或稀疏的原始信號，通過某個特定的矩陣將其投影到一個低維空間上，再利用一定的重構(gòu)算法重構(gòu)出原始信號[1]。CS理論的基本原理：設(shè)x為N維原始信號，稀疏度為K(即x中最多含有K個非零元素)，若原始信號非稀疏，則通過稀疏矩陣對其進(jìn)行稀疏化，得到信號在稀疏基下的系數(shù)Θ。觀測矩陣Φ為M×N(M

從觀測向量y重構(gòu)出稀疏信號x的過程是解方程組的過程：y=Φx。但矩陣Φ的維數(shù)關(guān)系是M

min‖x‖0

s.t.y=Φx

(1)

其中，‖x‖0是向量x的l0范數(shù)，表示x中非零元素的個數(shù)。

min‖x‖1

s.t.y=Φx

(2)

通常采用基追蹤算法[7]或貪婪算法[8-9]。

2 基于觀測矩陣優(yōu)化的重構(gòu)算法的改進(jìn)

2.1 基于梯度下降法的QR分解觀測矩陣優(yōu)化

該優(yōu)化方法主要是以高斯矩陣為原始觀測矩陣，將已有的梯度下降法與QR分解的思想相結(jié)合，得到一種新的優(yōu)化方法。通過它構(gòu)造Gram矩陣，利用梯度下降法對Gram矩陣逐步逼近于單位矩陣，通過迭代優(yōu)化后的矩陣反向求出觀測矩陣，并對其進(jìn)行QR分解，得到最終優(yōu)化后的觀測矩陣[10-12]；將最后的結(jié)果用來計算Gram矩陣，在這兩矩陣反復(fù)作用的過程中，若迭代次數(shù)達(dá)到一定值時，停止迭代，輸出此時的觀測矩陣。具體步驟如下：

輸入：稀疏矩陣Ψ，迭代步長η，最大迭代次數(shù)K

初始化：Φ為一個任意的隨機(jī)矩陣，Θ=ΦΨ

對Θ做列單位化：Θ←Θ-ηΘ(ΘTΘ-I)，得到：Φ1←ΘΨ-1

對Φ1進(jìn)行近似QR分解優(yōu)化：即先對Φ1進(jìn)行QR分解，得到Φ1=QR。其中，Q為正交陣，R為上三角矩陣。然后將R中的非對角線元素設(shè)置為零，得到R1。最后根據(jù)Φ2=QR1求得進(jìn)一步更新的矩陣Φ2，再根據(jù)Θ=Φ2Ψ，依次循環(huán)。

2.2 基于共軛梯度法的算法改進(jìn)

s.t.y=Φx

(3)

文獻(xiàn)[13]采用最速下降法求解式(3)，其搜索方向會產(chǎn)生“鋸齒效應(yīng)”，收斂速度慢。文獻(xiàn)[14]利用修正牛頓法求解式(3)，其使用的雙曲正切函數(shù)fσ(xi)逼近l0范數(shù)的收斂性高于高斯函數(shù)的收斂性，但是雙曲正切函數(shù)的Hesse矩陣是非正定的，文獻(xiàn)中使用牛頓法需加入修正項，這引入了一定的“干擾”。針對這一問題，采用文獻(xiàn)[4]提出的共軛梯度法求解式(3)。其重構(gòu)算法不需要計算Hesse矩陣，進(jìn)而不會引入一定的“干擾”，該方法當(dāng)前搜索方向是利用梯度值與前一搜索方向構(gòu)造得到的，存儲量較小。使用Fletcher-Reeves公式來構(gòu)造搜索方向，采用雙曲正切函數(shù)逼近l0范數(shù)，對于式(3)優(yōu)化問題求解的具體步驟如下：

首先確定全自動鋼印打印所需運(yùn)動方式，即證件必須正確堆放在固定區(qū)域，由抓手抓住證件，而后將證件準(zhǔn)確送到鋼印機(jī)打印位置，完成后打印后退回原位，抓手將證件通過另一方向移動將證件移至證件擺放區(qū)，松開抓手，抓手原位返回繼續(xù)抓住第2個證件，重復(fù)上述動作，最終

(1)初始點(diǎn)x(1)，k=1，置迭代步數(shù)Iter。

(2)k≤Iter時,求可行下降方向：d(k)=

投影梯度法求解可行方向：d(k)=PΦd(k)。其中，PΦ=I-Φ?Φ為投影矩陣，Φ?=ΦΤ(ΦΦΤ)-1為廣義逆。

x(k+1)=x(k)+μd(k)

k=k+1

(3)輸出最優(yōu)解x*=x(k+1)。

2.3 基于優(yōu)化觀測矩陣的共軛梯度算法

該改進(jìn)方法把基于梯度下降法的QR分解優(yōu)化后的觀測矩陣應(yīng)用于共軛梯度重構(gòu)算法中，優(yōu)化后的矩陣具有較大獨(dú)立性，同時與稀疏基間相關(guān)性較低，將其應(yīng)用在經(jīng)典重構(gòu)算法OMP中具有較好的重構(gòu)性能；而基于光滑L0范數(shù)(SL0)的共軛梯度重構(gòu)算法比較嚴(yán)謹(jǐn)。把優(yōu)化后的觀測矩陣應(yīng)用于共軛梯度重構(gòu)算法中，得到一個新的重構(gòu)算法，即基于優(yōu)化觀測矩陣的共軛梯度算法。具體過程：通過2.1的方法對矩陣進(jìn)行優(yōu)化，經(jīng)過M×N的觀測矩陣作用后得到M維的觀測向量；再通過2.2提出的共軛梯度法改進(jìn)的L0范數(shù)算法，進(jìn)行信號重構(gòu)。具體步驟如下：

(3)輸出最優(yōu)解x*=x0。

3 實驗仿真與分析

為證實所提出的優(yōu)化觀測矩陣的共軛梯度算法相關(guān)理論的可行性和優(yōu)越性，采用Matlab標(biāo)準(zhǔn)圖像庫中256*256的Lena圖像進(jìn)行仿真實驗。將提出方法與優(yōu)化的觀測矩陣OMP算法[3]和共軛梯度算法[4]進(jìn)行對比，在M/N<0.5范圍內(nèi)進(jìn)行研究。分別選取不同的壓縮比，比較采用不同重構(gòu)算法得到的重構(gòu)效果(用峰值信噪比表示)。因為初始矩陣的隨機(jī)性，采用30次平均統(tǒng)計結(jié)果為最終結(jié)果。圖1給出了不同壓縮比下三種重構(gòu)算法對Lena圖像的重構(gòu)時間。

圖1 不同壓縮比下三種重構(gòu)算法的重構(gòu)時間

由圖1易知，提出的觀測矩陣優(yōu)化共軛梯度法的重構(gòu)時間得到大大提升，特別當(dāng)壓縮比較小時，與共軛梯度法相比縮短了幾倍，與觀測矩陣優(yōu)化OMP法相比，重構(gòu)時間有明顯的改善；時間的改善表明所提出的共軛梯度法與觀測矩陣優(yōu)化結(jié)合的算法是可行、有效的。

圖2給出了在不同壓縮比下三種重構(gòu)算法對Lena圖像的重構(gòu)信噪比。

圖2 不同壓縮比下三種重構(gòu)算法的重構(gòu)信噪比

由圖2可知，當(dāng)壓縮比小于0.4時，提出算法的峰值信噪比均大于其他兩種算法的峰值信噪比，隨著壓縮比的增大，因原始信號的非稀疏性，得到的重構(gòu)效果不是很理想。

圖3給出了壓縮比為0.4時三種重構(gòu)算法對圖像的重構(gòu)效果。

由圖3可以看出，改進(jìn)算法的重構(gòu)效果與另外兩種算法相比還是有優(yōu)勢的，重構(gòu)算法的信噪比基本持平，但運(yùn)行時間卻有很大的提升。

由圖1和圖2可知，提出算法的PSNR沒有優(yōu)于觀測矩陣優(yōu)化OMP算法和共軛梯度算法，但相比PSN并沒有差很多。此方法最大的優(yōu)勢是在可以忽略的PSNR的差別下，重構(gòu)時間有明顯改善。以上分析表明，在不同的壓縮比下，基于觀測矩陣優(yōu)化后的共軛梯度法的重構(gòu)性能幾乎都是三種算法中最佳的，在一定程度上體現(xiàn)了該方法的優(yōu)越性。

圖3 原始圖像與三種重構(gòu)算法生成圖像的對比

4 結(jié)束語

將觀測矩陣優(yōu)化和共軛梯度算法改進(jìn)的思想相結(jié)合，提出了基于觀測矩陣優(yōu)化的共軛梯度重構(gòu)算法。通過實驗仿真驗證了該重構(gòu)算法具有一定的優(yōu)勢，另外，算法保留了觀測矩陣優(yōu)化OMP算法的穩(wěn)定性，使用較好性能的共軛梯度算法，而且與其他兩種算法相比，在時間上大大縮短。當(dāng)然，還可以將不同的重構(gòu)算法運(yùn)用到觀測矩陣的優(yōu)化中，可能會得到更佳的效果，這有待進(jìn)一步的研究。

[1]DonohoD.Compressedsensing[J].IEEETransactionsonInformationTheory,2006,52(4):1289-1306.

[2]CandesE.Compressivesampling[C]//Proceedingoftheinternationalcongressofmathematicians.Madrid,Spin:[s.n.],2006:1433-1452.

[3] 傅迎華.可壓縮傳感重構(gòu)算法與近似QR分解[J].計算機(jī)應(yīng)用,2008,28(9):2300-2302.

[4]ZhengDanqing,WangYouguo,WangLu,etal.ReconstructionalgorithmforcompressedsensingbasedonsmoothedL0normandGaussianconjugategradientmethod[J].JournalofComputationalInformationSystems,2015,16:6101-6109.

[5]DonohoDL.Formostlargeunderdeterminedsystemsoflinearequations,theminimall1normsolutionisalsothesparsestsolution[J].CommunicationsonPureandAppliedMathematics,2006,59(6):797-829.

[6]DonohoD,TsaigY.Extensionsofcompressedsensing[J].SignalProcessing,2006,86(3):533-548.

[7]ChenSS,DonohoDL,SaundersMA.Atomicdecompositionbybasispursuit[J].SIAMJournalonScientificComputing,2001,43(1):129-159.

[8]TroppJA,GilbertAC.Signalrecoveryfromrandommeasurementsviaorthogonalmatchingpursuit[J].IEEETransactionsonInformationTheory,2007,53(12):4655-4666.

[9]NeedellD,VershyninR.Uniformuncertaintyprincipleandsignalrecoveryviaregularizedorthogonalmatchingpursuit[J].FoundationsofComputationalMathematics,2007,9(3):317-334.

[10]CandesE,TaoT.Nearoptimalsignalrecoveryformrandomprojections:universalencodingstrategies[J].IEEETransactionsonInformationTheory,2007,52(12):5406-5425.

[11]BaraniukR.Alectureoncompressivesensing[J].IEEESignalProcessingMagazine,2007,24(4):118-121.

[12]DonohoDL,StarkPB.Uncertaintyprinciplesandsignalrecovery[J].SIAMJournalonAppliedMathematics,1989,49(3):906-931.

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

[14] 趙瑞珍,林婉娟,李 浩,等.基于光滑l0范數(shù)和修正牛頓法的壓縮感知重建算法[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2012,24(4):478-484.

Improved Conjugate Gradient Algorithm Based on Optimization ofMeasurement Matrix

LAN Ming-ran,WANG You-guo,ZHENG Dan-qing

(College of Science,Nanjing University of Posts and Telecommunications,Nanjing 210046,China)

The design of measurement matrix and the reconstruction of signal is the key in the study of compressed sensing theory.QR decomposition measurement matrix optimization based on gradient descent method makes it possible to preserve the main information during the process of observation,and the conjugate gradient algorithm is ideal for the reconstruction of the signal.The measurement matrix has been introduced to optimize the conjugate gradient reconstruction algorithm.In view of the conjugate gradient reconstruction algorithm,QR decomposition based on gradient descent method is used to optimize the measurement matrix and a new reconstruction algorithm,a conjugate gradient algorithm based on optimization of the measurement matrix,is obtained.In the improved algorithm,the matrix has larger column independence and lower correlation with sparse matrix,and has better performance with conjugate gradient method.Simulation experiments with Matlab have verified the new algorithm is feasible and effective.The results show that the conjugate gradient optimization algorithm with measurement matrix has been reduced 2～3 times in running time,which is greatly superior to other reconstruction algorithm.

compressive sensing;measurement matrix;conjugate gradient method;gradient descent method;QR decomposition

2016-06-07

2016-09-21 網(wǎng)絡(luò)出版時間：2017-03-13

國家自然科學(xué)基金資助項目(61179027)

蘭明然(1992-)，女，碩士研究生，研究方向為信號處理理論與應(yīng)用；王友國，教授，博士生導(dǎo)師，研究方向為信息理論及應(yīng)用、編碼理論與應(yīng)用、隨機(jī)共振理論與研究。

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

TP301.6

A

1673-629X(2017)05-0073-04

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