李 周 崔 琛

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

1 引言

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

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

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

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

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

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

(1)

(2)

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

CS理論的測(cè)量過(guò)程可以表示為[1]：

(3)

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

(4)

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

(5)

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

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

(6)

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

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

(7)

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

(8)

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

(9)

(10)

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

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

(11)

(12)

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

(13)

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

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

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)

分別討論上式中的三項(xiàng)：

由式(25)可得：

(29)

(30)

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

(31)

由于：

(32)

(33)

因?yàn)?/p>

(34)

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

(35)

(36)

(37)

(38)

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

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

(39)

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

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

輸出：觀測(cè)矩陣Φ。

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

步驟：

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

end

4 實(shí)驗(yàn)與分析

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

4.1 相關(guān)性

仿真實(shí)驗(yàn)1：

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

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

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

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

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

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

(40)

仿真實(shí)驗(yàn)2：

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

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

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

表1 K變化時(shí)三種算法的MSE對(duì)比表

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

仿真實(shí)驗(yàn)3：

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

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

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

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

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

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

4.3 運(yùn)行時(shí)間

仿真實(shí)驗(yàn)4：

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

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

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

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

5 結(jié)論

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

[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] 馬堅(jiān)偉,徐杰,鮑躍全,等, 壓縮感知及其應(yīng)用:從稀疏約束到低秩約束優(yōu)化[J]. 信號(hào)處理, 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]. 信號(hào)處理, 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)的壓縮感知測(cè)量矩陣優(yōu)化方法[J]. 信號(hào)處理, 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)觀測(cè)矩陣的壓縮信道感知[J]. 信號(hào)處理, 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.