胡 強(qiáng)，林 云

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065； 2.移動通信技術(shù)重慶市重點實驗室(重慶郵電大學(xué))，重慶 400065)

基于觀測矩陣優(yōu)化的自適應(yīng)壓縮感知算法

胡 強(qiáng)1*，林 云2

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065； 2.移動通信技術(shù)重慶市重點實驗室(重慶郵電大學(xué))，重慶 400065)

為提高傳統(tǒng)壓縮感知(CS)恢復(fù)算法的抗噪性能，結(jié)合觀測矩陣優(yōu)化和自適應(yīng)觀測的思想，提出一種自適應(yīng)壓縮感知(ACS)算法。該算法將觀測能量全部分配在由傳統(tǒng)CS恢復(fù)算法估計的支撐位置，由于估計支撐集中包含支撐位置，這樣可有效提高觀測信噪比(SNR)；再從優(yōu)化觀測矩陣的角度推導(dǎo)出最優(yōu)的新觀測向量，即其非零部分設(shè)計為Gram矩陣的特征向量。仿真結(jié)果表明，隨著觀測數(shù)增大,Gram矩陣非對角元素的能量增速小于傳統(tǒng)CS算法，并且分別在觀測次數(shù)、稀疏度和SNR相同的條件下，所提算法的重構(gòu)歸一化均方誤差低于傳統(tǒng)CS恢復(fù)算法10 dB以上，低于典型的貝葉斯方法5 dB以上。分析表明，所提自適應(yīng)觀測機(jī)制可有效提高傳統(tǒng)CS恢復(fù)算法的能量利用效率和抗噪性能。

自適應(yīng)壓縮感知；觀測矩陣優(yōu)化；觀測信噪比；特征分解；Gram矩陣

0 引言

壓縮感知(Compressed Sensing, CS)[1-3]技術(shù)因其高效的信息采樣機(jī)制，已被廣泛應(yīng)用到信道估計、神經(jīng)網(wǎng)絡(luò)、雷達(dá)信號處理、核磁共振成像等領(lǐng)域。傳統(tǒng)壓縮感知技術(shù)采用非自適應(yīng)的觀測過程，即通過預(yù)先設(shè)計觀測矩陣并對信號進(jìn)行一次性觀測，觀測向量的能量均勻分配，這樣做使得觀測向量每次都對整個信號域觀測，感知能量大部分被用來觀測不含非零元素的位置，造成能量利用效率和抗噪性能不高。

為了提高傳統(tǒng)CS算法的能量效率和抗噪性能，研究者們對自適應(yīng)壓縮感知(Adaptive CS, ACS)展開了一系列研究，其主要思想是根據(jù)以前的觀測值自適應(yīng)地設(shè)計下一步的觀測向量，可在觀測過程中剔除一些非支撐坐標(biāo)，使感知能量集中在含有支撐坐標(biāo)的少數(shù)位置。目前的一些典型的自適應(yīng)算法主要分別從提高觀測信噪比或優(yōu)化觀測矩陣出發(fā)考慮，并未將兩者有機(jī)地結(jié)合。貝葉斯壓縮感知(Bayesian Compressed Sensing, BCS)[4-5]在相關(guān)向量機(jī)的基礎(chǔ)上，根據(jù)貝葉斯推斷和最小微分熵來指導(dǎo)設(shè)計下一步觀測向量，由于高維求逆，導(dǎo)致計算量較大。文獻(xiàn)[6]建立一種信息貪婪(Info-Greedy)自適應(yīng)壓縮感知框架，觀測向量設(shè)計依據(jù)最大化當(dāng)前觀測值與信號相對于以前的觀測值的最大條件互信息增益，需要信號概率分布的參數(shù)先驗。BCS和文獻(xiàn)[6]中算法所設(shè)計的新觀測向量均具有隨機(jī)性，這可能導(dǎo)致每步的信噪比增益不穩(wěn)定，并且具有較高的復(fù)雜度。文獻(xiàn)[7]考慮數(shù)據(jù)間的關(guān)聯(lián)性，提出一種利用信號自相關(guān)性的自適應(yīng)觀測方案。文獻(xiàn)[8]考慮到實際應(yīng)用的物理約束，預(yù)先設(shè)置觀測池，提出一種能夠根據(jù)支撐集估計情況自適應(yīng)地從觀測池中選擇原子的感知方案。文獻(xiàn)[9]從動態(tài)規(guī)劃的角度利用粒子群算法設(shè)計了一種觀測矩陣更新機(jī)制。文獻(xiàn)[10]在生物信息研究中提出可自適應(yīng)選擇基向量的動態(tài)旋鈕框架。上述各自適應(yīng)算法雖然從提高觀測信噪比的角度實現(xiàn)了較好的抗噪恢復(fù)性能，但未考慮優(yōu)化觀測矩陣本身所能帶來的性能增益。文獻(xiàn)[11-13]在連續(xù)觀測過程中，將Gram矩陣向?qū)顷噧?yōu)化，通過迭代收縮Gram矩陣非對角元素，完成對觀測矩陣的優(yōu)化，有效提高了信號重構(gòu)概率和抗噪性能；但這些算法未考慮提高觀測信噪比可能帶來的性能增益。

