改進的壓縮感知量測矩陣優(yōu)化方法

王彩云，徐 靜

（1．南京航空航天大學航天學院，江蘇南京210016；2．南京航空航天大學電子信息工程學院，江蘇南京210016）

改進的壓縮感知量測矩陣優(yōu)化方法

王彩云1，徐 靜2

（1．南京航空航天大學航天學院，江蘇南京210016；2．南京航空航天大學電子信息工程學院，江蘇南京210016）

壓縮感知理論中信號的重建要求量測矩陣與稀疏變換基之間的互相關性要盡可能小。以降低二者互相關性為目的，研究了一種改進的基于變步長梯度下降的量測矩陣優(yōu)化方法。該方法利用梯度下降法更新步長，并基于模擬退火中的降溫思想引入學習速率因子來進一步調節(jié)步長的變化，提高算法的收斂速度，改善算法的性能。仿真結果表明，使用變步長梯度下降法優(yōu)化后的量測矩陣與稀疏變換基的互相關系數在零附近的分布更加集中，量測矩陣的優(yōu)化速度快并且重構圖像的峰值信噪比提高。因此，所提方法優(yōu)化所得的量測矩陣無論是降低互相關性還是提高圖像重建質量都具有良好的性能。

壓縮感知；量測矩陣；梯度下降；變步長；優(yōu)化

0 引 言

壓縮感知（compressed sensing，CS）［13］是信號及圖像處理領域誕生的一種嶄新的數據采樣理論，該理論突破了傳統(tǒng)奈氏采樣定理，在信號采樣的同時實現信號壓縮。由于CS理論大大降低了信息采集量、采樣時間和存儲空間，受到許多研究者的高度關注［46］。CS理論的核心環(huán)節(jié)是信號采樣和重建，而構造合理有效的量測矩陣對于量測值獲取和信號重建起著至關重要的作用。

CS理論研究表明，信號的精確恢復要求感知矩陣滿足有限等距性（restricted isometry property，RIP）［7］，該性質等價于量測矩陣與稀疏基不相關［8］。近年來，針對降低量測矩陣與稀疏變換基的互相關性已開展一些研究。一類是有效投影法［9］，該方法取稀疏變換基的奇異值向量的部分列向量組成量測矩陣，從而增強稀疏變換基與量測矩陣的非相干性。一類方法是基于Gram矩陣的迭代優(yōu)化方法，如：文獻［10］提出基于Gram矩陣的t平均互相關性，通過閾值縮放處理減小非對角線元素；文獻［11］提出基于Gram矩陣的整體互相關系數，采用特征值分解方法減小互相關系數；文獻［12- 13］利用梯度下降迭代法使得Gram矩陣接近于單位陣；文獻［14］采用特征值分解方法使Gram矩陣逼近于單位陣；文獻［15］通過等角緊框架結構，使Gram矩陣的非對角線元素都等于矩陣的最大互相關系數。此外，文獻［16］提出量測矩陣與稀疏字典聯合優(yōu)化，字典學習和量測矩陣優(yōu)化交替進行，從而降低二者互相關性。上述文獻研究表明通過減小互相關性的量測矩陣優(yōu)化方法可以得到性能更優(yōu)的量測矩陣，從而提高信號的重建精度，減小壓縮比。

本文研究了一種改進的基于變步長梯度下降的量測矩陣優(yōu)化方法。該方法在研究由量測矩陣與稀疏基構造的Gram矩陣元素的基礎上，基于模擬退火中的降溫思想，引入學習速率因子調節(jié)步長變化，即用變步長的梯度下降法減小二者的互相關性，用于圖像重建也取得了較高的峰值信噪比（peak signal to noise ratio，PSNR）。

1 CS基本理論

設x∈Rn為長度為n的一維離散時間信號，則信號x在正交基Ψ＝｛Ψ1，Ψ2，…，Ψn｝上的線性組合表示為

原始信號通過量測矩陣Φ∈Rm×n得到量測向量

式中，D＝ΦΨ為感知矩陣。利用重建算法恢復原始信號x，即求解式（3）的1-范數優(yōu)化問題。

由于m?n，所以式（3）是一個NP-hard問題。為解決此問題，通常是尋找一組稀疏的系數矢量解。典型的求解算法有：基追蹤（basis pursuit，BP）算法［17］，匹配追蹤（matching pursuit，MP）和正交匹配追蹤（orthogonal MP，OMP）算法［18］等。

2 改進的量測矩陣優(yōu)化設計

2.1 量測矩陣優(yōu)化模型設計

定義量測矩陣與稀疏基的互相關系數［8］為

由于D＝ΦΨ，因此互相關性等價為感知矩陣D各列間歸一化互相關系數的最大值［19］，即

