基于Dice系數的變步長自適應匹配追蹤算法

張世強，馬 可，張婷娟，黃 雷，宋人杰

(1.國網黑龍江省電力有限公司 伊春供電公司，黑龍江 伊春153000; 2.東北電力大學 計算機學院，吉林 吉林132012)

0 引 言

在信號處理領域中，傳統的信號處理方法為奈奎斯特采樣定理，即當采樣頻率為信號頻率的2倍時，該信號可以進行無失真的采樣。但是社會對于信號的帶寬需求越來越大，如果繼續利用奈奎斯特采樣定理進行信號處理，對于信號處理的物理硬件的研究會變得昂貴且復雜，而壓縮感知(Compressed Sensing，CS)[1]的出現很好地解決了這個問題。壓縮感知理論可以使信號在遠低于奈奎斯特采樣定理要求的采樣頻率下對信號進行采樣，并且幾乎無失真地重構出原信號。因此壓縮感知也成為當下的研究熱點，用于電能信號[2-3]傳輸等研究。

壓縮感知理論主要分為3部分：第1部分為信號的稀疏化，壓縮感知要求信號必須具有稀疏性，所謂稀疏性是指信號中大部分成分為0或趨近于0，只有小部分含有信號信息。但是自然界中的信號大多不是稀疏信號，因此要對信號進行稀疏處理，信號的稀疏化是壓縮感知理論的前提；第2部分為測量矩陣的設計，信號通過測量矩陣，就是對信號進行壓縮和采樣。測量矩陣的維度就是信號壓縮后的維度，對測量矩陣的要求是在壓縮矩陣的同時不能丟失信號的重要信息；第3部分為信號重構，目的是將壓縮后的信號無失真地恢復出來，在信號傳輸的過程中，信號重構是最為重要的一部分，重構算法的好壞直接決定了壓縮感知能否應用于實踐。

在重構算法中，貪婪算法因其算法結構簡單且重構性能較好的特點而廣泛應用在實際中。其中正交匹配追蹤(Orthogonal Match Pursuit，OMP)算法[4]是貪婪算法中最基礎的算法，該算法利用每次迭代挑選測量矩陣與信號殘差最相關的原子，用最小二乘法求出最優解，進而求出重構信號。在OMP的基礎上，研究人員相繼提出了正則化匹配追蹤(Regularization OMP，ROMP)算法[5]，廣義正交匹配追蹤(Generalized OMP，GOMP)算法[6]以及壓縮采樣匹配追蹤(Compression Sample Match Pursuit，CoSaMP)算法[7]。此類算法均有較高的信號重構精度，但是都有相同的缺點，即算法必須要在已知信號稀疏度的條件下進行，但是在實際應用中，大多數信號的稀疏度都是未知的，因此此類算法并沒有較高的應用能力。針對這個問題，T. Thong提出了稀疏度自適應匹配追蹤(Sparsity Adaptative Match Pursuit，SAMP)算法[8]，該算法設定1個估計稀疏度值和步長，然后通過步長使每次迭代中估計稀疏度都擴充步長大小，直至估計稀疏度與真實稀疏度相似或相等時，利用擴充集中的原子進行估計信號的計算。因此該算法可以在未知稀疏度的條件下對信號進行重構，擁有較為廣泛的應用前景。

但是SAMP算法仍存在一定缺陷，因為該算法使用固定步長估計稀疏度，因此對固定步長比較依賴，當步長設定較大時，在迭代后期會出現稀疏度過估計的情況，進而影響算法的重構性能。當步長設定較小時，則會增加算法的迭代次數，增加算法的運行時間，降低了SAMP算法的應用能力。針對這個問題，提出利用殘差控制步長的方式，將信號殘差分為2個區間，當殘差處在不同區間時，改變步長使估計稀疏度值可以逐步貼近真實稀疏度，減小稀疏度過估計的可能。同時，利用廣義Dice系數代替SAMP算法中的內積法求取原子相關性，使求出的相關性更加準確。

1 壓縮感知理論框架

壓縮感知的本質是信號經過測量矩陣后實現信號維度降低的過程，如式(1)所示。

y=Φx

(1)

式中：x為N×1維的信號；Φ為M×N的測量矩陣。其中M

當原信號x不是稀疏信號時，需要將信號先進行稀疏化使其變為稀疏信號，如式(2)所示。

x=Ψα

(2)

式中：α代表稀疏化的信號，如果α中包含K個非0元素(K=N)，或者說α中包含K個數值較大的元素，剩下的元素趨近于0。就證明經過α信號是原信號x通過稀疏基Ψ變換而來的K稀疏信號。

結合式(1)與式(2)，可以得出壓縮感知理論的通用方法如式(3)所示。

