軟閾值變步長分段自適應(yīng)匹配追蹤算法

李姣軍，邱 天，蔣 揚(yáng)，楊 凡

（重慶理工大學(xué) 電氣與電子工程學(xué)院，重慶 400054）

對于信號數(shù)據(jù)采集，傳統(tǒng)的奈奎斯特采樣已廣泛應(yīng)用多年。但是在某些應(yīng)用中，為了滿足實(shí)時性和分辨率的需求，軟硬件設(shè)備面臨著許多挑戰(zhàn)，如采樣頻率不夠高，數(shù)據(jù)處理效率較低，占用過多存儲空間等問題。近年來，D L Donohon等［1-2］定義一種新的信號采樣理論——壓縮感知理論（compressed sensing，CS）。CS理論優(yōu)勢表現(xiàn)在獲取數(shù)據(jù)的同時對其進(jìn)行降維處理，且采樣頻率遠(yuǎn)遠(yuǎn)低于Nyquist采樣，既能節(jié)省硬件處理時間又可以釋放數(shù)據(jù)存儲空間，從而實(shí)現(xiàn)軟硬件工作資源利用最大化。因其具備以上優(yōu)點(diǎn)，使得壓縮感知應(yīng)用前景很廣，如圖像恢復(fù)［3］、深度學(xué)習(xí)［4］、雷達(dá)［5］、信道估計［6］等。

目前經(jīng)典的貪婪算法主要有正交匹配追蹤算法（orthogonal matching pursuit，OMP）［7］、正則化正交匹配追蹤算法（regularized orthogonal matching pursuit，ROMP）［8］、壓縮采樣匹配追蹤算法（compressive sampling matching pursuit，CoSAMP）［9］等。但上述算法只有在已知信號稀疏度先驗信息的前提下，才能有較好的重建質(zhì)量，而現(xiàn)實(shí)應(yīng)用中大多數(shù)信號的稀疏情況都是不確定的。Thong T Do等學(xué)者［10］研究并提出稀疏度自適應(yīng)匹配追蹤算法（sparsity adaptive matching pursuit，SAMP），它通過固定步長擴(kuò)大支撐集大小去逼近真實(shí)稀疏度，無需獲取稀疏度先驗信息即可實(shí)現(xiàn)信號重構(gòu)。但采取固定步長會帶來一個問題，若選擇步長過大容易造成過估計，影響重構(gòu)精度；若選擇步長過小容易造成欠估計，影響重構(gòu)效率，因此，如何兼顧重建精度和重建效率是個兩難的問題。文獻(xiàn)［11］提出一種變步長分段自適應(yīng)匹配追蹤（variable step size stagewise adaptive matching pursuit，VSStAMP）算法。該算法在迭代開始時選擇測量矩陣與當(dāng)前殘差前L個最相關(guān)原子，放入候選集合，設(shè)置階段標(biāo)識參數(shù)，把迭代分成大步長階段和小步長階段，能夠在保障重構(gòu)精度的同時提升重構(gòu)效率，很大程度上優(yōu)化了重構(gòu)性能。雖然VSStAMP算法引入變步長思想，可以有效克服過欠估計問題，但VSStAMP算法根據(jù)支撐集大小來決定原子數(shù)量與質(zhì)量，在大稀疏度情況下，迭代后期會有大量低相關(guān)原子入選，重建效果并不理想。文獻(xiàn)［12］提出一種設(shè)置固定閾值選擇原子的方法，能夠改善重構(gòu)質(zhì)量，但由于采取固定閾值，閾值的取值會直接影響重構(gòu)性能。

針對VSStAMP算法在迭代后期入選大量低相關(guān)原子的問題，本文提出了軟閾值變步長分段自適應(yīng)匹配追蹤（variable proportion-variable step size stagewise adaptive matching pursuit，VP-VSStAMP）算法。該算法在VSStAMP算法的基礎(chǔ)上，引入原子預(yù)選動態(tài)閾值β，靈活選擇滿足要求的優(yōu)質(zhì)原子，有效地提升重構(gòu)性能。為了保證算法準(zhǔn)確性，令初始閾值為βmax，即挑選出少量相關(guān)性較大的原子，此時支撐集中原子個數(shù)較少，有效節(jié)省重構(gòu)時間資源。隨著殘差迭代更新，閾值逐步遞減到下限βmin，此時支撐集嚴(yán)格把控入選原子的質(zhì)量，避免低相關(guān)原子入選，算法重構(gòu)精度能夠得到保證。

