吳夢(mèng)行, 伍飛云, 楊坤德, 田天
(1.杭州應(yīng)用聲學(xué)研究所 聲納技術(shù)重點(diǎn)實(shí)驗(yàn)室,浙江 杭州 310023; 2.西北工業(yè)大學(xué) 航海學(xué)院,陜西 西安 710072)
壓縮感知(compressed sensing, CS)在過去的十幾年中,由于其在圖像和音頻處理[1]、視覺跟蹤[2-4]、以及計(jì)算機(jī)視覺和水聲信道估計(jì)[5-8]等多個(gè)領(lǐng)域的巨大潛在應(yīng)用價(jià)值,受到了越來越多的關(guān)注。
結(jié)合測(cè)量矩陣和壓縮的信號(hào)對(duì)原始信號(hào)進(jìn)行恢復(fù)是壓縮感知最重要的部分之一,其可以對(duì)采樣不足的信號(hào)進(jìn)行充分的重構(gòu),突破了傳統(tǒng)的香農(nóng)奈奎斯特采樣定理,實(shí)現(xiàn)了可接受的準(zhǔn)確性和復(fù)雜度。常用的重構(gòu)算法主要包括凸優(yōu)化算法和貪婪迭代算法[9]。其中,貪婪算法以其兼顧重構(gòu)質(zhì)量和運(yùn)行效率的優(yōu)勢(shì),受到越來越多的關(guān)注。匹配追蹤算法(matching pursuit)是最典型的貪婪算法之一,其特點(diǎn)是根據(jù)傳感矩陣與殘差值相關(guān)性的強(qiáng)弱,挑選最為匹配的原子擴(kuò)充支撐集,其重構(gòu)速度快且有較好的重構(gòu)質(zhì)量。其改進(jìn)算法還包括OMP (orthogonal MP)[10]、ROMP (regularized OMP)[11]、 StOMP (stagewise OMP)[12]等算法。然而,挑選的原子被選入支撐集后,將在整個(gè)迭代過程中保留,無法判斷和更新錯(cuò)選的原子,影響了支撐集的準(zhǔn)確性,且相關(guān)性判據(jù)有待改進(jìn)。為此,出現(xiàn)的CoSaMP算法 (compressive sampling MP)[13]和SP算法(subspace pursuit)[14]算法通過回溯步驟剔除相關(guān)性較低的原子,獲得更精確的支持集,但是重構(gòu)效果受到支撐集原子選擇方式缺乏靈活性的約束。為了滿足在未知稀疏度K的情況下獲得更好的跟蹤和重建性能,SAMP (sparsity adaptive MP)等算法對(duì)匹配跟蹤算法進(jìn)行了大量的改進(jìn)[15-18]。這類稀疏度自適應(yīng)算法的核心是利用一個(gè)固定步長(zhǎng)多次迭代不斷逼近,達(dá)到事先不需要知道稀疏度就能準(zhǔn)確估計(jì)真實(shí)的稀疏度K的目的。
在滿足稀疏性條件的前提下,MMP算法[19]從多個(gè)候選支撐集中選擇最優(yōu)方案,顯然多路徑搜索比單路徑搜索有更好的性能。但由于MMP計(jì)算量大,在沒有稀疏信息的情況下很難求解大規(guī)模問題。因此對(duì)MMP算法進(jìn)行優(yōu)化具有重要的意義。本文在MMP算法基礎(chǔ)上提出了一種改進(jìn)的快速稀疏度自適應(yīng)多路徑匹配追蹤算法(improved multipath matching pursuit algorithm with sparsity adaptive, IMMP)。與傳統(tǒng)算法相比,IMMP算法具有明顯的重構(gòu)精度和時(shí)間優(yōu)勢(shì)。
由CS理論可知,將一個(gè)K-稀疏或在某一稀疏域能稀疏表示的N維離散數(shù)字信號(hào)通過某一個(gè)測(cè)量矩陣進(jìn)行有效壓縮,我們就能夠在線性變換下通過得到少量的觀測(cè)值精確重構(gòu)原始信號(hào)[10]。信號(hào)x中除了只有K個(gè)非零值外其余N-K個(gè)值均為零,且K遠(yuǎn)小于N。采樣和壓縮過程可以描述為:
y=Φx
(1)
式中:Φ是大小為M×N的測(cè)量矩陣,觀測(cè)值y的長(zhǎng)度為M且滿足M?N。壓縮感知理論的目標(biāo)是基于觀測(cè)值y和測(cè)量矩陣Φ將重構(gòu)問題轉(zhuǎn)換為求具有稀疏約束的l0范數(shù)的最優(yōu)解問題。其求l0范數(shù)最優(yōu)解模型為:
(2)
式中 ‖x‖0為x的l0范數(shù)。如果在某一變換域中使信號(hào)x滿足稀疏條件,稱此變換域?yàn)閤的稀疏域,在此稀疏域中,信號(hào)可以稀疏表示為:
x=Ψθ
(3)
式中:Ψ=[ψ1ψ2…ψN]為稀疏基矩陣;θ為在稀疏基矩陣Ψ下的K稀疏信號(hào)矩陣。理論表明,求解最小l0范數(shù)是一個(gè)NP-hard問題[20],而且求解最小l0范數(shù)可以轉(zhuǎn)化為求解最小l1范數(shù)[11],即最小l1范數(shù)優(yōu)化問題:
(4)
MMP算法通過將搜索最優(yōu)路徑建模成基于樹的路徑搜索問題,每次迭代依據(jù)測(cè)量矩陣與殘差的相關(guān)性來更新一個(gè)支撐集原子,通過貪婪迭代搜索多個(gè)路徑,每個(gè)路徑經(jīng)K次迭代后得到一個(gè)含K個(gè)原子的支撐集,最終達(dá)到選擇最優(yōu)路徑即最優(yōu)支撐集的目的。在多路徑搜索中,當(dāng)前第k層分支節(jié)點(diǎn)原子通過計(jì)算第k-1層分支節(jié)點(diǎn)的殘差rk-1與測(cè)量矩陣Φ的內(nèi)積確定:
Γ=arg max|〈Φ,rk-1〉|
(5)
(6)
(7)
(8)
偽逆矩陣為:
(9)
在MMP算法中,分支原子選擇的優(yōu)先級(jí)由式(10)決定,其中Cl=[c1c2…cK],優(yōu)先級(jí)函數(shù)layer_Order是其算法實(shí)現(xiàn)過程:
(10)
式中:ck與當(dāng)前k層分支原子的選擇相關(guān);d表示當(dāng)前原子節(jié)點(diǎn)的子路徑數(shù)。Cl給予MMP搜索的第l條路徑每個(gè)節(jié)點(diǎn)原子被選擇的優(yōu)先級(jí),直至殘差值滿足一定停止迭代閾值ε1或達(dá)到最大搜索路徑數(shù)LMAX時(shí)停止搜索。
layer_Order函數(shù)的實(shí)現(xiàn)步驟如下:
1) 輸入當(dāng)前路徑次序當(dāng)前路徑次序l,子路徑d,稀疏度K,初始值j=1,p=l-1并計(jì)算余數(shù)cj=mod(p,d)。
2) 計(jì)算p除以d的商并賦值給p,如果j≤K,更新迭代j值:j=j+1,并轉(zhuǎn)步驟1);否則停止迭代,輸出當(dāng)前路徑節(jié)點(diǎn)搜索順序Cl=[c1c2…cK]。
MMP-DF算法步驟如下:
1) 輸入觀測(cè)向量y,測(cè)量矩陣Φ,稀疏度K,子路徑d,最大路徑迭代次數(shù)LMAX和停止迭代閾值ε,初始值l=0,rmin=y,Ω0=?,r0=y。
2) 如果l
4) 如果j MMP算法改進(jìn)了正交匹配追蹤算法支撐集非最優(yōu)的不足,將正交匹配追蹤算法每個(gè)原子僅分支出一個(gè)原子改為分支出多個(gè)原子,其多樣化的搜索路徑使搜索范圍更廣,避免陷入局部最優(yōu)解。理論上可以得到遠(yuǎn)多于OMP算法的支撐集,大大提高了重構(gòu)精度。但當(dāng)遇到大規(guī)模數(shù)據(jù)時(shí),MMP算法需要搜索大規(guī)模路徑,考慮實(shí)際應(yīng)用需要對(duì)搜索路徑進(jìn)行有效優(yōu)化降低計(jì)算復(fù)雜度。 在實(shí)際應(yīng)用中,重構(gòu)信號(hào)的稀疏度一般是未知的,借鑒SAMP算法稀疏度自適應(yīng)和SP算法回溯的思想,結(jié)合MMP算法的優(yōu)點(diǎn)和不足,本文提出了IMMP算法。該算法對(duì)內(nèi)積匹配準(zhǔn)則進(jìn)行改良,利用閾值法選擇支撐集,并采用變步長(zhǎng)思想來逼近信號(hào)稀疏度,并對(duì)MMP算法的搜索路徑進(jìn)行剪枝處理,在不影響重構(gòu)質(zhì)量的同時(shí)極大減少了運(yùn)算時(shí)間,使之更具實(shí)用價(jià)值。下面主要從以下幾個(gè)方面對(duì)IMMP算法進(jìn)行描述。 MMP等貪婪算法主要使用內(nèi)積匹配準(zhǔn)則度量測(cè)量矩陣與殘差值間的相關(guān)性強(qiáng)弱。傳統(tǒng)的內(nèi)積匹配準(zhǔn)則更多地是從方向上區(qū)分差異,而對(duì)絕對(duì)的數(shù)值不敏感,從而影響對(duì)相似原子的區(qū)分,使觀測(cè)矩陣中任意2個(gè)相近似的原子可能影響殘差信號(hào)的匹配過程。這種僅考慮向量維度方向上的相似性而沒考慮到各個(gè)維度量綱差異的不合理性會(huì)降低信號(hào)的重構(gòu)質(zhì)量。假設(shè)有任意向量a=(a1,a2,…,an)和向量b=(b1,b2,…,bn)。改良后的內(nèi)積匹配準(zhǔn)則公式為[21]: (11) (12) 從根節(jié)點(diǎn)迭代到第K個(gè)分支節(jié)點(diǎn),其中每個(gè)節(jié)點(diǎn)代表不同的字典原子,當(dāng)候選支撐集中選擇的原子數(shù)量等于稀疏度K時(shí),認(rèn)為此路徑搜索完成。根據(jù)原子選擇優(yōu)先級(jí)的不同,將會(huì)得到不同的候選支撐集。取當(dāng)前起始路徑l={1,2,…,LMAX},在后面每個(gè)路徑迭代過程中,一個(gè)最有希望的原子被添加到當(dāng)前路徑中。當(dāng)搜索路徑達(dá)到最大值LMAX或者完全確定最優(yōu)路徑時(shí)終止迭代。圖1給出了該算法的樹搜索過程,其中LMAX=3,d=3,K=3??梢钥吹接蒀1=(1,1,1)確定的原子構(gòu)成第1個(gè)支撐集,第2個(gè)支撐集則由C1=(2,1,1)確定的原子構(gòu)成,直到選擇最佳的候選支撐集為止。 在當(dāng)前支撐集迭代完成后,將與上一個(gè)支撐集執(zhí)行回溯步驟用來選擇最佳的K個(gè)原子。在第2個(gè)候選支撐集{4,1,2}完成后,執(zhí)行回溯細(xì)化沒有替換任何原子,第3個(gè)候選支撐集{6,3,4}回溯重新選擇原子后,支撐集更正為{6,2,4},提高了路徑搜索的精度?;厮蓦m然帶來了額外的計(jì)算負(fù)擔(dān),但優(yōu)化路徑大大降低了計(jì)算復(fù)雜度,提高了算法的重構(gòu)精度。 稀疏度自適應(yīng)算法設(shè)置的固定步長(zhǎng)無法兼顧重構(gòu)精度和重構(gòu)效率,初始步長(zhǎng)較小會(huì)降低算法重構(gòu)效率,步長(zhǎng)較大則會(huì)降低算法重構(gòu)精度。采用兼顧兩者的變步長(zhǎng)是一個(gè)不錯(cuò)的方法。根據(jù)稀疏度估計(jì)的特點(diǎn),改進(jìn)算法稀疏度估計(jì)可以分為2個(gè)部分:1)初始階段大步長(zhǎng)快速估計(jì),2)完成階段小步長(zhǎng)逐步逼近。 圖1 MMP和IMMP算法原理Fig.1 Schematic diagram of MMP and IMMP algorithms 文獻(xiàn)[22]研究表明,重構(gòu)信號(hào)的殘差能量在2個(gè)相鄰階段中是遞減的,且隨著支撐集長(zhǎng)度λ不斷逼近真實(shí)稀疏度K,殘差能量減小速度逐漸變緩趨于穩(wěn)定。所以本文以相鄰階段重構(gòu)信號(hào)的殘差能量作為步長(zhǎng)變換的條件。當(dāng)殘差能量小于等于‖rmin‖2時(shí),步長(zhǎng)切換更新稀疏度到下一階段,當(dāng)殘差能量小于ε2時(shí)稀疏度估計(jì)過程完成。ε2是迭代停止閾值,在這里取ε2=10-6。 利用ax指數(shù)函數(shù)的變化規(guī)律來調(diào)整步長(zhǎng),初始階段步長(zhǎng)取一個(gè)合適的初值s0,每次增加步長(zhǎng)s=s0ax,支撐集長(zhǎng)度λ=λ+s;其中a是固定常數(shù),文獻(xiàn)[23]證明當(dāng)a∈[0.3,0.5]時(shí)效果較好,x為當(dāng)前候選支撐集迭代次數(shù),「·?表示向上取整。當(dāng)支撐集長(zhǎng)度λ接近真實(shí)稀疏度K時(shí),添加進(jìn)支撐集的原子越來越少,直到支撐集長(zhǎng)度λ=λ+1。采用此變步長(zhǎng)方法可提高算法重構(gòu)質(zhì)量和計(jì)算效率。 根據(jù)上面對(duì)IMMP算法原理的描述,在下面分別詳細(xì)地給出了階段自適應(yīng)估計(jì)稀疏度Search函數(shù)和IMMP算法的實(shí)現(xiàn)步驟: Search函數(shù)的實(shí)現(xiàn)步驟如下: 1) 輸入搜索序列Cl,殘差值r0,稀疏度λ,inputj={rj,Ωj,j}。 2) 如果j<λ或λ>length(Ωj),更新參數(shù)j=j+1,否則轉(zhuǎn)到步驟4)。 MMP-DF算法步驟如下: 本節(jié)使用一維信號(hào)模擬實(shí)驗(yàn),以信號(hào)精確重構(gòu)比(exact reconstruction ratio, ERR)和重構(gòu)時(shí)間作為算法重構(gòu)性能的評(píng)價(jià)標(biāo)準(zhǔn),其中當(dāng)重構(gòu)信號(hào)的殘差小于閾值ε1時(shí),認(rèn)為信號(hào)重構(gòu)是成功的,本文取ε1=10-6。信號(hào)精確重構(gòu)率反映了重構(gòu)精度,其中ERR定義為準(zhǔn)確恢復(fù)次數(shù)pn與總實(shí)驗(yàn)次數(shù)psum的比值:ERR=pn/psum重構(gòu)時(shí)間和迭代殘差反映了重構(gòu)效率。仿真實(shí)驗(yàn)使用Matlab(版本R2018b)在一臺(tái)裝配了Core i5-6400 @2.70GHz 處理器的計(jì)算機(jī)上進(jìn)行。實(shí)驗(yàn)中設(shè)置MMP和IMMP算法的最大迭代次數(shù)和子路徑數(shù)(LMAX,d)分別為(50, 6)和(10, 6)。選擇高斯隨機(jī)矩陣作為觀測(cè)矩陣,為避免隨機(jī)因素的干擾,每個(gè)算法都獨(dú)立重復(fù)進(jìn)行了10 000次試驗(yàn)且稀疏信號(hào)的非零位置都是隨機(jī)選擇的。 以典型的單路徑搜索算法OMP作為MMP算法中的一條搜索路徑中為例,分別使用內(nèi)積準(zhǔn)則和改進(jìn)的內(nèi)積準(zhǔn)則來度量觀測(cè)矩陣原子和殘差信號(hào)的相關(guān)性,以便挑選最為匹配的原子。隨機(jī)生成稀疏度K=30,長(zhǎng)度N=256的一維信號(hào)作為測(cè)試信號(hào)。比較在加入高斯噪聲后(SNR=15 dB),2種匹配準(zhǔn)則下的殘差值隨不同迭代次數(shù)的變化情況,取對(duì)數(shù)表示的結(jié)果如圖2所示。 圖2 OMP不同迭代次數(shù)的殘差(K=30)Fig.2 Residual error of different iterations of OMP(K=30) 很明顯,隨著迭代次數(shù)增加,殘差值逐漸減小。同等條件下,可以從圖2看出改進(jìn)的內(nèi)積匹配準(zhǔn)則的殘差值比內(nèi)積準(zhǔn)則更低,迭代過程中殘差值逼近零的速度更快。這充分說明改進(jìn)的內(nèi)積匹配準(zhǔn)則不僅更有利于挑選最優(yōu)匹配原子,降低誤選原子的概率,而且能夠加速完成迭代逼近,提高重構(gòu)效率。 表1是當(dāng)壓縮比M/N=[0.234 4,0.312 5,0.396 0]時(shí),OMP算法應(yīng)用2種不同原子匹配準(zhǔn)則在不同高斯白噪聲等級(jí)(SNR=[0,5,10,15,20,25,30] dB)干擾下的平均重構(gòu)信噪比,更進(jìn)一步驗(yàn)證了改進(jìn)的內(nèi)積匹配準(zhǔn)則的性能。其中,重構(gòu)信噪比公式為: (13) 表1 2種原子匹配準(zhǔn)則的重構(gòu)性能比較Table 1 Reconstruction performance comparisons of two atomic matching criterias 實(shí)驗(yàn)表明應(yīng)用改進(jìn)的內(nèi)積匹配準(zhǔn)則在稀疏度和測(cè)量數(shù)2個(gè)方面都優(yōu)于改進(jìn)前的內(nèi)積匹配準(zhǔn)則。在相同壓縮比時(shí),改進(jìn)的內(nèi)積匹配準(zhǔn)則有更高的重構(gòu)信噪比;在有相同的重構(gòu)效果下,改進(jìn)的內(nèi)積匹配準(zhǔn)則能適應(yīng)更低的信噪比,抗干擾性能更優(yōu)。改進(jìn)的內(nèi)積匹配準(zhǔn)則從向量的夾角信息和長(zhǎng)度數(shù)值信息2個(gè)方面更好地比較了向量間的相關(guān)性強(qiáng)弱,是一種更加合理有效的相關(guān)性度量準(zhǔn)則。 本部分比較了IMMP算法與OMP、StOMP、SP、CoSaMP和MMP等5種稀疏信號(hào)重構(gòu)算法的平均重構(gòu)性能,同時(shí)也分析了在相同迭代次數(shù)下不同初始步長(zhǎng)對(duì)IMMP算法性能影響。 圖3(a)給出了固定測(cè)量數(shù)M=100時(shí),重構(gòu)信號(hào)的ERR性能隨不同稀疏度K的變化曲線。從圖3(a)可以看出,本文提出的IMMP算法的ERR要高于傳統(tǒng)的重構(gòu)算法,尤其當(dāng)K>30時(shí),IMMP算法的ERR明顯遠(yuǎn)高于傳統(tǒng)算法。當(dāng)K=40時(shí),IMMP算法在初始步長(zhǎng)s={1,5,8,12}時(shí)的ERR為86.59%、87.51%、88.12%和88.79%,而除了CoSaMP算法ERR為0外,OMP、StOMP、SP和MMP算法的ERR分別僅為6.99%、34.91%、4.99%和40.85%。 圖3(b)顯示了各種算法對(duì)應(yīng)的CPU平均計(jì)算時(shí)間,客觀上可以比較算法的計(jì)算效率。MMP多路徑搜索算法計(jì)算時(shí)間隨著稀疏度K的增加呈現(xiàn)近似指數(shù)式增長(zhǎng),而OMP、StOMP、SP和CoSaMP算法的計(jì)算時(shí)間增加幅度不明顯。優(yōu)化搜索路徑后的IMMP算法的計(jì)算時(shí)間較OMP、StOMP、SP和CoSaMP等單路徑搜索算法略有增加,但遠(yuǎn)低于MMP算法。 圖3 不同稀疏度下IMMP算法性能驗(yàn)證Fig.3 IMMP algorithm performance verification with different sparsity 圖4給出了稀疏度K=30,隨著測(cè)量數(shù)M增大時(shí)各種算法的重構(gòu)成功率。容易由ERR曲線得到,除OMP算法外,其他算法在M>110時(shí)能取得極高的重構(gòu)成功率,而IMMP算法在測(cè)量數(shù)M>90時(shí)也達(dá)到了相似的優(yōu)良性能,所需測(cè)量數(shù)明顯減少。 圖4 不同測(cè)量數(shù)下的精確恢復(fù)比(K=30)Fig.4 The ERR for different measurements(K=30) 圖5說明了相應(yīng)算法的平均計(jì)算時(shí)間,在M<110時(shí),IMMP算法顯然比MMP算法花費(fèi)更少的時(shí)間;而當(dāng)M>110,IMMP算法由于要滿足迭代停止條件計(jì)算時(shí)間比其他算法要長(zhǎng),所以IMMP算法在壓縮比低的情況下更能體現(xiàn)出性能優(yōu)勢(shì)。 圖5 CPU平均計(jì)算時(shí)間Fig.5 Average CPU time of computation 實(shí)驗(yàn)結(jié)果表明,初始步長(zhǎng)的大小對(duì)IMMP算法的重構(gòu)性能影響也較為明顯。適當(dāng)大的初始步長(zhǎng)不僅能提高算法精確重構(gòu)成功率,還能有效降低算法的計(jì)算時(shí)間,提高算法重構(gòu)效率。IMMP算法具有良好的收斂速度和重構(gòu)質(zhì)量,表明優(yōu)化后的精確的搜索策略可以加速搜索候選支撐集。 1)本文提出的IMMP算法可以盲稀疏度自適應(yīng)估計(jì),自適應(yīng)選擇支撐集原子個(gè)數(shù);而且改進(jìn)的原子選擇方式能在高斯測(cè)量矩陣中更準(zhǔn)確高效地挑選與殘差信號(hào)匹配的原子,并結(jié)合剪枝技術(shù)優(yōu)化了MMP算法的路徑搜索,大大降低了算法計(jì)算時(shí)間。 2)MMP算法在迭代過程中采用支撐集原子回溯操作和指數(shù)變步長(zhǎng)方法大大提高了信號(hào)重構(gòu)精度。 3)仿真結(jié)果表明,該算法在不同測(cè)量數(shù)下性能有所差異,與傳統(tǒng)算法相比,得到的測(cè)量數(shù)較大時(shí),算法計(jì)算時(shí)間有所增加,可適當(dāng)減少迭代次數(shù)減少計(jì)算時(shí)間,而不會(huì)降低算法重構(gòu)精度;在測(cè)量數(shù)較少時(shí),該算法的信號(hào)重建精度高,運(yùn)行時(shí)間短,更貼合實(shí)際工程應(yīng)用。2 改進(jìn)的快速稀疏度自適應(yīng)多路徑匹配追蹤算法
2.1 改進(jìn)的內(nèi)積匹配準(zhǔn)則
2.2 剪枝優(yōu)化搜索路徑
2.3 稀疏度自適應(yīng)與指數(shù)變步長(zhǎng)
2.4 算法步驟
3 仿真驗(yàn)證
3.1 改進(jìn)的內(nèi)積匹配準(zhǔn)則的有效性驗(yàn)證
3.2 算法性能分析
4 結(jié)論