基于壓縮感知的信號重構算法研究

基于壓縮感知的信號重構算法研究

0壓縮感知理論近年來，信息技術領域蓬勃發(fā)展，各種傳感器采集數據的能力不斷提高。現實世界的模擬化和信號處理工具的數字化決定了信號采樣是從模擬信源獲取數字信息的必經之路,而傳統(tǒng)的奈奎斯特采樣定理要求信號的采樣率不得低于信號帶寬的2倍,這必然給信號處理的能力提出了更高的要求,也給相應的硬件設備帶來了極大的挑戰(zhàn)。于是尋找一種新的數據采集、處理方法成為一種必然。2004年,由Donoho與Candes等人提出了壓縮感知(CompressedSensing,CS)理論,該理論表明,只要信號是可壓縮的或在某個變換域是稀疏的,那么就可以用一個與變換基不相關的觀測矩陣將變換所得高維信號投影到一個低維空間上,然后通過求解一個優(yōu)化問題就可以從這些少量的投影中以高概率重構出原信號,可以證明這樣的投影包含了重構信號的足夠信息。該理論還指出了將模擬信號直接采樣壓縮為數字形式的有效途徑,具有直接信息采樣的特性,這對應用科學和工程的許多領域具有重要的影響和實踐意義。在壓縮感知理論中,信號重構是其關鍵技術之一。信號重構的算法已有多種,基追蹤算法是其中比較常用的一種。經典的基追蹤算法針對含高斯白噪聲的信號進行去噪,從而達到信號重構的目的,它對高斯白噪聲有較好的去噪效果。但是高斯白噪聲并不是自然界中唯一種類的噪聲,在許多實際應用中所遇到的諸如水聲、低頻大氣噪聲以及許多人為噪聲等,往往具有一定的甚至比較顯著的脈沖特性,經典基追蹤模型就不足以適應上述的脈沖噪聲,因此對經典基追蹤模型進行改進,使其能夠適應脈沖噪聲的情況,擴展了基追蹤模型的應用范圍。仿真實驗驗證了改進基追蹤算法能夠較好的恢復含脈沖噪聲的信號。1基于基追蹤的高斯噪聲去噪在壓縮感知理論中,由于觀測數量遠小于信號長度,因此信號重構時不得不面對求解欠定方程組的問題。表面上看,求解欠定方程組似乎是無望的。但是,由于信號是稀疏的或可壓縮的,這個前提從根本上改變了問題,使得問題可解,而觀測矩陣具有有限等距性質(RestrictedIsometryProperty,RIP)也為從觀測值中精確恢復信號提供了理論保證?；謴秃胄盘柕淖罨疽罁切盘栐谀硞€變換空間的分解系數是稀疏的,而噪聲的存在則破壞了信號在空間中的稀疏性。經典的基追蹤算法就是基于以上原理從而達到重構和對高斯白噪聲去噪的目的?；粉櫵惴ǖ闹饕繕耸菍ふ仪范ǚ匠碳词?1)的解。Y=AX,A∈Rm×n,Y∈Rm,m?n(1)求解的最直接方法是通過0-范數下,求解式(2)的最優(yōu)化問題。min‖X‖0,s.t.AX=Y(2)由于式(2)的求解是個NP-hard問題,方程的解很難求得,所以根據1-范數下在一定條件下和0-最小范數具有等價性,利用式(3)的約束條件,可以得出求解一個更加簡單的線性規(guī)劃問題會產生同等的解。min‖X‖1,s.t.AX=Y(3)但是,這種模型在含有噪聲的情況下,不能夠準確的恢復信號。在含噪觀測的情況下,考慮如下觀測模型:Y=s+n=AX+n(4)式中:s為原信號(s=AX),Y為已知的觀測信號,假定n為高斯白噪聲,且‖n‖2<σ,重構算法就是在式(4)中求解原信號X。對式(3)作進一步的改進,沿用BP方法對噪聲的抑制方法,即BPDN方法,修改其約束條件定義最優(yōu)化問題,如式(5)所示。min‖X‖1,s.t.‖AX-Y‖2≤σ(5)對最優(yōu)化問題進一步求解,就可以重構出原信號。BPDN算法致力于最小化信號重建誤差,同時使得信號的表示最稀疏。而參數σ控制著允許誤差與稀疏性之間的平衡。式中σ≥0,是對噪聲在信號中強度的定義。若σ=0,則BPDN算法等同于BP算法。2算法的復雜度分析經典的基追蹤算法盡管可行,但是它存在兩個問題:1)算法的計算復雜度很高,在采樣點個數滿足M≥cK,c≈log2(N/K+1)時,重構計算復雜度的量級在O(N3)。2)算法只對高斯白噪聲重構去噪效果較明顯,而現實世界中的噪聲是多種多樣的,對常見的脈沖噪聲去噪效果并不明顯。針對以上的問題,提出了改進的基追蹤去噪算法。2.1基于拉格朗日乘數法的噪聲約束條件改進經典的基追蹤算法對信號的稀疏性是建立在1-范數的意義下,而對于噪聲的抑制采用了2-范數的約束形式。由于2-范數不能體現信號的稀疏性,對稀疏噪聲的抑制并不理想,恢復得到的信號的稀疏度無法精確達到真正的無噪信號的稀疏度。即經典基追蹤算法對于含脈沖噪聲的信號恢復效果較差,不能滿足信號處理的要求。所以,對經典的基追蹤算法進行改進,使其能夠適應重構含脈沖噪聲的信號。修改其對噪聲的約束條件,改變其不適應稀疏噪聲分布的2-范數約束形式?？紤]p-范數(p>2)約束的條件,由于p-范數的優(yōu)化是一個非凸函數的優(yōu)化問題,其中有很多數學問題有待解決,而1-范數意義下的優(yōu)化問題是一個凸函數優(yōu)化問題,且1-范數約束的噪聲對應的先驗分布應為拉普拉斯分布,它是一種典型的稀疏分布,適合抑制信號的稀疏噪聲。所以本文將基追蹤算法的噪聲約束條件將式(5)由2-范數改為1-范數,如式(6)所示。min‖X‖1,s.t.‖AX-Y‖1≤σ(6)根據拉格朗日乘數法,式(6)可等價為求解以下優(yōu)化問題。minXλ∥X∥1+12∥Y?AX∥1(7)minXλ∥X∥1+12∥Y-AX∥1(7)式(7)即為改進算法的模型。由于1-范數能夠比較好的體現信號的稀疏性,對稀疏噪聲的抑制較2-范數理想。所以對脈沖噪聲采用1-范數抑制可以得到比準確的結果。2.2改進基追蹤模型的實驗結果根據CS信息算子A在很大概率上具有有限等距性質,可得重構信號X?X^與原信號X的誤差在2-范數情況下如式(8)所示?！蝀??X∥2≤∥X^-X∥2≤C2RS1/2-1/p(8)式中:C2為正常數,R是范數變化的半徑,S是稀疏度,p控制上式的收斂,p越小收斂速度越快。而1-范數的情況下為:∥X??X∥1≤∥X^-X∥1≤C1RS1-1/p(9)對S-項稀疏的K×N維矩陣A有S≤C·K/log(N/K)從而得出∥X??X∥1≤∥X^-X∥1≤CR[K/log(N/K)]-r,r=1/p-1(10)由式(10)可知在以1-范數抑制噪聲的條件下,誤差仍然可控制在一定范圍內,說明了改進模型的可行性。而對于式(4)假設pn(n)∝exp(?∥n∥12σ2n)pn(n)∝exp(-∥n∥12σn2),故pY/X(Y/X)∝exp(?∥Y?AX∥12σ2n)pY/X(Y/X)∝exp(-∥Y-AX∥12σn2)假定表示系數X的先驗分布滿足拉普拉斯分布,pX(X)∝e-c‖X‖1,在給定先驗分布的情況下,式(4)的極大后驗解為:Xmap=argmaxXlnpX/Y(X/Y)=argminX[?lnpY/X(Y/X)?lnpX(X)]=argminX12∥Y?AX∥1+λ∥X∥1(11)Xmap=argmaxXlnpX/Y(X/Y)=argminX[-lnpY/X(Y/X)-lnpX(X)]=argminX12∥Y-AX∥1+λ∥X∥1(11)式中:取λ=σ2nn2/c?？梢?由極大后驗準則得到的目標函數與改進基追蹤模型中的目標函數是一致的。由以上分析還可以看出:在改進基追蹤模型中,目標函數中的擬合誤差項‖Y-AX‖1是與噪聲的先驗分布對應的;而正則項‖X‖1是與X的先驗分布對應的。2.3線性規(guī)劃的求解因為梯度投影算法易于在MATLAB上實現仿真,根據文獻對經典基追蹤算法求解的梯度投影法,針對含噪觀測情況下的改進基追蹤模型式(7),可以令X=a-b,其中a≥0,b≥0,且式中ai=(Xi)+,bi=(-Xi)+,i=1,2,…,n,n為向量的維數,在這里(·)+是對實部算子的定義,即(x)+=max{0,x},則‖X‖1=lTa+lTb記,則‖X‖1=lTu,其中向量l=[1,1,…,1],它的維數與向量u相同為n;同理,可以令Y-AX=c-d,其中c,d≥0,且式中ci=(Y-AXi)+,di=(-Y+AXi)+,i=1,2,…,m。記,則‖Y-AX‖1=lTv,此時向量l=[1,1,…,1],它的維數與向量v相同為m。因此推出下式:Y-AX=c-dc-d+A(a-b)=Y(I,-I,A,-A)(c,d,a,b)T=Y(12)式中:I為單位陣,進一步定義為正則化參數這里取經驗值λ=σ2logp????√?pλ=σ2logp?p為字典的勢。則模型式(7)問題和下述的線性規(guī)劃問題等價:mincTx,s.t.Dx=b,x≥0(13)式中:cTx是目標函數,Dx=b是等式約束集,x≥0是非負約束。這樣,問題的求解就可以轉化為上述線性規(guī)劃的算法求解。而對式(13)的求解見文獻。3經典基追蹤算法的實驗結果為了驗證改進重構算法的去噪效果,將分別對經典的基追蹤算法和改進的基追蹤算法進行仿真實驗。首先,選用的信號如圖1所示。圖中分別為仿真實驗中用到的無噪信號、含高斯白噪聲的信號和含脈沖噪聲的信號。圖1(a)中的信號是稀疏的,而各種噪聲則破壞了信號的稀疏性如圖1(b)(c)所示,其中圖1(b)的信噪比SNR=15。下面首先對信號進行觀測,然后通過使用不同的信號重構算法,對算法做出比較。針對經典的基追蹤算法,設A為50×128維的稀疏矩陣,使用上述的信號源,對其在無噪條件下的信號進行重構結果如圖2(a)所示。在有高斯白噪聲和脈沖噪聲的條件下,取σ=0.1,分別對信號進行重構,可見其結果如圖2(b)(c)所示。而針對改進的基追蹤算法,在脈沖噪聲的條件下,對信號進行重構,得結果如圖2(c)所示。由圖2中可以看出,經典的基追蹤算法在無噪的情況下可以精確重構原信號,在高斯白噪聲干擾的情況下,也可以比較準確地恢復原信號。而在脈沖噪聲的情況下則出現了大量的失真,尤其是在40、55、100、120點附近經典算法的失真很大,基本上不能恢復出原信號,無法滿足信號處理的要求。這說明經典的基追蹤去噪算法不能夠較好恢復含脈沖噪聲的信號。由圖2(d)可見,在脈沖噪聲條件下,經過改進的算法在上述幾點處失真度明顯減小,能夠比較準確地恢復出原信號。改進算法在脈沖噪聲條件下,對含噪信號的重構性能大大好于經典的基追蹤算法,這也驗證了在1-范數約束下,對稀疏噪聲抑制的有效性。改進的算法在運算速度方面要快于經典算法,雖然算法復雜度的數量級未變,但仿真實驗中,在相同條件下,對含脈沖信號的噪聲進行重構,經典算法的運行時間為0.89s,而改進算法的運行時間為0.65s。所以改進算法