1 壓縮感知理論

假設(shè)離散信號x∈RN長度為N，若該信號在某個域上呈現(xiàn)稀疏性，則可以把該信號分解成某個稀疏基和某個列向量，即用N組維度為N×1的基函數(shù)Ψi（i=1，2，…，N）構(gòu)成一個N×N維稀疏基矩陣Ψ=［Ψ1，Ψ2，…，ΨN］，則x可表示成如下：

式中：θ為維度為N×1的加權(quán)系數(shù)列向量，其可用x和Ψ-1來表示，即θ=Ψ-1x，如果θ中只有K（K?N）個非零元素，即，則可認(rèn)為在Ψ域中原始信號x是稀疏的，K即為稀疏度。

經(jīng)過上式將信號重新表示后，需設(shè)計一個測量矩陣Φ∈RM×N（M?N），該測量矩陣Φ要最大限度地與正交基矩陣Ψ不相關(guān)。原始信號x通過測量矩陣Φ后，就實(shí)現(xiàn)了降維處理，即得到K維的測量信號y∈RM，其中包含原始信號x大部分有用信息，用來恢復(fù)重建信號，即：

式中，A=Φ·Ψ為M×N維的感知矩陣，可利用測量值y和恢復(fù)矩陣A來重構(gòu)向量θ，通過求解最優(yōu)化問題方法，即轉(zhuǎn)換成求解最小l0范數(shù)優(yōu)化問題：

其中c是一個常數(shù)，其值往往很?。?4］。

當(dāng)滿足上述幾項條件時，能夠?qū)⒆钚0范數(shù)優(yōu)化問題轉(zhuǎn)化為最小l1范數(shù)優(yōu)化問題，即：

當(dāng)前對最小l1范數(shù)優(yōu)化問題的解法可采用基追蹤（basis pursuit，BP）算法［15］，通過該算法恢復(fù)出來的信號重建精度較高，但因計算復(fù)雜度太高，其應(yīng)用領(lǐng)域較窄，具有一定的局限性；因此，貪婪迭代算法既能滿足一定重建精度且在算法復(fù)雜度上相對較低，很適合用于信號重構(gòu)。

2 VP-VSStAMP算法

2.1 算法思想

本文在VSStAMP算法的基礎(chǔ)上，作了適當(dāng)?shù)母倪M(jìn)，在原子預(yù)選階段加入動態(tài)閾值參數(shù)β，在算法開始時，設(shè)定一個上限閾值βmax，此時閾值門限要求較嚴(yán)格，僅有少量的原子能夠被選擇，且這些原子具有較高的相關(guān)性，可以有效控制參與重建的原子質(zhì)量與數(shù)量，加快算法的重建速度；在迭代過程中，β逐步遞減，適當(dāng)放寬閾值門限要求，能讓更多有效的原子參與重構(gòu)，提高算法的重建成功率。本文也給閾值β設(shè)定了一個下限值βmin，避免在迭代后期，因β值太低造成大量相關(guān)度較低的原子參與重構(gòu)，導(dǎo)致信號重建精度降低，且信號重建時間過長。

2.2 算法步驟

輸入：測量矩陣Φ，接受信號y，起始步長s，標(biāo)識閾值參數(shù)μ，原子預(yù)選閾值遞減參數(shù)β0。

1）初始化：迭代次數(shù)t=1，初始?xì)埐顁0=y，初始支撐集F0=?，支撐集大小L=s，初始階段標(biāo)識參數(shù)I=0，階段stage=1，初始原子預(yù)選閾值β=βmax，原子預(yù)選下限閾值βmin，標(biāo)識閾值參數(shù)μ，原子預(yù)選閾值遞減參數(shù)β0；

2）原子預(yù)選：根據(jù)動態(tài)閾值內(nèi)積法選擇質(zhì)量較高的原子，將其放入索引集：β·σt｝，其中