綜上，自適應(yīng)觀測與優(yōu)化觀測矩陣均能提高傳統(tǒng)CS算法的重構(gòu)精度。為綜合利用這二者的優(yōu)勢，并提高傳統(tǒng)CS算法的能量利用效率和抗噪性能，本文設(shè)計一種自適應(yīng)觀測機(jī)制，將觀測能量集中估計支撐集的位置，以提高觀測信噪比，同時將Gram矩陣向?qū)顷噧?yōu)化，以減小其他位置的干擾。仿真實驗結(jié)果表明，本文所提觀測機(jī)制可有效提高觀測信噪比，減小非對角元素能量，并且能夠有效改善傳統(tǒng)CS重構(gòu)算法的抗噪性能。

1 壓縮感知基本理論

假設(shè)信號x僅有K個非零元素，其他元素均為0，則稱信號x是K-稀疏的，并定義信號x的支撐集：

Λ={i|xi≠0}

(1)

其中：xi為信號x的第i個元素，易知|Λ|=K，此處|·|表示集合中元素的個數(shù)。若信號并非稀疏，如果可將信號在某個變換域Ψ展開，即x=Ψc，若變換系數(shù)c是稀疏的，則仍可應(yīng)用壓縮感知理論。

設(shè)觀測矩陣為Φ，觀測過程可表示為：

y=Φx+w=ΦΨc+w=Θc+w

(2)

2 利用觀測矩陣優(yōu)化的自適應(yīng)觀測

2.1 理論推導(dǎo)

(3)

s.t.aTa=1

(4)

s.t.aTa=1

其中‖·‖F(xiàn)表示Frobenius范數(shù)。利用拉格朗日乘子法，式(4)等價于：

(5)

其中λ是拉格朗日常數(shù)。式(5)中代價函數(shù)對向量a求導(dǎo)，可得：

2aT(ATA-I+aaT)-2λaT=

2(aTATA-aT+aT)-2λaT=

2(aTATA-λaT)

(6)

其中tr{·}表示矩陣的跡，令式(6)等于0，則可得：

ATAa=λa

(7)

即下一步觀測向量a是Gram矩陣ATA對應(yīng)于特征值λ的特征向量：

a=ui;i=1,2,…,N

(8)

其中，ui為對應(yīng)于特征值λi的特征向量。因為ATA是奇異的，即rank(ATA)=M

a=ui;i=1,2,…,M

(9)

將式(9)代入式(5)，可得：

(10)

(11)

(12)

s.t.aTa+bTb=1

其中，I為N×N的單位矩陣。為完成自適應(yīng)觀測，設(shè)置b=0，這相當(dāng)于把全部能量都分配到估計支撐位置，估計支撐集中可能含有少量非支撐坐標(biāo)，這些非支撐坐標(biāo)會獲得少量能量分配，這種分配方式相比將能量分配在整個信號域的方案獲得信噪比增益高很多；并且，由于噪聲觀測值的隨機(jī)性，在后續(xù)觀測中這些坐標(biāo)將會被逐步取代。于是式(12)化簡為：

