軟閾值變步長分段自適應匹配追蹤算法

李姣軍，邱 天，蔣 揚，楊 凡

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

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

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

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

1 壓縮感知理論

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

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

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

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

其中c是一個常數，其值往往很小［14］。

當滿足上述幾項條件時，能夠將最小l0范數優化問題轉化為最小l1范數優化問題，即：

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

2 VP-VSStAMP算法

2.1 算法思想

本文在VSStAMP算法的基礎上，作了適當的改進，在原子預選階段加入動態閾值參數β，在算法開始時，設定一個上限閾值βmax，此時閾值門限要求較嚴格，僅有少量的原子能夠被選擇，且這些原子具有較高的相關性，可以有效控制參與重建的原子質量與數量，加快算法的重建速度；在迭代過程中，β逐步遞減，適當放寬閾值門限要求，能讓更多有效的原子參與重構，提高算法的重建成功率。本文也給閾值β設定了一個下限值βmin，避免在迭代后期，因β值太低造成大量相關度較低的原子參與重構，導致信號重建精度降低，且信號重建時間過長。

2.2 算法步驟

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

1）初始化：迭代次數t=1，初始殘差r0=y，初始支撐集F0=?，支撐集大小L=s，初始階段標識參數I=0，階段stage=1，初始原子預選閾值β=βmax，原子預選下限閾值βmin，標識閾值參數μ，原子預選閾值遞減參數β0；

2）原子預選：根據動態閾值內積法選擇質量較高的原子，將其放入索引集：β·σt｝，其中

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

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

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

9）令迭代次數t=t+1，并轉向步驟2），繼續向下執行。

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

3 仿真結果分析

3.1 不同上下限閾值的重構性能

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

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

圖1 不同βmax時VP-VSStAMP算法的重構成功率

圖2 不同βmax時VP-VSStAMP算法的重構時間

圖3 不同βmin時VP-VSStAMP算法的重構成功率

3.2 VP-VSStAMP算法與其他算法重構性能比較

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

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

圖4 不同算法重構成功率隨稀疏度的變化關系

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

3.3 算法復雜度比較

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

圖5 不同算法重構誤差隨稀疏度的變化關系

表1 不同算法重建信號運行時長 s

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

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

4 結論

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