王彩云，徐 靜

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

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

王彩云1，徐 靜2

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

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

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

0 引 言

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

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

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

1 CS基本理論

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

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

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

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

2 改進(jìn)的量測矩陣優(yōu)化設(shè)計

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

定義量測矩陣與稀疏基的互相關(guān)系數(shù)［8］為

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

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

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

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

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

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

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

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

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

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

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

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

式（12）中步長更新為

式中，參數(shù)η稱為學(xué)習(xí)速率。

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

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

首先定義矩陣的內(nèi)積公式［20］為

則梯度的計算可以轉(zhuǎn)化為

由式（11）得

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

通過式（14）～式（20）可實現(xiàn)步長更新。

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

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

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

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

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

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

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

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

3 實驗結(jié)果與分析

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

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

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

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

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

圖1 最大互相關(guān)系數(shù)μmax隨γ取值的變化

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

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

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

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

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

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

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

3.2 圖像重構(gòu)仿真

實驗2 參數(shù)設(shè)置：β0＝0.002，η0＝10－3，ε＝0.000 1，γ＝0.9，重構(gòu)算法選取OMP算法。

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

圖4 重構(gòu)圖像的PSNR隨量測數(shù)目m的變化

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

（2）Lena圖像的重構(gòu)效果比較：選取量測值為m＝200，PSNR為圖像重構(gòu)效果好壞的衡量標(biāo)準(zhǔn)，PSNR值越高重構(gòu)效果越好。

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

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

4 結(jié) 論

本文給出了一種改進(jìn)的基于變步長梯度下降的量測矩陣優(yōu)化方法。以降低量測矩陣與稀疏變換基之間的互相關(guān)性、提高信號重建精度為目的，借鑒模擬退火的降溫思想，引入學(xué)習(xí)速率因子調(diào)節(jié)步長的變動，改進(jìn)了基于梯度下降的量測矩陣優(yōu)化方法。實驗結(jié)果表明，本文方法優(yōu)化后的量測矩陣與稀疏變換基的互相關(guān)系數(shù)以及互相關(guān)系數(shù)的均值都最小，算法的收斂速度加快，圖像重構(gò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，F(xiàn)eng J Y．Unambiguous wideband DOA estimation based on compressed sensing［J］.Systems Engineering and Electronics，2013，35（5）：920- 923．（常虹，盧光躍，馮景瑜．基于壓縮感知的無模糊寬帶測向技術(shù)［J］．系統(tǒng)工程與電子技術(shù)，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)工程與電子技術(shù)，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，F(xiàn)erdowsi 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án)軍．一種利用自相關(guān)優(yōu)化壓縮感知量測矩陣的方法［J］．電子測量技術(shù)，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．（張勁東，張弓，潘匯，等．基于濾波器結(jié)構(gòu)的壓縮感知雷達(dá)感知矩陣優(yōu)化［J］．航空學(xué)報，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 ），女，副教授，博士，主要研究方向為雷達(dá)信號處理、壓縮感知。E-mail：wangcaiyun＠nuaa．edu．com

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

2014- 02- 25；

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

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

國家自然科學(xué)基金（61301211）資助課題

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