張世強(qiáng)，馬 可，張婷娟，黃 雷，宋人杰

(1.國(guó)網(wǎng)黑龍江省電力有限公司 伊春供電公司，黑龍江 伊春153000; 2.東北電力大學(xué) 計(jì)算機(jī)學(xué)院，吉林 吉林132012)

0 引 言

在信號(hào)處理領(lǐng)域中，傳統(tǒng)的信號(hào)處理方法為奈奎斯特采樣定理，即當(dāng)采樣頻率為信號(hào)頻率的2倍時(shí)，該信號(hào)可以進(jìn)行無(wú)失真的采樣。但是社會(huì)對(duì)于信號(hào)的帶寬需求越來(lái)越大，如果繼續(xù)利用奈奎斯特采樣定理進(jìn)行信號(hào)處理，對(duì)于信號(hào)處理的物理硬件的研究會(huì)變得昂貴且復(fù)雜，而壓縮感知(Compressed Sensing，CS)[1]的出現(xiàn)很好地解決了這個(gè)問(wèn)題。壓縮感知理論可以使信號(hào)在遠(yuǎn)低于奈奎斯特采樣定理要求的采樣頻率下對(duì)信號(hào)進(jìn)行采樣，并且?guī)缀鯚o(wú)失真地重構(gòu)出原信號(hào)。因此壓縮感知也成為當(dāng)下的研究熱點(diǎn)，用于電能信號(hào)[2-3]傳輸?shù)妊芯俊?/p>

壓縮感知理論主要分為3部分：第1部分為信號(hào)的稀疏化，壓縮感知要求信號(hào)必須具有稀疏性，所謂稀疏性是指信號(hào)中大部分成分為0或趨近于0，只有小部分含有信號(hào)信息。但是自然界中的信號(hào)大多不是稀疏信號(hào)，因此要對(duì)信號(hào)進(jìn)行稀疏處理，信號(hào)的稀疏化是壓縮感知理論的前提；第2部分為測(cè)量矩陣的設(shè)計(jì)，信號(hào)通過(guò)測(cè)量矩陣，就是對(duì)信號(hào)進(jìn)行壓縮和采樣。測(cè)量矩陣的維度就是信號(hào)壓縮后的維度，對(duì)測(cè)量矩陣的要求是在壓縮矩陣的同時(shí)不能丟失信號(hào)的重要信息；第3部分為信號(hào)重構(gòu)，目的是將壓縮后的信號(hào)無(wú)失真地恢復(fù)出來(lái)，在信號(hào)傳輸?shù)倪^(guò)程中，信號(hào)重構(gòu)是最為重要的一部分，重構(gòu)算法的好壞直接決定了壓縮感知能否應(yīng)用于實(shí)踐。

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

但是SAMP算法仍存在一定缺陷，因?yàn)樵撍惴ㄊ褂霉潭ú介L(zhǎng)估計(jì)稀疏度，因此對(duì)固定步長(zhǎng)比較依賴，當(dāng)步長(zhǎng)設(shè)定較大時(shí)，在迭代后期會(huì)出現(xiàn)稀疏度過(guò)估計(jì)的情況，進(jìn)而影響算法的重構(gòu)性能。當(dāng)步長(zhǎng)設(shè)定較小時(shí)，則會(huì)增加算法的迭代次數(shù)，增加算法的運(yùn)行時(shí)間，降低了SAMP算法的應(yīng)用能力。針對(duì)這個(gè)問(wèn)題，提出利用殘差控制步長(zhǎng)的方式，將信號(hào)殘差分為2個(gè)區(qū)間，當(dāng)殘差處在不同區(qū)間時(shí)，改變步長(zhǎng)使估計(jì)稀疏度值可以逐步貼近真實(shí)稀疏度，減小稀疏度過(guò)估計(jì)的可能。同時(shí)，利用廣義Dice系數(shù)代替SAMP算法中的內(nèi)積法求取原子相關(guān)性，使求出的相關(guān)性更加準(zhǔn)確。

1 壓縮感知理論框架

壓縮感知的本質(zhì)是信號(hào)經(jīng)過(guò)測(cè)量矩陣后實(shí)現(xiàn)信號(hào)維度降低的過(guò)程，如式(1)所示。

y=Φx

(1)

式中：x為N×1維的信號(hào)；Φ為M×N的測(cè)量矩陣。其中M

當(dāng)原信號(hào)x不是稀疏信號(hào)時(shí)，需要將信號(hào)先進(jìn)行稀疏化使其變?yōu)橄∈栊盘?hào)，如式(2)所示。

x=Ψα

(2)

式中：α代表稀疏化的信號(hào)，如果α中包含K個(gè)非0元素(K=N)，或者說(shuō)α中包含K個(gè)數(shù)值較大的元素，剩下的元素趨近于0。就證明經(jīng)過(guò)α信號(hào)是原信號(hào)x通過(guò)稀疏基Ψ變換而來(lái)的K稀疏信號(hào)。

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