y=Φx=ΦΨα=Aα

(3)

式中：A=ΦΨ稱為感知矩陣。

在得到了壓縮后的信號y后，就可以利用信號重構算法，將y恢復成原信號x，如式(4)所示。

(4)

其中，x為N維且y為M維，因此有x個未知數求y個解，這本質上是一個NP-hard問題，針對這一問題，研究人員大多用基于l0范數的貪婪算法解決。

2 SAMP算法

SAMP算法是重構算法中應用最廣泛的算法，因為該算法可以在未知稀疏度的條件下進行對信號的重構。SAMP算法在迭代初始階段設定1個階段數Stage=1以及步長s，并在開始時將估計稀疏度值設定為1，每次迭代通過階段數控制估計稀疏度值的增長，如式(5)、(6)所示。

Stagek=Stagek-1+1

(5)

Lk=Stagek×s

(6)

式中：Lk為估計稀疏度值；Stagek為迭代次數。

從式(5)和式(6)可以看出，在每次迭代中估計稀疏度值都增加一個步長大小，直到估計稀疏度值與真實稀疏度值相近時，將信號重構出來。SAMP具體步驟如圖1所示。

由SAMP的算法步驟可以看出，該算法十分依賴步長的大小，如果步長選擇過大，則會出現稀疏度過估計的情況，影響算法重構結果。為了使估計稀疏度更精確，可以讓步長為1，逐步地增加稀疏度，但這樣也會加大算法的迭代次數，導致算法運行時間加長，降低了SAMP算法的實際應用能力。

輸入:M×N的感知矩陣A=ΦΨ,M×1的測量值y,初始步長s,停止閾值η,階段數Stage0=1初始化:初始殘差r0=y,支撐集∧0=?,候選集C0=?,初始稀疏度估計值L0=s,迭代次數k=11)計算原子相關度u=〈rk-1,A〉,并將前Lk個最大值的列序號加入集合Sk中2)得到支撐集∧k=∧k-1∪Sk3)利用最小二乘法求信號估計值^x∧k=A+∧k·y與殘差 rk-1=y-A∧k·^x∧k4)回溯:在x∧k中選擇Lk個最大值,將這些值對應的列序號記錄下來并加入集合F中5)利用F中的原子信息再次求取信號估計值^xF=A+F·y與殘差rnew=y-AF·^xF6)當rnew2≥rk-12時,Stagek=Stagek-1+1,Lk=Stagek×s,k=k+1返回步驟1),如果不滿足條件,rnew=rk-1,∧k=F,k=k+1返回步驟4)。7)當觸發rn2<η時,停止迭代,輸出重構所得信號估計值^x∧k輸出:信號x的近似估計值^x

3 改進SAMP算法

針對SAMP算法出現的不足，在2個方面做出改進。在貪婪算法中，重構信號的質量在于每次迭代選擇測量矩陣與信號殘差中相關原子的準確性，挑選的原子相關性越高，重構效果越好。但是在SAMP算法中是由內積法進行相關性的計算的。內積法就是求2個向量的夾角余弦值，余弦值越大代表2個向量越相似。內積法本質如式(7)所示，可以看到內積法中分母采用的是幾何平均數，根據平均值理論，幾何平均值的重點在于表現樣本總體變化趨勢，無法突出樣本中重要信息，因此在匹配過程中會有丟失部分原子信息的情況發生[9]，導致相關性計算不準確，進而影響重構結果。

(7)

針對這一問題，提出利用廣義Dice系數替換內積法來計算原子相關性。式(8)中展示了廣義Dice系數的本質，可以看出分子部分與內積法相同，但在分母中廣義Dice系數利用算術平均值代替幾何平均值。在平均值理論中，算術平均值代表樣本個體期望的無偏估計，因此能更好地保留原子信息。

(8)

圖2為不同相關性計算方法的結果對比，將2種計算原子相關性的方法帶入到基礎的SAMP算法中，除了相關性計算方法不同，其他的條件完全一致。

圖2 不同相關度所計算出的殘差

由圖2可以看出，使用廣義Dice系數的重構算法的殘差更快地趨近于0，證明廣義Dice系數計算的相關性更加精確。因此，在改進算法中用廣義Dice系數D〈x,y〉代替內積法進行原子相關性的計算。

sk=「0.5×sk-1?

(9)

Lk=Lk-1+sk

(10)

式中：s為步長；L為估計稀疏度值；「?為向上取整。

由式(9)可知，當殘差值處于第二區間時，步長在每次迭代中減小一半，并按照向上取整處理。這樣可以使步長迅速衰減為1，通過式(10)來計算估計稀疏度，可以看出步長越小，估計稀疏度增長越慢，因此在迭代后期步長減少至1時，可以逐步增加估計稀疏度值，減少稀疏度過估計的可能性。改進算法針對SAMP算法做出兩步改進，具體步驟如圖3所示。