(13)

s.t.aTa=1

其中,IA∈RK×K、IB∈R(N-K)×(N-K)表示單位陣，又a只影響ATA+aaT-IA,從而式(13)等價于：

(14)

s.t.aTa=1

問題式(14)與式(4)具有相同的形式，易知其解為：

a=u

(15)

2.2 自適應(yīng)觀測機(jī)制

若考慮將a設(shè)計為隨機(jī)觀測向量，每次觀測仍將能量全部分配給a，這樣仍能帶來觀測信噪比的增益，但a的隨機(jī)性并不能保證它是最優(yōu)的，即它不能保證J(a)將取得最小值，也未實現(xiàn)觀測矩陣的優(yōu)化。若按照式(11)設(shè)計新觀測向量每一步都可以保證J(a)最小，完成了觀測矩陣優(yōu)化。

輸入 初始觀測矩陣Φ[0](已經(jīng)歸一化)，初始觀測值y[0]，總觀測數(shù)Mmax；

初始化 步數(shù)i=0。

5)回到步驟1)，i=i+1，繼續(xù)迭代，直到i=Mmax-M0。

上述機(jī)制的計算復(fù)雜度主要集中在獲取估計支撐集和特征值分解，參與特征值分解的矩陣維度在K×K，這遠(yuǎn)低于貝葉斯方法求逆的矩陣維度N×N，即本文算法運(yùn)算較之更快。又因為K?N，復(fù)雜度可忽略不計，采用貪婪算法獲得估計支撐集的復(fù)雜度一般在O(KMmaxN)，因為每一步觀測都要運(yùn)行貪婪算法，那么算法復(fù)雜度為O(KM0N+K(M0+1)N+…+KMmaxN)，顯然高于貪婪算法，這是提高貪婪算法抗噪性能付出的代價。若減小自適應(yīng)觀測步數(shù)，在一定程度上，這種代價是可以接受的。

3 仿真實驗與分析

為說明自適應(yīng)觀測和觀測矩陣優(yōu)化對傳統(tǒng)CS恢復(fù)算法的抗噪性能的改善作用，仿真實驗對SP算法及其相應(yīng)自適應(yīng)算法進(jìn)行對比分析。為簡化描述，將a設(shè)計為隨機(jī)向量且采用SP恢復(fù)信號的自適應(yīng)機(jī)制命名為隨機(jī)自適應(yīng)SP算法(Random Adaptive SP, R-ASP)，將a按式(15)設(shè)計且采用SP恢復(fù)信號的機(jī)制命名為優(yōu)化的自適應(yīng)SP算法(Optimized Adaptive SP, O-ASP)。為檢驗本文所提觀測方案與其他類似方案的優(yōu)劣，加入與BCS的性能對比，BCS初始觀測數(shù)與O-ASP相同，其他參數(shù)參考文獻(xiàn)[4]。

為評價本文所提自適應(yīng)壓縮感知算法的恢復(fù)性能，實驗采用相對支撐集誤差(Relative Support Set Error, RSSE)和歸一化均方誤差(Normalized Mean Square Error, NMSE)作為評價標(biāo)準(zhǔn)，它們可分別通過式(16)、(17)計算：

(16)

(17)

(18)

其中diag(·)表示矩陣的對角元素構(gòu)成的對角陣。

測試信號x為長為N的K-稀疏信號，且其非零項相互獨立且服從均值為0、方差為1的高斯分布。觀測矩陣元素相互獨立且服從均值為0、方差為1的高斯分布并對其行向量歸一化，那么總觀測能量為Mmax。定義觀測信噪比為：

(19)

(20)

其中，ynad、yad分別表示非自適應(yīng)觀測和自適應(yīng)觀測所得觀測值向量。對于非自適應(yīng)算法有yad=ynad，則GSNR=0。各實驗分別進(jìn)行500次蒙特卡洛仿真。

