改進(jìn)的稀疏度自適應(yī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é)合測量矩陣和壓縮的信號(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)勢，受到越來越多的關(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è)固定步長多次迭代不斷逼近，達(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)勢。

1 壓縮感知與多路徑匹配追蹤算法

1.1 壓縮感知理論

由CS理論可知，將一個(gè)K-稀疏或在某一稀疏域能稀疏表示的N維離散數(shù)字信號(hào)通過某一個(gè)測量矩陣進(jìn)行有效壓縮，我們就能夠在線性變換下通過得到少量的觀測值精確重構(gòu)原始信號(hào)[10]。信號(hào)x中除了只有K個(gè)非零值外其余N-K個(gè)值均為零，且K遠(yuǎn)小于N。采樣和壓縮過程可以描述為：

y=Φx

(1)

式中：Φ是大小為M×N的測量矩陣，觀測值y的長度為M且滿足M?N。壓縮感知理論的目標(biāo)是基于觀測值y和測量矩陣Φ將重構(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)

1.2 MMP算法

MMP算法通過將搜索最優(yōu)路徑建模成基于樹的路徑搜索問題，每次迭代依據(jù)測量矩陣與殘差的相關(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與測量矩陣Φ的內(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) 輸入觀測向量y，測量矩陣Φ，稀疏度K，子路徑d，最大路徑迭代次數(shù)LMAX和停止迭代閾值ε，初始值l=0,rmin=y,Ω0=?,r0=y。

2) 如果lε，則用當(dāng)前參數(shù)l、d、k由優(yōu)先級(jí)函數(shù)layer_Order算法步驟得到當(dāng)前路徑節(jié)點(diǎn)搜索順序序列Cl，更新參數(shù)l=l+1，j=0；否則轉(zhuǎn)到步驟6)結(jié)束。

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ù)雜度。

2 改進(jìn)的快速稀疏度自適應(yīng)多路徑匹配追蹤算法

在實(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)行改良，利用閾值法選擇支撐集，并采用變步長思想來逼近信號(hào)稀疏度，并對(duì)MMP算法的搜索路徑進(jìn)行剪枝處理，在不影響重構(gòu)質(zhì)量的同時(shí)極大減少了運(yùn)算時(shí)間，使之更具實(shí)用價(jià)值。下面主要從以下幾個(gè)方面對(duì)IMMP算法進(jìn)行描述。

2.1 改進(jìn)的內(nèi)積匹配準(zhǔn)則

MMP等貪婪算法主要使用內(nèi)積匹配準(zhǔn)則度量測量矩陣與殘差值間的相關(guān)性強(qiáng)弱。傳統(tǒng)的內(nèi)積匹配準(zhǔn)則更多地是從方向上區(qū)分差異，而對(duì)絕對(duì)的數(shù)值不敏感，從而影響對(duì)相似原子的區(qū)分，使觀測矩陣中任意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)

2.2 剪枝優(yōu)化搜索路徑

(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)精度。

2.3 稀疏度自適應(yīng)與指數(shù)變步長

稀疏度自適應(yīng)算法設(shè)置的固定步長無法兼顧重構(gòu)精度和重構(gòu)效率，初始步長較小會(huì)降低算法重構(gòu)效率，步長較大則會(huì)降低算法重構(gòu)精度。采用兼顧兩者的變步長是一個(gè)不錯(cuò)的方法。根據(jù)稀疏度估計(jì)的特點(diǎn)，改進(jìn)算法稀疏度估計(jì)可以分為2個(gè)部分：1)初始階段大步長快速估計(jì)，2)完成階段小步長逐步逼近。

圖1 MMP和IMMP算法原理Fig.1 Schematic diagram of MMP and IMMP algorithms

文獻(xiàn)[22]研究表明,重構(gòu)信號(hào)的殘差能量在2個(gè)相鄰階段中是遞減的，且隨著支撐集長度λ不斷逼近真實(shí)稀疏度K，殘差能量減小速度逐漸變緩趨于穩(wěn)定。所以本文以相鄰階段重構(gòu)信號(hào)的殘差能量作為步長變換的條件。當(dāng)殘差能量小于等于‖rmin‖2時(shí)，步長切換更新稀疏度到下一階段，當(dāng)殘差能量小于ε2時(shí)稀疏度估計(jì)過程完成。ε2是迭代停止閾值，在這里取ε2=10-6。