輸入:M×N的感知矩陣A=ΦΨ,M×1的測量值y,初始步長S0,殘差閾值η1,η2,階段數Stage0=1初始化:初始殘差r0=y,支撐集∧0=?,候選集C0=?,初始稀疏度估計值L0=s,迭代次數k=11)計算原子相關度u=D〈rk-1,A〉,并將前Lk個最大值的列序號加入集合Sk中2)得到支撐集∧k=∧k-1∪Sk3)利用最小二乘法求信號估計值^x∧k=A+∧k·y與殘差 rk-1=y-A∧k·^x∧k4)回溯:在x∧k中選擇Lk個最大值,將這些值對應的列序號記錄下來并加入集合F中5)利用F中的原子信息再次求取信號估計值^xF=A+F·y與殘差rnew=y-AF·^xF6)當殘差rnew2≥η1時,如果rnew2≥rk-12,Stagek=Stagek-1+1,Lk=Stagek×s,k=k+1返回步驟1),如果不滿足條件,rnew=rk-1,∧k=F,k=k+1返回步驟4)。7)當η1>rnew2>η2時如果rnew2≥rk-1,sk=「0.5×sk-1?,Lk=Lk-1×sk,k=k+1返回步驟1),如果不滿足條件,rnew=rk-1,∧k=F,k=k+1返回步驟4)。8)當rn2<η2時,停止迭代,輸出重構所得信號估計值^x∧k輸出:信號x的近似估計值^x

4 仿真實驗

針對所提SAMP的改進算法進行仿真，來驗證其重構性能。采用長度為256的高斯隨機稀疏信號作為原始信號，測量矩陣為隨機產生且服從高斯分布的矩陣。所得實驗數據均是在4核Matlab2014b的條件下進行500次所取的平均值。

表1為2種算法估計稀疏度與真實稀疏度的差距，為了體現出固定步長的不足，仿真選取步長為3，測量數M=128。所提算法中殘差閾值分別為η1=10-2，η2=-10-6，SAMP的停止閾值設為10-6。可以看出，SAMP算法中估計稀疏度值受限于步長，只能做到貼近真實稀疏度，會出現稀疏度過估計或估計不足的情況。但是所提算法由于迭代后期改變了步長，因此可以做到與真實稀疏度相等，具有較好的重構結果。

表1 估計稀疏度與真實稀疏度的比較Table 1 Comparison between real sparsity and estimated sparsity

表2記錄了所提算法與SAMP算法的平均重構誤差對比。仿真選取測量值M∈[115,140]，K=30。其他實驗條件與上一個實驗條件相同。可以看出，由于使用了變步長的策略以及廣義Dice系數，因此所提算法的重構誤差要遠小于SAMP算法。證明了所提算法在多頻帶信號重構上有著更高的重構精度。

表2 算法在不同測量值下誤差的比較Table 2 Error comparison of two algorithms under different measured values (×10-14)

表3比較了2種算法的平均運行時間，雖然所提算法使用了變步長的策略，后期步長減小會增加迭代次數，但是由于使用了廣義Dice系數計算原子相關度，因此在原子的選擇上更加精確，可以使算法更快地收斂，因此所提算法的運行速度比SAMP算法高出10%～20%。基于表2和表3可以得出，在一維信號的重構表現上，所提算法擁有更好的重構性能。

表3 算法在不同測量值下運行時間的比較Table 3 Comparison of running time of algorithm under different measured values s

在驗證了所提算法在一維信號中有較好的重構性能后，用二維圖像信號驗證所提算法的普適性，圖4為所提算法與SAMP算法對二維圖像的重構結果。

圖像采用256×256的2張實際電廠圖像[10-11]作為二維信號，稀疏基采用小波稀疏基，仿真中用峰值信噪比(Peak Signalto Noise Ratio，PSNR)來表示重構的精度，PSNR值越高代表重構效果越好。測量值M=128，所提算法與SAMP算法的步長均為3。圖4表示所提算法與SAMP算法對圖像信號的重構結果，可以看出所提算法的PSNR值相比SAMP算法要高2 dB左右，證明所提算法在圖片的細節上重構得更加精細，重構效果更好。

5 結 語

針對SAMP算法中固定步長會影響估計稀疏度值計算的問題。采取了2種改進方案：

1)用廣義Dice系數代替原有的內積法，使計算出的原子相關性更準確。

2)利用殘差控制步長，當殘差值處于一定區間時，逐步減小步長，減少稀疏度過估計的情況。

利用一維信號與二維信號的仿真實驗證明所提算法具有良好的重構性能。