圖1(a)為不同算法重構(gòu)NMSE隨觀測總數(shù)變化曲線；圖1(b)為隨機(jī)觀測矩陣和自適應(yīng)觀測矩陣(采用SP估計支撐集)非對角元素的能量EOE隨觀測總數(shù)變化曲線;圖1(c)為各算法信噪比增益GSNR與觀測總數(shù)的關(guān)系。圖1中，測試信號長度N=256，稀疏度K=5，自適應(yīng)算法的初始觀測數(shù)M0=50，信噪比SNR=10 dB。

圖1 不同算法重構(gòu)參數(shù)與觀測總數(shù)的關(guān)系Fig. 1 Relationship of reconstruction parameters and total number of observations for different algorithms

從圖1(a)易知，自適應(yīng)觀測對傳統(tǒng)CS恢復(fù)算法的重構(gòu)NMSE改善在10 dB以上，并且隨著觀測數(shù)增多改善越明顯；R-ASP、O-ASP算法的重構(gòu)NMSE低于BCS；O-ASP性能優(yōu)于R-ASP，說明優(yōu)化觀測矩陣的策略是有效的。從圖1(b)可以看出，非自適應(yīng)的隨機(jī)觀測和采用隨機(jī)方式設(shè)計新觀測向量的自適應(yīng)觀測的非對角元素能量都隨著觀測數(shù)增多而增大，而采用優(yōu)化觀測向量的BCS和O-ASP卻幾乎保持不變，并且O-ASP的非對角元素能量低于BCS，這是因為BCS設(shè)計新觀測向量并未考慮觀測矩陣的優(yōu)化。從圖1(c)可知，自適應(yīng)算法R-ASP、O-ASP和BCS的信噪比增益逐漸增大，而未實現(xiàn)自適應(yīng)觀測的SP算法沒有信噪比增益；O-ASP的信噪比增益低于R-ASP而高于BCS，因為考慮了觀測矩陣優(yōu)化，O-ASP的重構(gòu)性能仍優(yōu)于R-ASP；因為BCS每一步的觀測能量分配的位置一般多于K個，使其觀測信噪比增益低于R-ASP和O-ASP。

圖2為不同算法的RSSE與觀測數(shù)的變化趨勢，其中測試信號長度N=256，稀疏度K=15，自適應(yīng)算法的初始觀測數(shù)M0=50，信噪比SNR=10 dB。由圖2可以發(fā)現(xiàn)，自適應(yīng)算法BCS、R-ASP、O-ASP比非自適應(yīng)算法SP具有更小的RSSE，當(dāng)觀測數(shù)較少時(M<60)，BCS的RSSE相對最小，但誤差仍較大，而隨著觀測數(shù)增多，O-ASP性能則優(yōu)于BCS，且RSSE較小。而未采用觀測矩陣優(yōu)化的R-ASP直到M>80時RSSE才低于BCS，這進(jìn)一步說明在自適應(yīng)觀測過程中考慮觀測矩陣優(yōu)化的策略是有效的。

圖2 不同算法重構(gòu)RSSE與觀測總數(shù)的關(guān)系Fig. 2 Relationship of reconstruction RSSE and total number of observations for different algorithms

圖3為不同算法重構(gòu)NMSE與稀疏度的關(guān)系，其中測試信號長度N=256，自適應(yīng)算法的初始觀測數(shù)M0=70，總觀測數(shù)Mmax=128，信噪比SNR=15 dB。由圖3可知:隨著稀疏度增大，各算法重構(gòu)NMSE均增大，自適應(yīng)算法BCS、R-ASP、O-ASP的NMSE一般低于SP;但BCS隨著K增大性能迅速惡化，甚至差于SP(當(dāng)K>27)，R-ASP和O-ASP仍然具有最小的NMSE，而O-ASP的NMSE始終低于R-ASP，說明觀測矩陣優(yōu)化策略對恢復(fù)大稀疏度的信號具有優(yōu)勢。

圖3 不同算法重構(gòu)NMSE與稀疏度的關(guān)系Fig. 3 Relationship of reconstruction NMSE and parsity for different algorithms