式（14）中，梯度▽βk－1J（Φk）的計算公式推導過程如下：

定義Gram矩陣G＝^DT^D，^D是D列單位化以后的矩陣，則最大互相關系數為G矩陣的非對角元素絕對值的最大值，即

由于μmax只能描述G矩陣的局部相關性，因此引入平均互相關系數來描述其整體相關性，即

式（6）中，若感知矩陣D的列向量相互正交，即μmax＝0，則G矩陣近似于單位矩陣，即

式（8）左乘Ψ和右乘ΨT得［12］

對ΨΨT進行特征值分解VUVT＝ΨΨT，代入式（9）得

令T＝VU，則量測矩陣優(yōu)化模型為

由以上分析可知，滿足式（11）的量測矩陣與稀疏變換基的互相關系數最小。

2.2 量測矩陣優(yōu)化算法設計

本節(jié)介紹一種改進的基于變步長梯度下降的量測矩陣優(yōu)化算法。首先對量測矩陣Φ進行近似QR分解以降低矩陣的線性相關性；然后利用最速梯度下降法對量測矩陣進行自適應更新，即沿目標函數最速下降的方向對其進行調整，即φij←φij－ξ?J／?φij，ξ＞0為步長，可得?J／?Φ＝4ΦT（TTΦΤΦT－U）TT，因此更新方程為

式中，k是循環(huán)迭代次數；β＝4ξ是新的步長參數。

式（12）中步長更新為

式中，參數η稱為學習速率。

學習速率太小則算法的收斂性容易得到保證，但收斂速度較慢；學習速率太大則收斂速度快，但算法可能不穩(wěn)定。針對以上問題，本文中引入學習速率因子γ實現學習速率η的自適應變化。

模擬退火方法中經典的降溫公式為Tk＝γ×Tk－1，式中，γ為降溫系數（常取稍小于1的數值），顯然隨著迭代次數k的增加，溫度T以相同速率減小。本文中迭代初期希望步長β變動較大，需要較大的學習速率η，隨著迭代的進行，越來越接近最優(yōu)點，則希望β變動較小，需要較小的η，以便在最優(yōu)值所在的小范圍內搜索尋優(yōu)。因此學習速率η的變化可以通過降溫系數γ實現，本文中定義為學習速率因子，γ的引入使學習速率η在迭代過程中不斷減小，從而實現步長β隨著迭代由大到小的變化，此時步長β的更新公式為

首先定義矩陣的內積公式［20］為

則梯度的計算可以轉化為

由式（11）得

由式（12）得假設Lk－1＝Φk－1T（TTΦTk－1Φk－1T－U）TT，那么梯度的最終計算公式為

通過式（14）～式（20）可實現步長更新。

本算法中除了使用自適應學習速率以外，還明確設置了迭代終止條件，即當目標函數值在相鄰迭代過程中的相對誤差E滿足式（21），則迭代終止，得到優(yōu)化的量測矩陣。

式中，ε為門限參數，一般取10－3或更小的常數。終止條件的設置彌補了固定循環(huán)次數的不足，節(jié)省了計算時間，提高了算法性能。本文核心算法步驟如下：

步驟1 產生隨機量測矩陣Φ∈Rm×n，稀疏基Ψ∈Rn×n，初始步長β0，初始學習速率η0，學習速率因子γ，迭代終止門限ε；

步驟2 對ΨΨT進行特征值分解得到ΨΨT＝VUVT，對量測矩陣Φ進行QR分解，令T＝VU，k＝1；

步驟3 利用式（12）計算新的量測矩陣Φk；

步驟4 利用式（14）和式（15）計算新步長βk；

步驟5 計算相鄰迭代過程中目標函數的相對誤差E，若E＜ε滿足，迭代終止，執(zhí)行步驟6；否則，令k＝k＋1，執(zhí)行步驟2～步驟4，繼續(xù)迭代；

步驟6 輸出優(yōu)化后的量測矩陣^Φ。

3 實驗結果與分析

針對上述的算法，本節(jié)通過仿真實驗驗證算法的正確性和有效性。仿真條件設置如下：

實驗1 量測矩陣為60×64的高斯隨機矩陣，稀疏基為64×64的離散余弦變換矩陣；

實驗2 選取256×256的Lena圖像為實驗對象，量測矩陣為m×256的高斯隨機矩陣和循環(huán)矩陣，量測數目m在20～200范圍內變動，稀疏基為256×256離散小波變換矩陣。

3.1 量測矩陣優(yōu)化仿真

實驗1 參數設置：β0＝0.01，η0＝10－2，ε＝0.001，γ＝0.5～0.9。圖1為在學習速率因子γ取不同值時，最大互相關系數μmax的變化曲線。

圖1 最大互相關系數μmax隨γ取值的變化

