壓縮感知聯(lián)合多屬性關(guān)聯(lián)的數(shù)據(jù)恢復(fù)算法

,,

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院,海口 570228)

0 概述

在無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network,WSN)中,參數(shù)信號大都具有非穩(wěn)定性、不確定性以及大時滯等特性,導(dǎo)致傳統(tǒng)的修復(fù)方法如多項式遞推法、差分法、卡爾曼濾波法以及最小二乘法在數(shù)據(jù)恢復(fù)效果上并不理想。目前,壓縮感知理論[1]已經(jīng)逐漸被人們使用在信號恢復(fù)重建工作上,壓縮感知理論是一種別于傳統(tǒng)信號壓縮理論的一種新理論,它利用信號的稀疏特性,通過非線性重建的算法來重建信號,并且它能使壓縮過程與采樣過程同時進行,而在壓縮比較大時也能夠獲得較為理想的恢復(fù)效果。

信號如何進行稀疏表示,測量矩陣如何構(gòu)造以及重構(gòu)算法如何設(shè)計是壓縮感知理論的3個核心內(nèi)容。信號具有可壓縮性能是壓縮感知理論中的必須要求,而信號的稀疏表示則是該要求的具體體現(xiàn)。想要獲得較好的可壓縮性,需要依賴稀疏字典的設(shè)計,而為了得到與原始信號相匹配的優(yōu)化字典,需用應(yīng)用一定的學(xué)習(xí)算法來彌補先驗知識的不足。壓縮采樣后獲取的信息量受到測量矩陣構(gòu)造的影響,測量矩陣的有限等距特性[2](Restricted Isometry Property,RIP)是測量矩陣構(gòu)造的必要條件,在此條件的基礎(chǔ)上專家學(xué)者提出了更廣泛的構(gòu)造原則,在不同的編碼方式與構(gòu)造方式的情況下,都能夠幾乎精確地重構(gòu)原始信號,并且重構(gòu)的信號具有唯一性。

原始信號經(jīng)過壓縮采樣,依舊能夠保留其重構(gòu)所必要的信息,但光憑這些信息是遠遠不夠的。信號重構(gòu)問題一直以來就是個NP難的問題,為了讓信號重建成為可能,利用了在重構(gòu)過程中,信號的稀疏性以及信號具有有限個的非零系數(shù)這2個特性。隨著壓縮感知理論的推廣普及以及深入研究,目前出現(xiàn)了各種優(yōu)化的重構(gòu)算法,主要為凸優(yōu)化算法和貪婪算法等,凸優(yōu)化算法包括基追蹤算法(Basis Pursuit,BP)[3]、梯度投影算法[4]、內(nèi)點迭代法[5]等,該類算法在重構(gòu)精度上較有優(yōu)勢但其運算時間過長。較為常見的貪婪算法有正交匹配追蹤(Orthogonal Matching Pursuit,OMP)[6]、分段正交匹配追蹤(Stagewise Orthogonal Matching Pursuit,StOMP)[7]、正則化正交匹配追蹤 (Regularized Orthogonal Matching Pursuit,ROMP)[8]、壓縮采樣匹配追 (CompressiveSampling Matching Pursuit,CoSaMP)[9]、子空間追蹤(Subspace Pursuit,SP)[10]和稀疏度自適應(yīng)匹配追蹤 (Sparsity Adaptive Matching Pursuit,SAMP)[11]等,該類算法在運算速度上有較好的優(yōu)勢,但其運算的精度有限。由于信號重構(gòu)是用于無線傳感器網(wǎng)絡(luò)這種實際應(yīng)用中,數(shù)據(jù)需要具有實時性,因此數(shù)據(jù)的恢復(fù)重構(gòu)在運算速度方面較為重要,而如何在確保運算速度的情況下提升數(shù)據(jù)恢復(fù)的精度是本文研究的主要內(nèi)容。

