壓縮感知中觀測矩陣的優(yōu)化算法

李 周 崔 琛

(國防科技大學(xué)電子對抗學(xué)院,安徽合肥 230037)

1 引言

壓縮感知(Compressive Sensing,CS)理論[1]在采樣率遠(yuǎn)小于奈奎斯特采樣率的條件下獲取信號的離散樣本,然后通過非線性優(yōu)化算法重構(gòu)出原始信號。重構(gòu)信號所需的采樣率并不取決于信號的帶寬,而與信號的稀疏度密切相關(guān),因此CS有效降低了信號獲取、存儲及傳輸?shù)拇鷥r[2],引起了越來越多學(xué)者的關(guān)注。

信號的稀疏表示、觀測矩陣的構(gòu)造、重構(gòu)算法是CS理論中三個主要研究方向[3],其中觀測矩陣是影響壓縮感知性能的關(guān)鍵因素之一。觀測矩陣構(gòu)造的目的是如何采樣得到觀測值,并能從觀測值中重構(gòu)出原始信號。文獻(xiàn)[4- 6]對精確重構(gòu)所需觀測矩陣的約束條件進(jìn)行了研究：文獻(xiàn)[4]提出了有限等距性質(zhì)(Restricted Isometry Property, RIP),但判斷觀測矩陣是否符合RIP是組合復(fù)雜度的問題,實際用于觀測矩陣的分析非常困難；文獻(xiàn)[5- 6]提出了相關(guān)性的概念,其含義是觀測矩陣與稀疏基之間的相關(guān)程度。研究表明,通過降低相關(guān)性可以減少CS的重構(gòu)誤差和精確重構(gòu)原始信號所需的觀測數(shù)。

文獻(xiàn)[7]提出了一種對Gram矩陣中絕對值大于限定閾值的非對角元求平均的方法來表示觀測矩陣與稀疏基的相關(guān)性,之后線性收縮 Gram矩陣中絕對值大于限定閾值的非對角元來降低相關(guān)性,取得了較好的實驗效果。但是,該算法對Gram 矩陣進(jìn)行奇異值分解來降階計算下一輪迭代時的Gram矩陣時會產(chǎn)生絕對值較大的相關(guān)系數(shù)。為提高算法平穩(wěn)收斂性,文獻(xiàn)[8]用Welch 界作為觀測矩陣和稀疏基相關(guān)系數(shù)的極限最小值,將非對角元均小于等于Welch界的Gram矩陣作為優(yōu)化目標(biāo),使用梯度下降法逼近最優(yōu)觀測矩陣。但是算法中的步長因子b的選擇對算法性能影響較大,需要由經(jīng)驗確定。

為提高CS的重構(gòu)精度,本文對觀測矩陣與稀疏基的相關(guān)性進(jìn)行研究,提出了一種Gram矩陣的構(gòu)造算法：首先將Gram矩陣與逼近等角緊框架 (Equiangular Tight Frame, ETF)的矩陣差的F范數(shù)作為目標(biāo)函數(shù),之后對目標(biāo)函數(shù)進(jìn)行最優(yōu)化求解在理論上得到最優(yōu)的Gram矩陣的解析式,最后本文在所推導(dǎo)出的最優(yōu)Gram矩陣解析式的基礎(chǔ)上使用迭代來優(yōu)化觀測矩陣。

2 觀測矩陣基本架構(gòu)

假定離散信號r∈Rl×1,若r中最多含有K個非零值且K?l,那么r就稱作K-稀疏的。將K-稀疏的信號集合記為：

(1)

(2)

如果變換后的s符合‖s‖0≤K?l,即r可以用已知的稀疏基中少量的元素線性表示,那么r也被稱作K-稀疏的。

CS理論的測量過程可以表示為[1]：

(3)

對于任意兩個不同的稀疏信號r1,r2∈ΛK,必須滿足Xr1≠Xr2,否則僅僅根據(jù)觀測值無法區(qū)分r1,r2,因此感知矩陣需要滿足一定的條件：對于任意K-稀疏的信號,只要其稀疏度K滿足下式,信號即可準(zhǔn)確地恢復(fù)出來[12]。