圖4為不同算法重構(gòu)NMSE隨信噪比變化曲線，其中測試信號長度N=256，稀疏度K=5，自適應(yīng)算法的初始觀測數(shù)M0=50，總觀測數(shù)Mmax=80。

圖4 不同算法重構(gòu)NMSE與SNR的關(guān)系Fig. 4 Relationship of reconstruction NMSE and SNR for different algorithms

由圖4可知，R-ASP、O-ASP可改善SP重構(gòu)NMSE達(dá)10 dB以上，并且隨著信噪比增大，改善效果越明顯，這驗證了自適應(yīng)觀測對恢復(fù)性能的增益；O-ASP具有比R-ASP更低重構(gòu)NMSE，表明觀測矩陣優(yōu)化對恢復(fù)性能的增益；并且，O-ASP的重構(gòu)NMSE比BCS低至少5 dB(當(dāng)SNR≥15 dB)，這是因為O-ASP每次觀測都將能量集中在K個位置，而BCS的能量分配位置一般多于K個，故而O-ASP對觀測信噪比的增益更高，使它們的抗噪性能優(yōu)于BCS。

4 結(jié)語

本文結(jié)合自適應(yīng)觀測和觀測矩陣優(yōu)化的思想，提出一種自適應(yīng)觀測機(jī)制，在實現(xiàn)自適應(yīng)觀測的同時，也使觀測矩陣得到優(yōu)化。O-ASP的良好性能建立在估計支撐集的正確度上，如果估計支撐集不夠準(zhǔn)確(如觀測數(shù)過少、信噪比過低等)，則使O-ASP恢復(fù)性能不及BCS；如果估計支撐集足夠準(zhǔn)確，則僅需要少量觀測步驟就可恢復(fù)信號，并且恢復(fù)效果優(yōu)于BCS。O-ASP綜合利用了自適應(yīng)觀測和觀測矩陣優(yōu)化的優(yōu)勢，重構(gòu)效果始終優(yōu)于未采用自適應(yīng)觀測的SP和未采用觀測矩陣優(yōu)化的R-ASP。本文所提自適應(yīng)觀測機(jī)制因為每一步都需要傳統(tǒng)CS恢復(fù)算法獲得估計支撐集，需要更多的重構(gòu)時間。此外，恢復(fù)信號要求預(yù)先設(shè)置觀測總數(shù)，這不利于自適應(yīng)觀測。下一步工作將考慮如何以更低的復(fù)雜度獲取較為準(zhǔn)確的估計支撐集，以及如何自適應(yīng)確定恢復(fù)信號所需的觀測總數(shù)或確定停止觀測條件。

References)