在上述貪婪算法中,除了SAMP算法以外,其余算法需要預(yù)先假設(shè)信號是稀疏的并規(guī)定稀疏度。然而,在實際的信號恢復(fù)重構(gòu)問題中,稀疏度往往很難獲得。因此,本文提出一種改進SAMP算法,并借助多屬性間存在的相關(guān)性來協(xié)助數(shù)據(jù)恢復(fù)。

1 壓縮感知理論及其重構(gòu)算法

1.1 壓縮感知理論

(1)

其中,θ被稱作投影系數(shù)向量,θ=ΨTX。如果θ的l0范數(shù)遠遠小于N,即非零項有限且很少,那么可以稱信號向量X在矩陣Ψθ上是稀疏的,即信號向量X是可壓縮的,信號向量X的稀疏度用K=‖θ‖l0來表示,其中‖·‖l0表示向量的l0范數(shù)。

在信號稀疏表示后,需要確定隨機測量矩陣ΦM×N,該隨機測量矩陣需要擁有RIP特性,并且跟信號的稀疏基不相關(guān)。確定隨機測量矩陣之后,便可對信號X進行壓縮采樣,其壓縮采樣過程表示為:

Y=ΦM×NX=ΦM×NΨθ

(2)

其中,M為隨機測量個數(shù),向量Y為測量信號向量。隨機測量個數(shù)M遠遠小于N,即信號的隨機測量過程實則是對信號的壓縮過程。信號進行隨機測量后,把得到的結(jié)果用l0范數(shù)優(yōu)化,重新把原始信號向量X進行重構(gòu):

min‖θ‖l0s.t.Y=ΦM×NΨθ

(3)

然而根據(jù)統(tǒng)計理論和組合優(yōu)化理論得知,組合優(yōu)化是一個NP問題,當(dāng)N很大時,數(shù)值上無法有效實現(xiàn),且抗噪聲能力很差,因此,由一些研究者證明l0約束優(yōu)化問題可以轉(zhuǎn)為數(shù)值上容易處理l1約束的凸優(yōu)化問題:

min‖θ‖l1s.t.Y=ΦM×NΨθ

(4)

其中,‖·‖l1表示向量的l1范數(shù)。基于l1范數(shù)凸優(yōu)化算法的系數(shù)重構(gòu)模型一般采用:

min‖X‖l1s.t. ‖Y-ΦM×NX‖l2≤σ

(5)

其中,σ為殘差,‖·‖l2表示向量的l2范數(shù)。即對式(5)進行多次重復(fù)迭代,設(shè)定一個合理的殘差上限,當(dāng)?shù)蟮臍埐钚∮诘扔跉埐钌舷迺r,用最小二乘法便可求出x的廣義解。

1.2 SAMP算法

鑒于大部分算法都需要已知信號的稀疏度,而實際問題中稀疏度往往是未知的,SAMP算法便可很好地解決這種問題。該算法在稀疏度無法確定時,設(shè)定初始步長與初始稀疏度,在每次迭代后可以得出一個殘差值,把得出的殘差值進行對比,從而更新步長以及稀疏度,如此反復(fù)得出稀疏的一個最優(yōu)估計,實現(xiàn)信號的壓縮重構(gòu)。但是該算法仍然有一定的缺陷,如果設(shè)定稀疏度的初始值相對于實際值過于偏小,便會導(dǎo)致迭代次數(shù)增多,即會影響到運算時間,在實際應(yīng)用中會有比較大的影響。如果設(shè)定步長的初始值相對于實際值過于偏大,那么會導(dǎo)致可能無法獲得真實稀疏度的值,使結(jié)果存在一定的誤差,從而降低了重構(gòu)精度。因此,需要一種改進的算法來解決上述的問題。

2 基于壓縮感知和多屬性協(xié)助的改進算法

2.1 改進的SAMP算法

為了解決SAMP算法帶來的缺陷,將原稀疏信號向量X進行分塊得到多個子信號,把分出的子信號逐一重構(gòu)再合并得出整體的重構(gòu)信號。由于原始稀疏信號向量X稀疏度越低在運用同樣重構(gòu)算法的前提下重構(gòu)精度越高[12]。如式(6)所示,利用信號整體是稀疏的,因此,局部也是稀疏的特性,將信號向量X分為多個相同長度的子信號,每一個子信號作為一個統(tǒng)一體來進行運算。