(4)

其中μ(X)指X任意兩列xi和xj之間的內(nèi)積絕對值的最大值[7],公式如下：

(5)

然而μ(X)僅表示觀測矩陣與稀疏基之間列向量最大的相關(guān)性,是一種局部的相關(guān)性,因為在X只有某兩列的相關(guān)性比較大,其余各列之間相關(guān)性比較小的情況下,就會出現(xiàn)相關(guān)系數(shù)μ(X)很大,感知矩陣X的性能并不差的情況。

因此文獻(xiàn)[7]提出了表示總體相關(guān)性的t-平均相關(guān)性μt-aν,定義為X所有列向量兩兩之間的內(nèi)積絕對值中大于限定閾值t的部分的平均值,或者是X所有列向量兩兩之間的內(nèi)積絕對值中最大的t%部分的均值,其定義式如下：

(6)

其中g(shù)ij為Gram矩陣G=XTX中的元素,gij為矩陣X的第i列xi與第j列xj的內(nèi)積,Naν為Hav中的元素數(shù)目,即Gram矩陣非對角元|gij|大于t的數(shù)目或者所有|gij|中最大的t%部分的元素數(shù)目。僅闡述μt-aν為X任意兩列內(nèi)積絕對值大于t的平均值時Hav的定義：

Hav{(i,j):gij>t&i≠j}

(7)

為降低X任意兩列的相關(guān)性,即減少Gram矩陣非對角元素的值,文獻(xiàn)[7]采用如下閾值函數(shù)對Gram矩陣G中絕對值大于限定閾值的非對角元進(jìn)行線性收縮,下式中t為閾值,γ為收縮因子。

(8)

當(dāng)X中的列向量兩兩不相關(guān)時,其對應(yīng)的Gram矩陣經(jīng)列歸一化后變成單位陣Il,基于此Elad提出了如下優(yōu)化目標(biāo)函數(shù)[7],使得Gram矩陣盡可能的接近單位陣Il,即使得觀測矩陣與稀疏基的相關(guān)性盡可能為0。

(9)

(10)

僅當(dāng)l≤m(m+1)/ 2時上式成立。

針對于壓縮感知中Gram矩陣不可能為單位陣,Abolghasemi提出了如下優(yōu)化函數(shù)[8]：

(11)

(12)

Abolghasemi將Gram矩陣進(jìn)行如下收縮得到ETF矩陣Gt：

(13)

3 Gram矩陣的構(gòu)造及觀測矩陣的優(yōu)化

本節(jié)將Gram矩陣與逼近ETF的矩陣Gt差的F范數(shù)作為目標(biāo)函數(shù),通過使目標(biāo)函數(shù)對感知矩陣X的偏導(dǎo)等于零得到逼近Gt的一系列Gram矩陣,之后在一系列Gram矩陣中通過最小化目標(biāo)函數(shù)在理論上選出最逼近Gt的Gram矩陣,最后將得到的Gram矩陣經(jīng)閾值函數(shù)處理后作為下一輪迭代的Gt,使用迭代優(yōu)化來降低Gram矩陣中非對角元的大小。

3.1 目標(biāo)函數(shù)

(14)

3.2 Gram矩陣的構(gòu)造

將感知矩陣X進(jìn)行奇異值分解：

X=U(Σx0)VT

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

由式(22)可知G由V11和Σx唯一確定。

(23)

XGt=XXTX

(24)

將式(21)帶入上式可得：

(25)

(26)

(27)

(28)

分別討論上式中的三項：

由式(25)可得：

(29)

(30)

由于式(28)中前兩項均為定值,所以：

(31)

由于：

(32)

(33)

因為

(34)

因為G=XTX為對稱陣,Gt為G經(jīng)閾值函數(shù)處理后的矩陣,所以Gt為對稱陣,其奇異值分解可記為：

(35)

(36)

(37)

(38)

3.3 觀測矩陣的優(yōu)化算法

首先使用下式所示的閾值函數(shù)將Gram矩陣變?yōu)楸平麰TF的矩陣。

(39)

其中ε為限定閾值,ε>μE,sign()為符號函數(shù)。

