壓縮感知聯合多屬性關聯的數據恢復算法

,,

(海南大學 信息科學技術學院,海口 570228)

0 概述

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

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

原始信號經過壓縮采樣,依舊能夠保留其重構所必要的信息,但光憑這些信息是遠遠不夠的。信號重構問題一直以來就是個NP難的問題,為了讓信號重建成為可能,利用了在重構過程中,信號的稀疏性以及信號具有有限個的非零系數這2個特性。隨著壓縮感知理論的推廣普及以及深入研究,目前出現了各種優化的重構算法,主要為凸優化算法和貪婪算法等,凸優化算法包括基追蹤算法(Basis Pursuit,BP)[3]、梯度投影算法[4]、內點迭代法[5]等,該類算法在重構精度上較有優勢但其運算時間過長。較為常見的貪婪算法有正交匹配追蹤(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]和稀疏度自適應匹配追蹤 (Sparsity Adaptive Matching Pursuit,SAMP)[11]等,該類算法在運算速度上有較好的優勢,但其運算的精度有限。由于信號重構是用于無線傳感器網絡這種實際應用中,數據需要具有實時性,因此數據的恢復重構在運算速度方面較為重要,而如何在確保運算速度的情況下提升數據恢復的精度是本文研究的主要內容。

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

1 壓縮感知理論及其重構算法

1.1 壓縮感知理論

(1)

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

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

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

(2)

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

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

(3)

然而根據統計理論和組合優化理論得知,組合優化是一個NP問題,當N很大時,數值上無法有效實現,且抗噪聲能力很差,因此,由一些研究者證明l0約束優化問題可以轉為數值上容易處理l1約束的凸優化問題:

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

(4)

其中,‖·‖l1表示向量的l1范數。基于l1范數凸優化算法的系數重構模型一般采用:

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

(5)

其中,σ為殘差,‖·‖l2表示向量的l2范數。即對式(5)進行多次重復迭代,設定一個合理的殘差上限,當迭代后的殘差小于等于殘差上限時,用最小二乘法便可求出x的廣義解。

1.2 SAMP算法

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

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

2.1 改進的SAMP算法

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

(6)

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

(7)

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

(8)

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

2.2 多參數協助的改進算法

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

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

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

(9)

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

在匯聚節點進行稀疏變換可得:

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

(10)

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

(11)

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

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

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

(12)

為了使聯合稀疏表示后稀疏度達到最小值,因此問題轉化為求下式l0范數的最小化:

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

(13)

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

聯合稀疏后的信號群矩陣變成如下形式:

(14)

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

(15)

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

Yc=ΦcΔc

Y1=Φ1Δ1

?

YP=ΦPΔP

(16)

(17)

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

3 算法的實現步驟

輸入

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;

信號重構步驟如下:

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)步繼續迭代;

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

矩陣分塊算法如下:

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

4 實驗仿真

實驗1SSAMP算法的信號重構效果

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

圖1 SSAMP算法重構信號效果

實驗2MCS- SSAMP算法的信號重構效果

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

圖2 稀疏度與信號重構精度的關系

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

圖3 測量數與信號重構精度的關系

5 結束語

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

[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] 楊 成,馮 巍,馮 輝,等.一種壓縮采樣中的稀疏度自適應子空間追蹤算法[J].電子學報,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.