(6)

由文獻[13]中的理論得,當(dāng)觀測矩陣ΦM×N滿足RIP性質(zhì)時,可得如下公式:

(7)

其中,F0表示迭代的索引集合的初始值。利用命題成立則其逆否命題也成立的性質(zhì),可得:

(8)

因此,在K0初始化后如果滿足式(8),則K0=K0+s,其中,s為步長,更新F0。重復(fù)式(8)直至條件不成立為止。將此算法命名為分段稀疏度自適應(yīng)匹配追蹤(Stagewise Sparsity Adaptive Matching Pursuit,SSAMP)算法。

2.2 多參數(shù)協(xié)助的改進算法

無線傳感器網(wǎng)絡(luò)獲得的參數(shù)屬性一般均為某一系統(tǒng)中的屬性,而系統(tǒng)中的屬性間往往存在一定的聯(lián)系,比如在自然環(huán)境下,室內(nèi)與室外的溫度與濕度間就具有一定的線性關(guān)系[14]。然而這些關(guān)系較為復(fù)雜,在絕多數(shù)情況是無法用一個簡單的函數(shù)式子去把它們表示出來。因此,本文使用聯(lián)合稀疏分解的方法把多種參數(shù)的信號融合并提出共同分量和特征分量2個部分的方法來表現(xiàn)無線傳感器網(wǎng)絡(luò)中不同屬性間的相關(guān)性。若共同分量比之總體所占比例越高,則這些屬性間的相關(guān)性也就越高。

通過研究信號群中信號內(nèi)部和信號之間的相關(guān)性以及借助分布式信源編碼的思想,文獻[15]針對不同領(lǐng)域與用途提出了3種聯(lián)合稀疏模型(Joint Sparsity Model,JSM),其中,JSM-1模型十分適合應(yīng)用于無線傳感器網(wǎng)絡(luò)。

假設(shè)在無線傳感器網(wǎng)絡(luò)中多種不同的傳感器組成一個傳感器群,每個傳感器群由一個傳感器節(jié)點來接收數(shù)據(jù)并發(fā)送到匯聚節(jié)點。則在這個過程中令傳感器節(jié)點一共有P個以及N個傳感器組成的傳感器群,即N個參數(shù)屬性。由于在監(jiān)測周期內(nèi)有Q個時間隙,每個時間隙內(nèi)為數(shù)據(jù)采集后各個節(jié)點采集到的信號向量的長度L,因此可以把采集到的數(shù)據(jù)用Q×P的矩陣的形式表示:

(9)

矩陣A的每一列矩陣Xi,i=1,2,…,P表示在該時間隙內(nèi),一個傳感器節(jié)點得到的信號向量,矩陣A的每一行矩陣Xj,j=1,2,…,Q表示在同一采樣時刻,所有傳感器節(jié)點得到的采樣信息。

在匯聚節(jié)點進行稀疏變換可得:

Xi=Ψθ,i=1,2,…,P

(10)

則正交基矩陣Ψ為Xi,i=1,2,…,P的稀疏基。反變換后,寫成矩陣的形式得:

(11)

其中,矩陣B為稀疏變換后系數(shù)稀疏構(gòu)成的矩陣,矩陣θi,i=1,2,…,P表示矩陣B的第i列,矩陣θj,j=1,2,…,Q表示矩陣B的第j行。

利用JSM-1模型進行聯(lián)合稀疏表示,則矩陣θi可以寫成另一種形式:

θi=Δc+Δi,i=1,2,…,P

(12)

為了使聯(lián)合稀疏表示后稀疏度達到最小值,因此問題轉(zhuǎn)化為求下式l0范數(shù)的最小化:

min(‖Δc‖l0+‖Δ1‖l0+…+‖ΔP‖l0)

(13)

