王彩云，徐 靜

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

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

王彩云1，徐 靜2

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

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

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

0 引 言

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

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

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

1 CS基本理論

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

原始信號(hào)通過量測(cè)矩陣Φ∈Rm×n得到量測(cè)向量

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

式（12）中步長(zhǎng)更新為

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

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

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

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

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

由式（11）得

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

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

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

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

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

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

步驟3 利用式（12）計(jì)算新的量測(cè)矩陣Φk；

步驟4 利用式（14）和式（15）計(jì)算新步長(zhǎng)βk；

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

實(shí)驗(yàn)1 量測(cè)矩陣為60×64的高斯隨機(jī)矩陣，稀疏基為64×64的離散余弦變換矩陣；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié) 論

本文給出了一種改進(jìn)的基于變步長(zhǎng)梯度下降的量測(cè)矩陣優(yōu)化方法。以降低量測(cè)矩陣與稀疏變換基之間的互相關(guān)性、提高信號(hào)重建精度為目的，借鑒模擬退火的降溫思想，引入學(xué)習(xí)速率因子調(diào)節(jié)步長(zhǎng)的變動(dòng)，改進(jìn)了基于梯度下降的量測(cè)矩陣優(yōu)化方法。實(shí)驗(yàn)結(jié)果表明，本文方法優(yōu)化后的量測(cè)矩陣與稀疏變換基的互相關(guān)系數(shù)以及互相關(guān)系數(shù)的均值都最小，算法的收斂速度加快，圖像重構(gòu)后的PSNR提高，證明本文提出的量測(cè)矩陣優(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．（常虹，盧光躍，馮景瑜．基于壓縮感知的無模糊寬帶測(cè)向技術(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．（趙瑞珍，秦周．一種特征值分解的量測(cè)矩陣優(yōu)化方法［J］．信號(hào)處理，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)化壓縮感知量測(cè)矩陣的方法［J］．電子測(cè)量技術(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é)報(bào)，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 ），女，副教授，博士，主要研究方向?yàn)槔走_(dá)信號(hào)處理、壓縮感知。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-），女，碩士研究生，主要研究方向?yàn)閴嚎s感知、目標(biāo)識(shí)別。E-mail：xujing_ll99＠163．com