3）形成候選集Ct∶Ct=Ft-1∪St；

4）更新標(biāo)識：如果size（Ct）＞μ×M，則I=1；否則，I=0，其中size（Ct）表示候選集中的元素個數(shù)；

5）獲得支撐集F：如果size（Ct）＞L，則F=；否則，F(xiàn)=Ct；其中矩陣ΦCt由測量矩陣Φ中列索引為候選集Ct元素的列向量構(gòu)成，中選擇前L個最大的元素所對應(yīng)的索引；

9）令迭代次數(shù)t=t+1，并轉(zhuǎn)向步驟2），繼續(xù)向下執(zhí)行。

因為VSStAMP算法在原子初選階段，總是挑選內(nèi)積值最大的前L個原子，隨著階段數(shù)的增加，支撐集長度L逐漸變大，大量弱相關(guān)性的原子也會入選，而這些原子所包含的有用信息很少，反而會影響重構(gòu)精度。故為了在迭代前期加快重建速度，迭代后期保證重建精度，本算法在步驟2）通過動態(tài)閾值參數(shù)β來篩選原子的質(zhì)量，僅讓內(nèi)積值大于βσt的原子參與重構(gòu)，初始閾值β取上限值，能夠有效控制入選原子數(shù)目，且這些被挑選原子質(zhì)量較優(yōu)；在迭代后期β值遞減到下限值，可以淘汰相關(guān)性低的原子，僅保留有效的原子。步驟4）中，根據(jù)size（Ct）＞μ×M更新階段標(biāo)識參數(shù)I，根據(jù)1/4原則［16］，μ可取（0，1/4）內(nèi)任意實(shí)數(shù)。

3 仿真結(jié)果分析

3.1 不同上下限閾值的重構(gòu)性能

步驟2）中閾值參數(shù)β取值區(qū)間為［βmin，βmax］，上限閾值參數(shù)βmax的取值區(qū)間為［0.6，1］，下限閾值參數(shù)βmin的取值區(qū)間為［0，0.5］，為了研究上下閾值參數(shù)取值對性能的影響，先設(shè)定βmin=0.5進(jìn)行不同βmax下的仿真分析，得到VPVSStAMP算法中βmax對重構(gòu)性能的影響。仿真實(shí)驗采用128×256高斯隨機(jī)矩陣作為測量矩陣，選擇矩陣大小為256×1高斯隨機(jī)信號作為未知稀疏信號，稀疏度K為10～60，每隔5取一次值，取步長s=5。β每隔0.1取一次值，得到不同βmax對重構(gòu)成功率和重構(gòu)時長的影響。同理，固定βmax，得到βmin對重構(gòu)成功率和重構(gòu)時長的影響，每次實(shí)驗仿真500次，取其平均值。

經(jīng)過仿真對比，如圖1所示，固定下限閾值參數(shù)βmin不變，改變βmax。當(dāng)K＜45時，βmax值對重構(gòu)成功率影響不大；當(dāng)K＞50時，βmax值取0.8，算法的重構(gòu)成功率相對較高。由圖2可得，從重構(gòu)時間考慮，對于同一個稀疏度K來說，βmax值越大，重構(gòu)時間越短。綜合考慮重構(gòu)成功率和重構(gòu)時間，βmax宜取0.8。如圖3所示，固定上限閾值參數(shù)βmax不變，改變βmin，βmin值越大，重構(gòu)成功率越高，且在稀疏度K=60時，βmin取0.5仍有83.8%的重構(gòu)成功率。故下面VP-VSStAMP算法選擇βmax=0.8，βmin=0.5進(jìn)行仿真實(shí)驗。

圖1 不同βmax時VP-VSStAMP算法的重構(gòu)成功率

圖2 不同βmax時VP-VSStAMP算法的重構(gòu)時間

圖3 不同βmin時VP-VSStAMP算法的重構(gòu)成功率

3.2 VP-VSStAMP算法與其他算法重構(gòu)性能比較