之后將式(37)求出的最優(yōu)Gram矩陣經(jīng)上述閾值函數(shù)處理后作為下一輪迭代的ETF,迭代優(yōu)化減少感知矩陣的列相關(guān)性。迭代算法的具體步驟如下：

輸出：觀測矩陣Φ。

初始化：迭代次數(shù)k=1。

步驟：

2)對Gk進(jìn)行列歸一化；

end

4 實驗與分析

仿真中相關(guān)參數(shù)如下：m=30,n=l=100,信號的稀疏度K=10,CSElad方法中Gram矩陣收縮變換時非對角線的限定閾值(下文簡稱“閾值”)t=0.4,縮減倍數(shù)γ=0.2；CSAbolghasemi的K_iter=10,步長采用文獻(xiàn)[8]中所用的b=0.05；CSOpt-to-Gt的閾值ε=0.4。為減少隨機(jī)性對實驗結(jié)果造成的影響,每次仿真均為1000次的蒙特卡羅仿真。

4.1 相關(guān)性

仿真實驗1：

CSOpt-to-Gt,CSElad和CSAbolghasemi都是迭代進(jìn)行的算法,將三種算法每次迭代時Gram矩陣的t-平均相關(guān)性μt-aν進(jìn)行對比可以看出在各個算法迭代時t-平均相關(guān)性的變化趨勢,進(jìn)而對比出三種算法在t-平均相關(guān)性這一方面的優(yōu)劣性。t-平均相關(guān)性μt-aν中的參數(shù)t=20%,其含義是Gram矩陣非對角元中最大的20%部分的均值。

由圖1可知,隨著迭代的進(jìn)行三種優(yōu)化算法優(yōu)化的觀測矩陣與稀疏基的相關(guān)性逐漸減少,CSOpt-to-Gt的相關(guān)性最小,CSAbolghasemi的相關(guān)性次之,CSElad的相關(guān)性最大,且CSElad由于降階計算觀測矩陣時會產(chǎn)生比較大的非對角元故隨迭代進(jìn)行其μt-aν變化范圍較大。原因分析如下：

圖1 三種算法得到的Gram矩陣所對應(yīng)的μt-aν隨著迭代次數(shù)的變化

(1)閾值函數(shù)不同：CSElad線性收縮Gram矩陣中較大的非對角元,而CSAbolghasemi與CSOpt-to-Gt直接使用較小的閾值限定Gram矩陣中非對角元最大值,故CSElad的Gram矩陣中非對角元的最大值大于CSAbolghasemi與CSOpt-to-Gt。

(2)優(yōu)化方法不同：CSOpt-to-Gt使用理論上最優(yōu)的Gram矩陣直接求出最逼近Gt的Gram矩陣,其中Gt為Gram矩陣經(jīng)過閾值函數(shù)處理后逼近ETF的矩陣,而CSElad在每次迭代中線性收縮Gram矩陣的非對角元,CSAbolghasemi在每次迭代中在梯度方向上求解Gram矩陣,CSElad和CSAbolghasemi只是利用了不同的方法使Gram矩陣逼近各自的Gt,并不是求解最優(yōu)的Gram矩陣,故CSOpt-to-Gt所求出的Gram矩陣更加接近Gt。

4.2 算法的重構(gòu)性能

(40)

仿真實驗2：

稀疏度K對算法的重構(gòu)性能有直接的影響：在給定觀測次數(shù)的前提下,稀疏度越高,重構(gòu)誤差越大。為了得出稀疏度K對各個算法重構(gòu)性能的影響,仿真稀疏度K由8變化到16時三種算法的MSE的變化情況,如圖2所示。

圖2 稀疏度變化時三種算法的MSE變化情況

圖2中6≤K≤10時三種算法的重構(gòu)誤差曲線重合在一起,下表列出了6≤K≤10時三種算法的重構(gòu)誤差數(shù)值。

表1 K變化時三種算法的MSE對比表

由圖2與表1可知三種算法的MSE隨著稀疏度K的增加而逐漸加大,在稀疏度K<12時CSOpt-to-Gt的重構(gòu)誤差比CSElad和CSAbolghasemi小但優(yōu)勢不明顯,當(dāng)K≥12時CSOpt-to-Gt的重構(gòu)誤差遠(yuǎn)小于CSElad和CSAbolghasemi。

