基于壓縮感知的信號重構(gòu)算法研究

基于壓縮感知的信號重構(gòu)算法研究

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