利用ax指數(shù)函數(shù)的變化規(guī)律來調(diào)整步長，初始階段步長取一個(gè)合適的初值s0，每次增加步長s=s0ax，支撐集長度λ=λ+s；其中a是固定常數(shù)，文獻(xiàn)[23]證明當(dāng)a∈[0.3,0.5]時(shí)效果較好，x為當(dāng)前候選支撐集迭代次數(shù)，「·?表示向上取整。當(dāng)支撐集長度λ接近真實(shí)稀疏度K時(shí)，添加進(jìn)支撐集的原子越來越少，直到支撐集長度λ=λ+1。采用此變步長方法可提高算法重構(gòu)質(zhì)量和計(jì)算效率。

2.4 算法步驟

根據(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算法步驟如下：

3 仿真驗(yàn)證

本節(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ī)矩陣作為觀測矩陣，為避免隨機(jī)因素的干擾，每個(gè)算法都獨(dú)立重復(fù)進(jìn)行了10 000次試驗(yàn)且稀疏信號(hào)的非零位置都是隨機(jī)選擇的。

3.1 改進(jìn)的內(nèi)積匹配準(zhǔn)則的有效性驗(yàn)證

以典型的單路徑搜索算法OMP作為MMP算法中的一條搜索路徑中為例，分別使用內(nèi)積準(zhǔn)則和改進(jìn)的內(nèi)積準(zhǔn)則來度量觀測矩陣原子和殘差信號(hào)的相關(guān)性，以便挑選最為匹配的原子。隨機(jī)生成稀疏度K=30，長度N=256的一維信號(hào)作為測試信號(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)則在稀疏度和測量數(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)則從向量的夾角信息和長度數(shù)值信息2個(gè)方面更好地比較了向量間的相關(guān)性強(qiáng)弱，是一種更加合理有效的相關(guān)性度量準(zhǔn)則。

3.2 算法性能分析

本部分比較了IMMP算法與OMP、StOMP、SP、CoSaMP和MMP等5種稀疏信號(hào)重構(gòu)算法的平均重構(gòu)性能，同時(shí)也分析了在相同迭代次數(shù)下不同初始步長對(duì)IMMP算法性能影響。

圖3(a)給出了固定測量數(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算法在初始步長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ù)式增長，而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，隨著測量數(shù)M增大時(shí)各種算法的重構(gòu)成功率。容易由ERR曲線得到，除OMP算法外，其他算法在M>110時(shí)能取得極高的重構(gòu)成功率，而IMMP算法在測量數(shù)M>90時(shí)也達(dá)到了相似的優(yōu)良性能，所需測量數(shù)明顯減少。

圖4 不同測量數(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í)間比其他算法要長，所以IMMP算法在壓縮比低的情況下更能體現(xiàn)出性能優(yōu)勢。

圖5 CPU平均計(jì)算時(shí)間Fig.5 Average CPU time of computation

實(shí)驗(yàn)結(jié)果表明，初始步長的大小對(duì)IMMP算法的重構(gòu)性能影響也較為明顯。適當(dāng)大的初始步長不僅能提高算法精確重構(gòu)成功率，還能有效降低算法的計(jì)算時(shí)間，提高算法重構(gòu)效率。IMMP算法具有良好的收斂速度和重構(gòu)質(zhì)量，表明優(yōu)化后的精確的搜索策略可以加速搜索候選支撐集。

4 結(jié)論

1)本文提出的IMMP算法可以盲稀疏度自適應(yīng)估計(jì)，自適應(yīng)選擇支撐集原子個(gè)數(shù)；而且改進(jìn)的原子選擇方式能在高斯測量矩陣中更準(zhǔn)確高效地挑選與殘差信號(hào)匹配的原子，并結(jié)合剪枝技術(shù)優(yōu)化了MMP算法的路徑搜索，大大降低了算法計(jì)算時(shí)間。

2)MMP算法在迭代過程中采用支撐集原子回溯操作和指數(shù)變步長方法大大提高了信號(hào)重構(gòu)精度。

3)仿真結(jié)果表明，該算法在不同測量數(shù)下性能有所差異,與傳統(tǒng)算法相比，得到的測量數(shù)較大時(shí)，算法計(jì)算時(shí)間有所增加，可適當(dāng)減少迭代次數(shù)減少計(jì)算時(shí)間，而不會(huì)降低算法重構(gòu)精度；在測量數(shù)較少時(shí)，該算法的信號(hào)重建精度高，運(yùn)行時(shí)間短，更貼合實(shí)際工程應(yīng)用。