圖1 表明，隨著迭代次數的增加，μmax的值不斷減小，且學習速率因子γ的取值越大，在μmax最終收斂取值相當時，γ＝0.9時的收斂速度最快。表1所示γ＝0.9時，本文方法與前人方法的μmax，μav的比較。圖2給出運算時間t隨量測數目m的變化曲線。

表1 不同方法所得的μmax，μav比較

圖2 運算時間t隨量測數目m的變化曲線

將不同方法優(yōu)化后的量測矩陣與稀疏變換基的互相關系數的絕對值以0．025為間隔進行統(tǒng)計，給出統(tǒng)計直方圖如圖3所示。

圖3 量測矩陣與稀疏基之間的互相關系數統(tǒng)計分布

由表1可見，本文算法得到的量測矩陣與稀疏基的最大互相關系數、互相關系數的平均值均最小，說明本文算法在降低最大互相關系數的同時使得互相關系數的平均值也明顯降低，意味著信號恢復時所需量測數目更少。由圖2可見，量測值在20～60間變動時，不同方法的運算時間的變化情況，可以看出，本文算法的運算時間低于其他3種方法，運算時間降低，表明算法性能得到提高。

圖3表明，經過本文優(yōu)化后的相關系數的分布范圍縮小且在零值附近的分布更加集中，達到降低互相關系數的目的。以上分析說明經過本文方法處理后整體性能得到提升。

3.2 圖像重構仿真

實驗2 參數設置：β0＝0.002，η0＝10－3，ε＝0.000 1，γ＝0.9，重構算法選取OMP算法。

（1）量測數目m對重構效果的影響分析：實驗中量測值m從20到200變化，重構圖像PSNR隨m的變化曲線如圖4所示。

圖4 重構圖像的PSNR隨量測數目m的變化

由圖4可知，經過本文方法優(yōu)化后的量測矩陣用于重建圖像的PSNR顯然高于其他兩種方法，更高于未經優(yōu)化的量測矩陣圖像重建效果。

（2）Lena圖像的重構效果比較：選取量測值為m＝200，PSNR為圖像重構效果好壞的衡量標準，PSNR值越高重構效果越好。

圖5給出了量測值m為200時Lena圖像重建效果。由PSNR值對比可知，本文方法重建圖像的質量優(yōu)于Abolghasemi和王紅梅方法重建圖像的質量。此外，量測數一定時本文方法迭代次數平均為25次，比其他兩種方法的迭代次數至少減少50%，優(yōu)化效率提高。

圖5 量測矩陣為200×256的高斯矩陣重建圖像

4 結 論

本文給出了一種改進的基于變步長梯度下降的量測矩陣優(yōu)化方法。以降低量測矩陣與稀疏變換基之間的互相關性、提高信號重建精度為目的，借鑒模擬退火的降溫思想，引入學習速率因子調節(jié)步長的變動，改進了基于梯度下降的量測矩陣優(yōu)化方法。實驗結果表明，本文方法優(yōu)化后的量測矩陣與稀疏變換基的互相關系數以及互相關系數的均值都最小，算法的收斂速度加快，圖像重構后的PSNR提高，證明本文提出的量測矩陣優(yōu)化方法是可行且有效的。

［1］Donoho D．Compressed sensing［J］.IEEE Trans.on Information Theory，2006，52（4）：1289- 1306.

［2］Candes E，Romberg J，Tao T．Robust uncertainty principles：exact signal reconstruction from highly incomplete frequency information［J］.IEEE Trans.on Information Theory，2006，52（2）：489- 509.

［3］Elad M，Michal A．Image denoising via sparse and redundant representations over learned dictionaries［J］.IEEE Trans.on Image Processing，2006，15（12）：3736- 3745.

［4］Chang H，Lu G Y，Feng J Y．Unambiguous wideband DOA estimation based on compressed sensing［J］.Systems Engineering and Electronics，2013，35（5）：920- 923．（常虹，盧光躍，馮景瑜．基于壓縮感知的無模糊寬帶測向技術［J］．系統(tǒng)工程與電子技術，2013，35（5）：920- 923．）

［5］Zhou T Y，Tao D C．1-bit hamming compressed sensing［C］∥Proc.of the IEEE International Symposium Information Theory，2012：1862- 1866.

［6］Ling X X，Wei Z H，Xiao L，et al．Compressive sensing image reconctruction algorithm based on non-local regularization［J］. Systems Engineering and Electronics，2013，35（1）：196- 202．（李興秀，韋志輝，肖亮，等．非局部正則化的壓縮感知圖像重建算法［J］．系統(tǒng)工程與電子技術，2013，35（1）：196- 202．）