本文所采用的仿真環(huán)境為AMD Ryzen 5 3600 6-core Processor CPU@3.60GHz，16 GBRAM，Matlab 2018a。在不添加噪聲的條件下，采用一維長度為N=256的稀疏信號，測量值M取128，VSStAMP算法和VP-VSStAMP算法μ取值均為1/8，為了算法準(zhǔn)確，VSStAMP算法、SAMP算法和VP-VSStAMP算法初始步長s=1，各類算法的迭代結(jié)束條件均為表示的是當(dāng)前殘差，ε是一個很小的數(shù)，仿真實(shí)驗中皆取10-6。對于不同稀疏度，各算法皆仿真實(shí)驗500次，稀疏度K∈［10，70］，每隔5取一次K值，取其平均值。

由圖4可得：在M=128，N=256時，VPVSStAMP算法重構(gòu)成功率優(yōu)于其他算法。在大稀疏度情況下，VSStAMP等其他算法重構(gòu)曲線下降過快。當(dāng)K=60時，VSStAMP算法僅有34.6%的重構(gòu)成功率，而VP-VSStAMP算法仍有85.4%，重構(gòu)成功率有所提升，最大可達(dá)50.8%左右，在稀疏度K大于60之后，傳統(tǒng)的SAMP算法和StAOMP算法重構(gòu)成功率皆為0。

圖4 不同算法重構(gòu)成功率隨稀疏度的變化關(guān)系

由圖5可得：在M=128，N=256，不添加噪聲的條件下，在小稀疏度時，各類算法重構(gòu)誤差近乎一致；在大稀疏度情況下，對比VSStAMP等其他算法，VP-VSStAMP算法重構(gòu)誤差改善明顯。重構(gòu)誤差改善最高可達(dá)2 dB左右，并且隨著稀疏度的增加，VP-VSStAMP算法的重構(gòu)誤差變化不大，始終保持在允許誤差范圍內(nèi)。

3.3 算法復(fù)雜度比較

從3.2節(jié)的仿真結(jié)果可得：在無噪條件下，無論是在重構(gòu)成功率還是在重構(gòu)誤差方面，VPVSStAMP算法的重構(gòu)效果優(yōu)于其他算法。本節(jié)將從算法復(fù)雜度討論算法重構(gòu)性能好壞，通過重構(gòu)時長指標(biāo)來評定算法復(fù)雜度。

圖5 不同算法重構(gòu)誤差隨稀疏度的變化關(guān)系

表1 不同算法重建信號運(yùn)行時長 s

從表1可得：在沒有噪聲的情況下，N=256，M=128時，觀察未知稀疏度K的SAMP算法、VSStAMP算法和本文提出的VP-VSStAMP算法，步長均取s=1，VP-VSStAMP算法所用重建時長少于SAMP算法，而多于VSStAMP算法，但隨著稀疏度的增加，該算法重構(gòu)成功率優(yōu)于VSStAMP算法3.2%～50.8%左右，且重構(gòu)誤差優(yōu)于VSStAMP算法0.7～2 dB左右。

綜合圖4、5和表1仿真結(jié)果，當(dāng)在大稀疏度情況時，在重建質(zhì)量方面，VP-VSStAMP算法具有較高的重構(gòu)成功率和較低的重構(gòu)誤差。在重建時長方面，VP-VSStAMP算法介于VSStAMP算法和SAMP算法之間。綜合對比其他算法，VP-VSStAMP算法整體重構(gòu)效果最優(yōu)。

4 結(jié)論

本文在傳統(tǒng)的VSStAMP算法的基礎(chǔ)上，引入動態(tài)閾值參數(shù)，提出了軟閾值變步長分段自適應(yīng)匹配追蹤（VP-VSStAMP）算法，有效克服VSStAMP算法在迭代后期有大量低相關(guān)原子入選的問題。該算法在原子預(yù)選階段設(shè)定動態(tài)閾值參數(shù)，在迭代初期選擇高質(zhì)量原子，在迭代后期淘汰低質(zhì)量原子，能夠保證在大稀疏度時仍有較好的重建性能，且通過變步長來加快重構(gòu)速度。仿真結(jié)果表明：在大稀疏度K條件下，相比傳統(tǒng)VSStAMP算法，VP-VSStAMP算法重構(gòu)成功率平均提高了25.7%，重構(gòu)誤差平均提高1.5 dB。