仿真實驗3：

觀測次數(shù)M對壓縮感知的重構(gòu)誤差有直接的影響：M越大,重構(gòu)誤差越??；M越小,重構(gòu)次數(shù)越小。仿真了稀疏度K=10,觀測次數(shù)M從20增加到34時三種算法重構(gòu)誤差的變化情況,如圖3所示。

圖3 觀測次數(shù)變化時三種算法的MSE變化情況

圖3中30≤M≤34時三種算法的重構(gòu)誤差曲線重合在一起,為便于查看,下表列出了30≤M≤34時三種算法的重構(gòu)誤差數(shù)值。

表2 M變化時三種算法的重構(gòu)誤差對比表

由圖3與表2可以看出CSOpt-to-Gt在觀測次數(shù)M≤24時重構(gòu)誤差遠(yuǎn)小于CSElad和CSAbolghasemi,在M≥26時CSOpt-to-Gt重構(gòu)誤差略小于CSElad和CSAbolghasemi。

由仿真實驗2與3可得CSOpt-to-Gt的MSE在稀疏度高或者觀測次數(shù)少的情況下遠(yuǎn)小于CSElad和CSAbolghasemi。這是由于CSOpt-to-Gt產(chǎn)生的觀測矩陣與稀疏基的相關(guān)性小于CSElad和CSAbolghasemi,可以更好地保持不同K稀疏向量之間的距離。在觀測次數(shù)多或者稀疏度K低時觀測矩陣與稀疏基的相關(guān)性較大也可保持不同K稀疏向量之間一定的距離,故三者的MSE差別不大；在觀測次數(shù)少或者稀疏度K高時相關(guān)性必須小才可以保持不同K稀疏向量之間一定的距離,此時CSElad和CSAbolghasemi由于相關(guān)性大不能保持任意不同的K稀疏向量之間一定的距離,故CSOpt-to-Gt的MSE遠(yuǎn)小于CSElad和CSAbolghasemi。

4.3 運(yùn)行時間

仿真實驗4：

為了研究本文所提算法的復(fù)雜度,該仿真實驗統(tǒng)計CSOpt-to-Gt、CSElad和CSAbolghasemi三種算法優(yōu)化后的觀測矩陣與稀疏基的t-平均相關(guān)性μt-aν達(dá)到0.28所需要的運(yùn)行時間。雖然算法的運(yùn)行時間不能嚴(yán)格地定義算法復(fù)雜度,卻可以在一定程度上對算法的復(fù)雜度做出描述。這里,我們的仿真環(huán)境為2.53 GHz英特i5四核處理器、4 GB內(nèi)存Win10 系統(tǒng)下的 MATLAB R2014a。圖4給出了信號長度N變化時各算法對應(yīng)的運(yùn)行時間。

圖4 算法運(yùn)行時間的比較

由圖4可以看出,當(dāng)信號的長度增加時,三種算法的運(yùn)行時間也會增長,其中：CSOpt-to-Gt算法的運(yùn)行時間增長最快,CSAbolghasemi次之,CSElad的運(yùn)行時間增長最慢。原因分析如下：CSOpt-to-Gt在3.3小節(jié)所示的算法中的第(4)步與第(7)步均需要計算運(yùn)算量較大的矩陣奇異值分解；CSAbolghasemi利用內(nèi)層迭代在梯度方向上對觀測矩陣進(jìn)行迭代優(yōu)化,在每一輪的迭代中均需要求解梯度運(yùn)算；CSElad則是將Gram矩陣經(jīng)過閾值函數(shù)收縮后利用計算量小但精度較低的矩陣求逆計算出觀測矩陣。

但總體上看,相對于在相關(guān)性與重構(gòu)精度方面的優(yōu)勢而言,CSOpt-to-Gt增加的運(yùn)行時間是可接受的。

5 結(jié)論