y=Φx=ΦΨα=Aα

(3)

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

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

(4)

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

2 SAMP算法

SAMP算法是重構(gòu)算法中應(yīng)用最廣泛的算法，因?yàn)樵撍惴梢栽谖粗∈瓒鹊臈l件下進(jìn)行對(duì)信號(hào)的重構(gòu)。SAMP算法在迭代初始階段設(shè)定1個(gè)階段數(shù)Stage=1以及步長(zhǎng)s，并在開(kāi)始時(shí)將估計(jì)稀疏度值設(shè)定為1，每次迭代通過(guò)階段數(shù)控制估計(jì)稀疏度值的增長(zhǎng)，如式(5)、(6)所示。

Stagek=Stagek-1+1

(5)

Lk=Stagek×s

(6)

式中：Lk為估計(jì)稀疏度值；Stagek為迭代次數(shù)。

從式(5)和式(6)可以看出，在每次迭代中估計(jì)稀疏度值都增加一個(gè)步長(zhǎng)大小，直到估計(jì)稀疏度值與真實(shí)稀疏度值相近時(shí)，將信號(hào)重構(gòu)出來(lái)。SAMP具體步驟如圖1所示。

由SAMP的算法步驟可以看出，該算法十分依賴步長(zhǎng)的大小，如果步長(zhǎng)選擇過(guò)大，則會(huì)出現(xiàn)稀疏度過(guò)估計(jì)的情況，影響算法重構(gòu)結(jié)果。為了使估計(jì)稀疏度更精確，可以讓步長(zhǎng)為1，逐步地增加稀疏度，但這樣也會(huì)加大算法的迭代次數(shù)，導(dǎo)致算法運(yùn)行時(shí)間加長(zhǎng)，降低了SAMP算法的實(shí)際應(yīng)用能力。

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

3 改進(jìn)SAMP算法

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

(7)

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

(8)

圖2為不同相關(guān)性計(jì)算方法的結(jié)果對(duì)比，將2種計(jì)算原子相關(guān)性的方法帶入到基礎(chǔ)的SAMP算法中，除了相關(guān)性計(jì)算方法不同，其他的條件完全一致。

圖2 不同相關(guān)度所計(jì)算出的殘差

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

sk=「0.5×sk-1?

(9)

Lk=Lk-1+sk

(10)

式中：s為步長(zhǎng)；L為估計(jì)稀疏度值；「?為向上取整。

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

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

4 仿真實(shí)驗(yàn)

針對(duì)所提SAMP的改進(jìn)算法進(jìn)行仿真，來(lái)驗(yàn)證其重構(gòu)性能。采用長(zhǎng)度為256的高斯隨機(jī)稀疏信號(hào)作為原始信號(hào)，測(cè)量矩陣為隨機(jī)產(chǎn)生且服從高斯分布的矩陣。所得實(shí)驗(yàn)數(shù)據(jù)均是在4核Matlab2014b的條件下進(jìn)行500次所取的平均值。

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

表1 估計(jì)稀疏度與真實(shí)稀疏度的比較Table 1 Comparison between real sparsity and estimated sparsity

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

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

表3比較了2種算法的平均運(yùn)行時(shí)間，雖然所提算法使用了變步長(zhǎng)的策略，后期步長(zhǎng)減小會(huì)增加迭代次數(shù)，但是由于使用了廣義Dice系數(shù)計(jì)算原子相關(guān)度，因此在原子的選擇上更加精確，可以使算法更快地收斂，因此所提算法的運(yùn)行速度比SAMP算法高出10%～20%?；诒?和表3可以得出，在一維信號(hào)的重構(gòu)表現(xiàn)上，所提算法擁有更好的重構(gòu)性能。

表3 算法在不同測(cè)量值下運(yùn)行時(shí)間的比較Table 3 Comparison of running time of algorithm under different measured values s

在驗(yàn)證了所提算法在一維信號(hào)中有較好的重構(gòu)性能后，用二維圖像信號(hào)驗(yàn)證所提算法的普適性，圖4為所提算法與SAMP算法對(duì)二維圖像的重構(gòu)結(jié)果。

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

5 結(jié) 語(yǔ)

針對(duì)SAMP算法中固定步長(zhǎng)會(huì)影響估計(jì)稀疏度值計(jì)算的問(wèn)題。采取了2種改進(jìn)方案：

1)用廣義Dice系數(shù)代替原有的內(nèi)積法，使計(jì)算出的原子相關(guān)性更準(zhǔn)確。

2)利用殘差控制步長(zhǎng)，當(dāng)殘差值處于一定區(qū)間時(shí)，逐步減小步長(zhǎng)，減少稀疏度過(guò)估計(jì)的情況。

利用一維信號(hào)與二維信號(hào)的仿真實(shí)驗(yàn)證明所提算法具有良好的重構(gòu)性能。