基于優化觀測矩陣的共軛梯度改進算法

蘭明然，王友國，鄭丹青

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

基于優化觀測矩陣的共軛梯度改進算法

蘭明然，王友國，鄭丹青

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

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

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

0 引 言

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

研究表明，性能優越的觀測矩陣具有相關性較小的性質，它能夠影響到信號的重構精度。文獻[3-4]提出并驗證了基于梯度下降法的QR分解觀測矩陣優化的可行性和共軛梯度重構算法的優越性。對于文獻[4]中提出的共軛梯度法，若將觀測矩陣的優化引入其中，是否能夠對結果有一個更優的改善。基于此問題，做如下理論分析：

觀測矩陣的優化是基于梯度下降法和QR分解相結合，將其應用在經典重構算法OMP中，優化后的矩陣具有較大的列獨立性以及與稀疏矩陣間相關性較低的特性，有較好的效果；而基于光滑L0范數(SL0)的共軛梯度重構算法是一種比較嚴謹的算法，在此重構算法中，選取的觀測矩陣是跟其他重構算法相同的，其重構性能較好。

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

1 壓縮感知信號重構模型

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

從觀測向量y重構出稀疏信號x的過程是解方程組的過程：y=Φx。但矩陣Φ的維數關系是M

min‖x‖0

s.t.y=Φx

(1)

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

min‖x‖1

s.t.y=Φx

(2)

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

2 基于觀測矩陣優化的重構算法的改進

2.1 基于梯度下降法的QR分解觀測矩陣優化

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

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

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

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

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

2.2 基于共軛梯度法的算法改進

s.t.y=Φx

(3)

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

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

(1)初始點x(1)，k=1，置迭代步數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)輸出最優解x*=x(k+1)。

2.3 基于優化觀測矩陣的共軛梯度算法

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

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

3 實驗仿真與分析

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

圖1 不同壓縮比下三種重構算法的重構時間

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

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

圖2 不同壓縮比下三種重構算法的重構信噪比

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

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

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

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

圖3 原始圖像與三種重構算法生成圖像的對比

4 結束語

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

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

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

[3] 傅迎華.可壓縮傳感重構算法與近似QR分解[J].計算機應用,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范數和修正牛頓法的壓縮感知重建算法[J].計算機輔助設計與圖形學學報,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 網絡出版時間：2017-03-13

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

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

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