為提高稀疏信號的重構(gòu)精度和觀測矩陣優(yōu)化時的收斂平穩(wěn)性,本文對觀測矩陣與稀疏基的相關(guān)性進(jìn)行研究,提出了一種稀疏基已知的前提下面向觀測矩陣優(yōu)化的Gram矩陣構(gòu)造算法。該算法首先將Gram矩陣與逼近ETF的矩陣差的F范數(shù)作為目標(biāo)函數(shù),后對目標(biāo)函數(shù)進(jìn)行最優(yōu)化求解在理論上得到最優(yōu)Gram矩陣的表達(dá)式,最后將產(chǎn)生的Gram矩陣經(jīng)閾值函數(shù)處理后作為下一輪迭代時目標(biāo)函數(shù)中逼近ETF的矩陣,使用迭代優(yōu)化降低感知矩陣的列相關(guān)性。仿真表明,在相同的實驗條件下,該算法在觀測矩陣與稀疏基的相關(guān)性方面優(yōu)于現(xiàn)有算法,在觀測次數(shù)少或者稀疏度高的情況下具有更高的重構(gòu)精度。如何優(yōu)化閾值函數(shù)來構(gòu)造性能更優(yōu)的觀測矩陣以及如何由最優(yōu)的Gram矩陣得到相應(yīng)的觀測矩陣是下一步的研究方向。

[1] Candes E J, Romberg J, Tao T. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J]. IEEE Transactions on Information Theory, 2004, 52(2):489-509.

[2] 馬堅偉,徐杰,鮑躍全,等, 壓縮感知及其應(yīng)用:從稀疏約束到低秩約束優(yōu)化[J]. 信號處理, 2012, 28(5): 609- 623.

Ma Jianwei, Xu Jie, Bao Yuequan, et al. Compressive Sensing and its Application: from Sparse to Low-rank Regularized Optimization[J]. Signal Processing, 2012, 28(5): 609- 623.(in Chinese)

[3] 王軍華,黃知濤,周一宇,等. 壓縮感知理論中的廣義不相關(guān)性準(zhǔn)則[J]. 信號處理, 2012, 28(5): 675- 679.

Wang Junhua, Huang Zhitao, Zhou Yiyu, et al. Generalized Incoherence Principle in Compressed Sensing[J]. Signal Processing, 2012, 28(5): 675- 679.(in Chinese)

[4] Donoho D L, Elad M. Optimally Sparse Representation in General (Nonorthogonal) Dictionaries via l1Minimization[J]. Proceedings of the National Academy of Sciences of the United States of America, 2003, 100(5):2197.

[5] Gribonval R, Nielsen M. Sparse representations in unions of bases[J]. Information Theory IEEE Transactions on, 2011, 49(12):3320-3325.

[6] Tropp J A, Dhillon I S, Heath R W, et al. Designing structured tight frames via an alternating projection method[J]. IEEE Transactions on Information Theory, 2005, 51(1):188-209.

[7] Elad M. Optimized Projections for Compressed Sensing[J]. IEEE Transactions on Signal Processing, 2007, 55(12):5695-5702.

[8] Abolghasemi V, Ferdowsi S, Sanei S. A gradient-based alternating minimization approach for optimization of the measurement matrix in compressive sensing[J]. Signal Processing, 2012, 92(4):999-1009.

[9] 麻曰亮,裴立業(yè),江樺. 改進(jìn)的壓縮感知測量矩陣優(yōu)化方法[J]. 信號處理, 2017, 33(2): 192-197.

Ma Yueliang, Pei Liye, Jiang Hua. Improved Optimization Algorithm for Measurement Matrix in Compressed Sensing[J]. Journal of Signal Processing, 2017, 33(2): 192-197.(in Chinese)

[10]肖小潮, 鄭寶玉, 王臣昊. 基于最優(yōu)觀測矩陣的壓縮信道感知[J]. 信號處理, 2012, 28(1):67-72.

Xiao Xiaochao, Zheng Baoyu, Wang Chenhao. Compressed Channel Estimation based on Optimized Measurement Matrix[J]. Signal Processing, 2012, 28(1): 67-72. (in Chinese)

[11]Kwon S, Wang J, Shim B. Multipath Matching Pursuit[J]. IEEE Transactions on Information Theory, 2014, 60(5):2986-3001.