[1] DONOHO D L. Compressed sensing [J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306.

[4] JI S H, XUE Y, CARIN L. Bayesian compressive sensing [J]. IEEE Transactions on Signal Processing, 2008, 56(6): 2346-2356.

[5] CASTRO R M, HAUPT J, NOWAK R, et al. Finding needles in noisy haystacks [C]// Proceedings of the 2008 IEEE International Conference on Acoustics, Speech and Signal Processing. Piscataway, NJ: IEEE, 2008: 5133-5136.

[6] BRAUN G, POKUTTA S, XIE Y. Info-greedy sequential adaptive compressed sensing [J]. IEEE Journal of Selected Topics in Signal Processing, 2015, 9(4): 601-611.

[7] FU C J, JI X Y, DAI Q H. Adaptive compressed sensing recovery utilizing the property of signal’s autocorrelations [J]. IEEE Transactions on Image Processing, 2012, 21(5): 2369-2378.

[8] DAVENPORT M A, MASSIMINO A K, NEEDELL D, et al. Constrained adaptive sensing [J]. IEEE Transactions on Signal Processing, 2016, 64(20): 5437-5449.

[9] CHEN Q, WU X J, LIU J H. Adaptive compressed sensing based randomized step frequency radar with a weighted PSO [C]// Proceedings of the 2015 IEEE International Conference on Information and Automation. Piscataway,NJ: IEEE, 2015: 1751-1756.

[10] WANG A S, LIN F, JIN Z P, et al. Ultra-low power dynamic knob in adaptive compressed sensing towards biosignal dynamics [J]. IEEE Transactions on Biomedical Circuits and Systems, 2016, 10(3): 579-592.

[11] 吳光文,張愛軍,王昌明.一種用于壓縮感知理論的投影矩陣優(yōu)化 算法 [J]. 電子與信息學(xué)報,2015,37(7):1681-1687.(WU G W, ZHANG A J, WANG C M. Novel optimization method for projection matrix in compress sensing theory [J]. Journal of Electronics & Information Technology, 2015, 37(7): 1681-1687.)

[12] 王韋剛,楊震,顧彬,等.基于觀測矩陣優(yōu)化的自適應(yīng)壓縮頻譜感知[J].通信學(xué)報,2014,35(8):33-39.(WANG W G, YANG Z, GU B, et al. Adaptive compressed spectrum sensing based on optimized measurement matrix [J]. Journal on Communications, 2014, 35(8): 33-39.)

[13] 王志文,徐以濤,黃鑫權(quán),等.基于觀測矩陣優(yōu)化的自適應(yīng)壓縮寬帶頻譜感知[J].通信技術(shù),2016,49(1):62-67.(WANG Z W, XU Y T, HUANG X Q, et al. Adaptive compressive wideband spectrum sensing based on measurement matrix optimization [J]. Communications Technology, 2016, 49(1): 62-67.)

[14] TROPP J A, GILBERT A C. Signal recovery from random measurement via orthogonal matching pursuit [J]. IEEE Transactions on Signal Processing, 2007, 53(12): 4655-4666.

[15] DAI W, MILENKOVIC O. Subspace pursuit for compressive sensing signal reconstruction [J]. IEEE Transactions on Information Theory, 2009, 55(5): 2230-2249.

HUQiang, born in 1993, M. S. candidate. His research interests include compressed sensing.

LINYun, born in 1968, Ph. D., associate professor. His research interests include compressed sensing, sparse signal processing.

Adaptivecompressedsensingalgorithmbasedonobservationmatrixoptimization

HU Qiang1*, LIN Yun2

(1.CollegeofCommunicationandInformationEngineering,ChongqingUniversityofPostsandTelecommunications,Chongqing400065,China; 2.ChongqingKeyLaboratoryofMobileCommunicationTechnology(ChongqingUniversityofPostsandTelecommunications),Chongqing400065,China)

In order to improve the anti-noise performance of the traditional Compressed Sensing (CS) recovery algorithm, a kind of Adaptive Compressed Sensing (ACS) algorithm was proposed based on the idea of observation matrix optimization and adaptive observation. The observed energy was all allocated in the support position estimated by the traditional CS recovery algorithm, which could effectively improve the observed Signal-to-Noise Ratio (SNR) owing to the support positions contained in the estimated support set. Then, the optimal new observation vector was derived from the perspective of observation matrix optimization, that is, its nonzero part was designed as the eigenvector of Gram matrix. The simulation results show that, the energy growth rate of non-diagonal elements of Gram matrix is less than that of the traditional CS algorithm with the increase of the number of observations. And the reconstruction normalized mean square error of the proposed algorithm is respectively lower than that of the traditional CS algorithm and the typical Bayesian method above 10 dB and 5 dB under the same conditions of number of observations, sparsity and SNR. The analysis shows that the proposed adaptive observation mechanism can effectively improve the energy efficiency and anti-noise performance of the traditional CS recovery algorithm.

adaptive compressed sensing; observation matrix optimization; observed Signal-to-Noise Ratio (SNR); feature decomposition; Gram matrix

2017- 06- 12;

2017- 08- 15。

胡強(qiáng) (1993—)，男，四川南充人，碩士研究生，主要研究方向：壓縮感知； 林云 (1968—)，男，四川南充人，副教授，博士，主要研究方向：壓縮感知、稀疏信號處理。

1001- 9081(2017)12- 3381- 05

10.11772/j.issn.1001- 9081.2017.12.3381

(*通信作者電子郵箱huqiang0424@qq.com)

TN911.7

A