劉俊梅, 馬永剛
(榆林學(xué)院數(shù)學(xué)與統(tǒng)計學(xué)院,陜西榆林 719000)
2006 年,Donoho,Candès和Tao等提出壓縮感知(Compressed Sensing,CS)[1-3]理論,該理論是一種充分利用信號的稀疏性和可壓縮性對信號進(jìn)行獲取和重構(gòu)的全新理論,一經(jīng)提出就引起國內(nèi)外相關(guān)研究人員的高度關(guān)注和重視,并迅速成為研究熱點. 隨著理論研究的深入,壓縮感知在實際應(yīng)用中也面臨著許多有待解決的問題,如大尺寸圖像信號壓縮采樣以及重構(gòu)圖像信號的應(yīng)用研究一直存在待改善的問題. 壓縮感知理論基于信號的稀疏性、觀測矩陣的隨機(jī)性以及非線性優(yōu)化算法對信號進(jìn)行采樣和重構(gòu),然而在實際應(yīng)用中,隨機(jī)觀測矩陣(如Gaussian,Bernoulli 等矩陣)要占用大量的存儲空間和內(nèi)存空間,存在實際應(yīng)用困難等問題.特別是在信號優(yōu)化重構(gòu)過程中,當(dāng)圖像尺寸增大時,所需觀測矩陣的存儲空間也隨之增大,造成重構(gòu)算法內(nèi)存消耗量成倍增加,這樣很大程度上限制了壓縮感知理論的實際應(yīng)用.
因此,研究如何降低壓縮感知過程中的觀測矩陣、稀疏化矩陣的存儲空間,并通過采用高效的信號重構(gòu)算法,進(jìn)一步提升壓縮感知理論的應(yīng)用仍然具有重要的理論價值和現(xiàn)實意義.
迄今為止,國內(nèi)外不少學(xué)者提出相應(yīng)的方法來解決壓縮感知過程中觀測矩陣占用內(nèi)存多,消耗量大,重構(gòu)算法計算復(fù)雜度高,不能適用于大規(guī)模實際應(yīng)用等問題.
在文獻(xiàn)[4-5]的基礎(chǔ)上,本文將半張量積壓縮感知模型采用正交匹配追蹤算法進(jìn)行信號重構(gòu),利用1 維可稀疏化信號對本文算法的重構(gòu)性能進(jìn)行驗證和比較. 實驗結(jié)果表明,采用本文所述擬合重構(gòu)方法同樣實現(xiàn)了對稀疏信號的重構(gòu).
2)結(jié)合律
壓縮感知模型簡單描述如下:設(shè)向量組ψ=[φ1,φ2,…,φN]為空間RN中的一組正交向量基,信號x ∈RN在正交矩陣下ψ 能夠表示為
式中:正交矩陣ψ 滿足ψψT=ψTψ=I,α 為信號向量x 的系數(shù)向量,且αi=<x,φi>=φiTx.
若向量α 中非零項的個數(shù)K ?M,則稱信號x 或系數(shù)向量α 是稀疏的(K-稀疏的),式(6)為信號x 的稀疏化表示,壓縮感知理論成立的大前提是待壓縮信號本身是稀疏的或者可在某個空間域稀疏表示.
利用矩陣ΦM×N(與稀疏化矩陣ψ 不相干,其中M ?N)作為壓縮感知模型的觀測矩陣,對信號x 進(jìn)行壓縮,該壓縮感知模型可簡單表示為
y 為壓縮后的數(shù)據(jù),稱為觀測向量. 通過這些少量的數(shù)據(jù)信號、系數(shù)向量α 的稀疏等約束條件,利用一些優(yōu)化算法可以重構(gòu)信號x .
從壓縮感知模型中可知,觀測矩陣參與了信號壓縮觀測、信號恢復(fù)這兩個數(shù)據(jù)處理的重要環(huán)節(jié),因此設(shè)計一個好的觀測矩陣是壓縮感知的核心問題,也很有研究的必要.
為了降低觀測矩陣在信號壓縮、重構(gòu)過程中的存儲空間,本文采用半張量積理論重新構(gòu)造觀測矩陣[8-10],即半張量積壓縮感知模型定義如下:
其中:Φ(M/t)×(N/t)是經(jīng)過降維以后的隨機(jī)觀測矩陣,其中M/t,N/t,t 為正整數(shù),且t <M,從以上模型可知,在相同數(shù)據(jù)的情況下,采用(8)式觀測矩陣的存儲空間是式(7)觀測矩陣存儲空間的1 t2倍.
利用半張量積的性質(zhì)結(jié)合律,我們可以驗證,式(8)是滿足式(7)所示模型的,同樣利用M 個觀測值可以對N 維信號進(jìn)行表示,即
至此,本文所述問題的關(guān)鍵技術(shù)在于,如何采用式(8)所示的模型對N 維信號x 進(jìn)行恢復(fù)或重構(gòu). 當(dāng)t=1 時,觀測矩陣維數(shù)為M×N,(8)式可表示成(7)式,由此可知,本文提到的基于半張量積的修正壓縮感知模型是適用于式(7)所示的壓縮感知模型的,為此,借鑒正交匹配追蹤算法來討論上述基于半張量積的修正壓縮感知模型的重構(gòu)方法.
正交匹配追蹤算法(OMP)[11-14]的基本思想:從字典矩陣A,注意這里字典原子是相互正交的向量,選擇一個與信號y 最匹配的原子,構(gòu)建一個稀疏逼近信號,并求出信號殘差,然后繼續(xù)選擇與信號殘差最匹配的原子,反復(fù)迭代,信號y 可以由最后的殘差值與這些原子的線性組合之和表示. 很顯然,如果殘差值在允許的范圍內(nèi)可以忽略,則信號y 可表示為這些原子的線性組合,這里殘差與已經(jīng)選擇過的原子正交的. 這就要求一個原子不會被選擇兩次,結(jié)果會在有限步達(dá)到收斂.
正交匹配追蹤重構(gòu)算法的流程如下.
輸入:觀測矩陣y,傳感矩陣A=Φ(M/t)×(N/t)?ψN×N,信號稀疏度k;
輸出:信號稀疏系數(shù)向量s,殘差rt=y-A ?st.
為驗證本文算法迭代收斂速度、恢復(fù)稀疏解的能力,設(shè)計了兩組實驗進(jìn)行驗證算法的性能,第一組選擇時域一維稀疏信號進(jìn)行重構(gòu),并從不同稀疏度情況下時域一維稀疏信號的恢復(fù)誤差、重構(gòu)效果、重構(gòu)時間等角度進(jìn)行比較. 第二組選擇變換域一維稀疏信號進(jìn)行重構(gòu),同樣從恢復(fù)誤差、重構(gòu)效果、重構(gòu)時間等角度進(jìn)行比較. 實驗平臺配置Intel(R)Core(TM)i7-8550U CPU,1.99 GHz主頻,8 GB內(nèi)存,64位Windows10操作系統(tǒng),仿真采用軟件Matlab 2014a.
設(shè)一維稀疏x 的稀疏度為k,且非零元素的位置隨機(jī),這里設(shè)置k 的最大值為M 2,因為文獻(xiàn)[15]指出一個稀疏信號能夠唯一恢復(fù)的前提是稀疏度最多不超過極限值M 2 .
為驗證本文算法的重構(gòu)性能,這里設(shè)定M=100,N=256,K=25,t=2,迭代次數(shù)設(shè)置為25 次,觀測矩陣Φ(M/t)×(N/t)為滿足N( 0,1/(M/t) )高斯獨立分布的( M/t )×( N/t )維高斯隨機(jī)矩陣,由于信號x 是稀疏的,所以稀疏化矩陣ψ 取為N×N 維單位矩陣,圖1給出稀疏信號x 的原始信號、重構(gòu)信號比較圖. 實驗結(jié)果顯示,信號重構(gòu)相對誤差0.004,重構(gòu)時間9.203,重構(gòu)效果良好,值得推廣應(yīng)用.
圖1 時域稀疏信號的壓縮感知重構(gòu)過程Fig.1 CS reconstruction of time-domain sparse signals
這里取M=100,N=256,t=2,迭代次數(shù)設(shè)置為25 次,觀測矩陣Φ(M/t)×(N/t)為滿足N( 0,1/(M/t))高斯獨立分布的( M/t )×( N/t )維高斯隨機(jī)矩陣,由于信號x 是變換域稀疏的,這里在壓縮感知過程中選取的變換域ψ 為離散傅里葉變換域,x 在ψ下的稀疏度為4,圖2給出變換域稀疏信號x 的原始信號、重構(gòu)信號比較圖. 實驗結(jié)果顯示,信號重構(gòu)相對誤差0.005,重構(gòu)時間10.445,重構(gòu)效果良好,值得推廣應(yīng)用.
圖2 變換域稀疏信號的壓縮感知重構(gòu)過程Fig.2 CS reconstruction of transformation domain sparse signals
本文利用半張量積理論知識,修正壓縮感知模型,給出一種基于半張量積的修正壓縮感知模型正交匹配追蹤算法,通過一維稀疏信號的重構(gòu)實驗,表明該算法的重構(gòu)效果良好,而且利用半張量積理論知識,減少了觀測矩陣的存儲空間,提高了重構(gòu)效率,今后的研究中,考慮將該重構(gòu)算法應(yīng)用到二維稀疏信號的重構(gòu).