設(shè)矩陣Δc(n),n=1,2,…,Q為共同分量的第n個元素,因此,如若求解稀疏度最小時對應(yīng)的共同分量,只需令矩陣Δc(n)等于矩陣B的第n行的P個元素中出現(xiàn)頻數(shù)最大的元素。

聯(lián)合稀疏后的信號群矩陣變成如下形式:

(14)

將式(14)向量化,按列堆棧成一個Q(P+1)×1的列向量得:

(15)

設(shè)‖Δc‖l0=Kc,‖Δi‖l0=Ki,i=1,2,…,P,由共同分量和特征分量的稀疏度,由式(3)可以確定矩陣Δc,Δ1,…,ΔP所需的觀測值個數(shù)Mc,M1,…,MP,其對應(yīng)的隨機測量矩陣為Φc,Φ1,…,ΦP,則測量值向量可以表示為:

Yc=ΦcΔc

Y1=Φ1Δ1

?

YP=ΦPΔP

(16)

(17)

將以上的算法命名為多屬性壓縮感知(Multipara-meter Compressed Sensing,MCS)算法。

3 算法的實現(xiàn)步驟

輸入

1)觀測矩陣Φ

2)傳感矩陣Z=ΦΨ

3)觀測向量X

4)初始步長s

輸出

矩陣分塊算法[9]如下:

For id_x=1:ceil(a/size);

For id_y=1:ceil(b/size);

XX= X((id_x-1)·size+1:id_x·size,(id_y-1)·

size+1:id_y·size);

X1=ww·sparse(XX)·wwT;x1=full(X1);

y=ΦX1;

For i=1:size;

信號重構(gòu)步驟如下:

4)令Ck=Ft-1∪Sk,Zt={Zj}(for allj∈Ck);

5)求向量X=Ztθt的最小二乘解:

8)如果殘差rtnew=0,那么停止迭代第3)步～第8)步進入第9)步;

(1)如果‖rtnew‖2≥‖rt-1‖2,更新步長I=I+s,返回第3)步繼續(xù)迭代;

(2)如果前面2個條件都不滿足,那么Ft=F,rt=rtnew,t=t+1,如果t≤P停止迭代進入第9)步,否則返回第3)步繼續(xù)迭代;

矩陣分塊算法如下:

X2(:,i)=x;

End

X3((id_x-1)·size+1:id_x·size,(id_y-1)·

size+1:idid_y·size)=wwT·sparse(X2)·ww

End

End

在上述的步驟中,a是x的行數(shù),b是x的列數(shù),size是分塊的大小,?是空集符號,∪是并集運算符號,〈·,·〉是2個向量求內(nèi)積,abs[·]是求模值,即絕對值,rt表示迭代殘差,t表示迭代的次數(shù),Ft表示t次迭代的列序號集合(元素個數(shù)為I,I等于整數(shù)倍步長s),Zj表示矩陣Z的第j列,Zt={Zj}(for allj∈Ck)表示通過列序號集合Ck選出的矩陣Z的列集合(設(shè)矩陣的列數(shù)為It),θt為It×1的列向量。

4 實驗仿真

實驗1SSAMP算法的信號重構(gòu)效果

本文實驗采用信號長度L=256的稀疏信號,觀測矩陣是壓縮維度為128的高斯隨機矩陣,非零系數(shù)的大小服從高斯分布。圖1是通過SSAMP算法重構(gòu)的信號與原始信號對比圖,其恢復(fù)殘差ans=1.285e-14,運行時間為0.070 570 s。由于信號為隨機生成,每次結(jié)果均不相同,但經(jīng)過多次實驗,其恢復(fù)殘差均滿足ans≤3e-14。

圖1 SSAMP算法重構(gòu)信號效果

實驗2MCS- SSAMP算法的信號重構(gòu)效果

首先實驗觀測稀疏度k對重構(gòu)精度的影響,規(guī)定對每一個觀測值重復(fù)測驗m=128次,得出稀疏度10≤k≤70時各個不同算法對于重構(gòu)精度的影響,如圖2所示。實驗證明,隨著稀疏度k的降低,各個算法的重構(gòu)精度會不斷提高,而MCS-SSAMP算法提高的速度明顯快于其他算法,并且當(dāng)稀疏度在k=52時,該算法就已經(jīng)可以達到重構(gòu)成功的水平,而其他算法達到重構(gòu)成功水平所需要的稀疏度區(qū)間均小于MCS-SSAMP算法。