［7］Candes E．The restricted isometry property and its implications for compressed sensing［J］.Comptes Rendus Mathematique，2008，346（9／10）：589- 592.

［8］Baraniuk R．A lecture on compressive sensing［J］.IEEE Signal Processing Magazine，2007，24（4）：118- 121.

［9］Nhat V D M，Vo D，Challa S，et al．Efficient projection for compressed sensing［C］∥Proc.of the Computer and Information Science，2008：322- 327.

［10］Elad M．Optimized projections for compressed sensing［J］. IEEE Trans.on Signal Processing，2007，55（12）：5695- 5702.

［11］Zhao R Z，Qin Z．An optimization method for measurement matrix based on eigenvalue decomposition［J］.Signal Processing，2012，28（5）：654- 656．（趙瑞珍，秦周．一種特征值分解的量測矩陣優(yōu)化方法［J］．信號處理，2012，28（5）：654- 656．）

［12］Abolghasemi V，Ferdowsi S，Makkiabadi B，et al．A robust approach for optimization of the measurement matrix in compressed sensing［C］∥Proc.of the International Workshop on Cognitive Information Processing，2010：388- 392.

［13］Wang H M，Yan J．Optimization method of measurement matrix used of mutual coherence matrix in the compressed sensing［J］. Electronic Measurement Technology，2012，35（11）：117- 118．（王紅梅，嚴軍．一種利用自相關優(yōu)化壓縮感知量測矩陣的方法［J］．電子測量技術，2012，35（11）：117- 118．）

［14］Duarte-Carvajalino J M，Sapiro G．Learning to sense sparse signals：simulataneous sensing matrix and sparsifying dictionary optimization［J］.IEEE Trans.on Image Processing，2009，18（7）：1395- 1408.

［15］Xu J P，Pi Y M，Cao Z J．Optimized projection matrix for compressive sensing［J］.Eurasip Journal on Advances in Signal Processing，2010：1- 9.

［16］Endra M．Joint optimization of measurement matrix and sparse dictionary in compressive sensing［C］∥Proc.of the International Conference on Chemistry and Chemical Engineering，2012：3- 5.

［17］Chen S S，Donoho D L，Saunders M A．Atomic decomposition by basis pursuit［J］．Society for Industrial and Applied Mathematics Journal on Scientific Computing，1998，20（1）：33- 61.

［18］Huang S S，Zhu J B．Recovery of sparse signals using OMP and its variants：convergence analysis based on RIP［J］.Inverse Problems，2011，27（3）：2- 10.

［19］Zhang J D，Zhang G，Pan H，et al．Optimized sensing matrix design of filter structure based compressed sensing radar［J］. Acta Aeronautica et Astronautica Sinica，2013，34（4）：866-868．（張勁東，張弓，潘匯，等．基于濾波器結構的壓縮感知雷達感知矩陣優(yōu)化［J］．航空學報，2013，34（4）：866- 868．）

［20］Yuan L X，Wang W W，Chambers J A．Variable step-size sign natural gradient algorithm for sequential blind source separation［J］.IEEE Signal Processing Letters，2005，12（8）：589- 592.

Improved optimization algorithm for measurement matrix in compressed sensing

WANG Cai-yun1，XU Jing2
（1.College of Astronautics，Nanjing University of Aeronautics&Astronautics，Nanjing 210016，China；2.College of Electronic and Information Engineering，Nanjing 210016，China）

The signal recovery performance of compressed sensing（CS）requires that the cross correlations between the measurement matrix and sparse transformed matrix should be as small as possible．In order to reduce the cross correlations，an varied step gradient descent algorithm is studied and si-mulated annealing（SA）learning rate factor is introduced to adjust the step function．The simulation results demonstrate that due to the adaptive adjustment of step length in the iteration process，the speed of optimizing matrix is fast，more mutual coherence coefficients are distributed around zero，and the peak signal to noise ratio of reconstructed image is improved with the optimized measurement matrix．The improved algorithm has good performance in achieving lower mutual coherence and improving reconstruction performance．

compressed sensing（CS）；measurement matrix；gradient descent；varied step；optimization

TP751

A

10．3969／j．issn．1001-506X．2015．04．05

王彩云（1975 ），女，副教授，博士，主要研究方向為雷達信號處理、壓縮感知。E-mail：wangcaiyun＠nuaa．edu．com

1001-506X（2015）04-0752-05

2014- 02- 25；

2014- 09- 18；網絡優(yōu)先出版日期：2014- 11- 21。

網絡優(yōu)先出版地址：http：／／w ww．cnki．net／kcms／detail／11．2422．TN．20141121．0937．009．html

國家自然科學基金（61301211）資助課題

徐 靜（1989-），女，碩士研究生，主要研究方向為壓縮感知、目標識別。E-mail：xujing_ll99＠163．com