圖2 稀疏度與信號重構(gòu)精度的關(guān)系

其次實驗觀測測量數(shù)m對重構(gòu)精度的影響,令稀疏度k=20,得出測量數(shù)50≤m≤100時,各個不同算法對于重構(gòu)精度的影響,如圖3所示。實驗證明,隨著測量數(shù)m的增加,各個算法的重構(gòu)精度會不斷提高,而MCS-SSAMP算法提高的速度明顯快于其他算法,并且當(dāng)測量數(shù)m=68時,該算法就已經(jīng)可以達到重構(gòu)成功的水平,而其他算法達到重構(gòu)成功水平所需要的測量數(shù)區(qū)間均小于MCS-SSAMP算法。

圖3 測量數(shù)與信號重構(gòu)精度的關(guān)系

5 結(jié)束語

本文研究水產(chǎn)養(yǎng)殖中數(shù)據(jù)的恢復(fù)問題,提出一種數(shù)據(jù)恢復(fù)算法。采用原始稀疏信號分塊重構(gòu),使用最佳的匯聚節(jié)點確定出共同分量,并進行聯(lián)合編碼,降低每輪迭代當(dāng)中要處理的信號稀疏度,從而用更少的測量值實現(xiàn)信號群的精確重構(gòu)。改進的算法在運算時間上,由于對信號的初始稀疏度做了初始估計,因此可以有效避免稀疏度的初始值相對于實際值過于偏小時,導(dǎo)致迭代次數(shù)增多的問題。實驗結(jié)果表明,該算法降低了運算的時間,使運算更加高效,測定精度更高。今后將著重于研究用何種算法選取效率比較高的次屬性,以進行協(xié)助數(shù)據(jù)恢復(fù)的工作。

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

[3] CHEN S S,DONOHO D L,SAUNDERS M A.Atomic decomposition by basis pursuit[J].SIAM Review,2006,43(1):129-159.

[4] APPLEBAUM L,HOWARD S D,SEARLE S,et al.Chirp sensing codes:deterministic compressed sensing measure-ments for fast recovery[J].Applied & Computational Harmonic Analysis,2009,26(2):283-290.

[5] ROMBERG J.Compressive sensing by random convolution[J].SIAM Journal on Imaging Sciences,2009,2(4):1098-1128.

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

[7] DONOHO D L,TSAIG Y,DRORI I,et al.Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2012,58(2):1094-1121.

[8] NEEDELL D,VERSHYNIN R.Signal recovery from incomplete and inaccurate measurements via ROMP[J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2):310-316.

[9] NEEDELL D,TROPP J A.CoSaMP:iterative signal recovery from incomplete and inaccurate samples[J].Applied & Computational Harmonic Analysis,2008,26(3):301-321.

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

[11] DO T T,LU G,NGUYEN N,et al.Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//Proceedings of Asilomar Conference on Signals,Systems,and Computers.Washington D.C.,USA:IEEE Press,2008:581-587.

[12] 閆 鵬,張志賢,王阿川.基于壓縮感知SAMP算法的改進[J].森林工程,2014,30(3):80-83.

[13] 楊 成,馮 巍,馮 輝,等.一種壓縮采樣中的稀疏度自適應(yīng)子空間追蹤算法[J].電子學(xué)報,2010,38(8):1914-1917.

[14] LAWRENCE M G.The relationship between relative humidity and the dewpoint temperature in moist air:a simple conversion and applications[J].Bulletin of the American Meteorological Society,2010,86(2):225-233.

[15] BARON D,DUARTE M F,WAKIN M B,et al.Distributed compressive sensing[C]//Proceedings of International Conference on Acoustics,Speech and Signal Processing.Washington D.C.,USA:IEEE Press,2009:2886-2889.