王雪瑞,周巖

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

?

基于差分演化-MP的快速信號(hào)稀疏分解

王雪瑞,周巖

(河南工程學(xué)院 計(jì)算機(jī)學(xué)院，河南 鄭州 451191)

針對(duì)傳統(tǒng)的稀疏分解算法存在的計(jì)算量大和耗費(fèi)時(shí)間長(zhǎng)的缺點(diǎn)，利用差分演化算法具有魯棒性強(qiáng)和全局收斂性好的優(yōu)點(diǎn)，提出了一種基于差分演化的匹配追蹤算法(DE-MP).算法使用差分演化(DE)算法替換傳統(tǒng)匹配追蹤(MP)算法中的遍歷搜索策略，優(yōu)化了尋找稀疏分解最優(yōu)原子的過程，從而大大降低了算法復(fù)雜度.此外，DE算法特殊的搜索策略很好地提高M(jìn)P的全局收斂性，進(jìn)一步提高了稀疏分解的準(zhǔn)確性.通過對(duì)雷達(dá)仿真信號(hào)和語(yǔ)音信號(hào)仿真實(shí)驗(yàn)結(jié)果表明：與傳統(tǒng)MP算法相比，差分演化匹配追蹤算法(DE-MP)在計(jì)算速度提高了兩個(gè)數(shù)量級(jí)，在收斂精度上也有明顯提高，且收斂精度優(yōu)于其他改進(jìn)MP算法.

信號(hào)稀疏分解；匹配追蹤；差分演化算法；正交匹配

0 引 言

信號(hào)稀疏分解理論由于具有顯著的自適應(yīng)性，靈活性等優(yōu)點(diǎn)，因此在信號(hào)處理領(lǐng)域的研究發(fā)展迅速起來，并在信號(hào)壓縮、特征提取、去噪、超分辨重建等領(lǐng)域有著廣泛的應(yīng)用[1-2].然而常用稀疏分解算法運(yùn)算量都十分巨大，這是因?yàn)樵谶^完備字典中選擇信號(hào)的最優(yōu)逼近方式被證明是一個(gè)NP問題，而這也成為阻礙其在信號(hào)處理領(lǐng)域進(jìn)一步發(fā)展的致命缺[3-4].國(guó)內(nèi)外許多研究者針對(duì)現(xiàn)有的稀疏分解算法的缺點(diǎn)進(jìn)行了深入的研究，方輝等人[5]提出了一種模擬退火MP算法，該算法使用模擬退火處理的方法選擇原子，提高信號(hào)稀疏分解速度.侯坤等[6]人提出一種ABC-MP算法，利用人工蜂群算法尋找近似最佳原子.Mariral[7]提出自適應(yīng)學(xué)習(xí)算法構(gòu)造稀疏表示學(xué)習(xí)字典，對(duì)樣本集學(xué)習(xí)出稀疏表示原子，能較好地匹配信號(hào)的結(jié)構(gòu)特征，但計(jì)算復(fù)雜度仍然很大.為此，本文將DE算法引入MP算法中，提出了一種DE-MP算法，利用差分算法來優(yōu)化MP算法每一次尋找稀疏分解最優(yōu)原子的過程，從而大大提高M(jìn)P算法的收斂速度和增強(qiáng)其全局搜索能力.改進(jìn)后的算法結(jié)構(gòu)簡(jiǎn)單，易操作，大幅度減少了計(jì)算的復(fù)雜度，并進(jìn)一步提高了收斂精度.

1 信號(hào)稀疏分解描述

在實(shí)際生活中，信號(hào)都是由很多種信號(hào)混合而成的.這種混合信號(hào)很難在完備正交基中有效地表示出來的，并且完備正交基的表示過于復(fù)雜，不利于信號(hào)處理的識(shí)別和壓縮等.因此，這些混合信號(hào)采用稀疏表示對(duì)其處理非常有利，并且過完備系統(tǒng)比正交基也在非線性逼近理論中得到了證明.

1.1 稀疏逼近的定義

假設(shè)集合D={gk;k=1,2,...,K}，K≥N，集合D又稱為原字庫(kù)，其中元素稱為原子，則Hilbert(H=RN)空間中單位矢量可以由原字庫(kù)中原子表示.選取信號(hào)y∈H，在D中選取m個(gè)原子對(duì)信號(hào)y做m項(xiàng)逼近，具體表示如下：

(1)

其中，Im是gγ的下標(biāo)集，cγ是展開系數(shù)，則A=span(gγ,γ∈Im)就是由m個(gè)原子在庫(kù)D中組成的最佳子集，gγ是由參數(shù)組γ定義的原子，且每個(gè)原子的長(zhǎng)度和待分解的信號(hào)長(zhǎng)度一致，近似誤差為：

(2)

由于m遠(yuǎn)遠(yuǎn)小于空間的維數(shù)N，所以這種逼近也被稱作稀疏逼近.原子庫(kù)是冗余的，導(dǎo)致gγ不能線性獨(dú)立，故信號(hào)有多種表示方法.對(duì)不同的表示方法進(jìn)行選擇時(shí)，必須在滿足公式(2)中近似誤差定義的基礎(chǔ)上，選出分解系數(shù)最為稀疏的組合.

1.2 過完備原字庫(kù)

長(zhǎng)度為N的信號(hào)y，且y=H∈RN，H=RN是N維Hilbert空間.信號(hào)的稀疏表示過程中，基在其構(gòu)造空間中非常的密，導(dǎo)致其不絕對(duì)正交，此時(shí)的基稱為原子，這些基組成的集合稱為過完備原子庫(kù).

采用文獻(xiàn)[8]中過完備原子庫(kù)的生成方法，具體生成公式如下所示：

(3)

其中，g(t)=e-πt2是高斯窗函數(shù)，γ=(s,u,w,φ)是產(chǎn)生原子的4個(gè)時(shí)頻參數(shù)，s代表伸縮因子、u代表位移因子、w代表頻率、φ代表相位[6].將這些參數(shù)進(jìn)行離散化的方法為：

γ=(aj,pajΔu,ka-jΔv,iΔw)

(4)

2 匹配追蹤算法與差分演化算法

2.1 匹配追蹤算法

匹配追蹤(MP)算法原理是以貪婪算法為基礎(chǔ)，采用不斷逼近的方法求得信號(hào)的稀疏表示，具體的步驟如下：

首先在過完備原子庫(kù)中匹配出與初始信號(hào)最為近似的原子gγ0，同時(shí)，gγ0要使公式(5)成立.

(5)

然后，再根據(jù)上式對(duì)信號(hào)進(jìn)行匹配迭代，得出gγ0的分量和殘余分量Ry，方法如下：

y=〈y,gγ0〉gγ0+Ry

(6)

殘余分量Ry是信號(hào)y減去最佳原子gγ0所占的分量后得到的殘差部分，通過將殘差Ry在過完備原子庫(kù)D上投影得到新的分量，依次進(jìn)行投影求殘差，MP算法就是不斷地進(jìn)行上述同樣的分解過程，即：

Rhy=〈Rhy,gγh〉gγh+Rh+1y

(7)

每一次迭代選擇最小殘差量Ry，gγh需滿足：

(8)

其中，迭代得到殘差Ry的過程，都可看作是從原子庫(kù)中取一個(gè)最優(yōu)原子對(duì)原始信號(hào)進(jìn)行重構(gòu)的過程.這樣經(jīng)過n次迭代后，信號(hào)可以表示為如下的線性組合：

(9)

其中，Rny為n次分解后的誤差值，該數(shù)值很小時(shí)，表明經(jīng)特定數(shù)目n個(gè)過完備原子的線性組合已經(jīng)很逼近原始信號(hào)了，而且n?N，N為信號(hào)采樣點(diǎn)數(shù).

2.2 差分演化算法

差分演化(DE)是一種新興的演化算法，算法中同樣包含變異和、交叉和選擇等操作[9].主要包括以下步驟：

1)種群初始.在定義域的范圍內(nèi)，隨機(jī)產(chǎn)生Pop個(gè)樣本矢量；

2)差分變異.任意選擇兩個(gè)樣本做比例差分，再然后跟另外任意一個(gè)樣本相加得到變異種群PV,m中的變異樣本Vi,m，具體方法如公式(10)所示.

Vi,m=Xr1,m+F(Xr2,m-Xr3,m)

(10)

其中,F∈(0,1)為比例因子，主要控制變異的大小，Xr2,m-Xr3,m為兩個(gè)群體的差異向量.

3)差分交叉.新一代種群PU,m=(Ui,m)是通過上一代種群PX,m和變異的種群PV,m樣本數(shù)值的融合交叉得到的，交叉規(guī)則如下：

(11)

其中，交叉概率PC∈[0,1]，用來控制變異樣本數(shù)值對(duì)試驗(yàn)樣本數(shù)值的替代概率，若小于PC，替代為試驗(yàn)樣本，否則為原樣本.

4)差分選擇.比較Ui,m的目標(biāo)函數(shù)值與Xi,m的目標(biāo)函數(shù)值大小，選擇較優(yōu)者替換Xi,m.

5) 判斷是否符合算法結(jié)束條件，不滿足繼續(xù)迭代，否則輸出結(jié)果.

3 差分演化的分解策略

3.1 算法原理

由于傳統(tǒng)MP算法進(jìn)行信號(hào)稀疏分解時(shí)，實(shí)際上是使用遍歷搜索的方法來尋找全局最優(yōu)原子，即信號(hào)或信號(hào)殘差需要和冗雜的原子庫(kù)中的每一個(gè)原子做內(nèi)積完成投影計(jì)算，而內(nèi)積值計(jì)算是在一個(gè)高維空間上求解得到的，因此算法的計(jì)算復(fù)雜度非常高.本文利用分演化算法來替代MP算法中遍歷搜索的方法尋找較優(yōu)原子，進(jìn)而減低算法的計(jì)算復(fù)雜度.

3.2 DE-MP算法流程

DE-MP算法的具體流程如下，其中差分演化算法找出最優(yōu)原子的過程與標(biāo)準(zhǔn)差分演化算法一致.

1)MP算法初始化；

2)將原子參數(shù)編碼.每個(gè)原子的4個(gè)參數(shù)作為算法中尋優(yōu)樣本的四維數(shù)值，適應(yīng)度函數(shù)為待分解信號(hào)或者該信號(hào)殘差和每個(gè)原子的投影內(nèi)積值；

3)使用差分演化算法找出最優(yōu)原子；

4)計(jì)算每個(gè)樣本的適應(yīng)值，即對(duì)應(yīng)的投影內(nèi)積值，求信號(hào)殘差；

5)當(dāng)達(dá)到了預(yù)設(shè)的殘差閾值或算法迭代次數(shù)，就可以得到最優(yōu)的結(jié)果，否則返回步驟2).這里使用迭代次數(shù)為終止條件.

4 仿真實(shí)驗(yàn)結(jié)果與分析

為了直觀且定性地看出DE-MP算法的稀疏分解效果，將DE-MP算法分別進(jìn)行了模擬雷達(dá)信號(hào)與語(yǔ)言信號(hào)兩組測(cè)試.

4.1 模擬雷達(dá)信號(hào)仿真

實(shí)驗(yàn)采用長(zhǎng)度N為128，由式(12)產(chǎn)生的模擬雷達(dá)信號(hào)，如圖1所示.

圖1 模擬雷達(dá)原始信號(hào)

圖2 過完備

產(chǎn)生原子的4個(gè)時(shí)頻參數(shù)γ=(s,u,w,φ)對(duì)應(yīng)的個(gè)體范圍最大值分別為N、N、2π、2π，最小值均為0.產(chǎn)生原子如圖2所示.

使用上述的DE-MP算法對(duì)模擬信號(hào)進(jìn)行仿真，相關(guān)參數(shù)如DE算法的種群規(guī)模Pop、迭代次數(shù)Loop、維度dim、尺度F、變異概率PC、形成過完備原子的4個(gè)參數(shù)最大值s,u,w,φ均按照表1設(shè)置.

表1 參數(shù)設(shè)置

算法的終止條件為稀疏分解得到的原子數(shù)M.

(12)

經(jīng)過稀疏分解后得到的重建信號(hào)如圖3所示.

圖3 DE+MP重建信號(hào)

圖4 語(yǔ)音原始信號(hào)

對(duì)比圖1和圖3可以看出由DE-MP算法稀疏分解重建的信號(hào)與原始信號(hào)十分接近.

4.2 語(yǔ)音信號(hào)仿真

采用Matlab自帶的語(yǔ)音信號(hào)“bird.wav”進(jìn)行仿真實(shí)驗(yàn)，選取第11000∶12023個(gè)信號(hào)采樣點(diǎn)組成長(zhǎng)度N為1024的音頻信號(hào)，如圖4所示.參數(shù)如表1所示設(shè)置.

采用DE-MP算法進(jìn)行稀疏分解得到的語(yǔ)音重建如圖5所示.

圖5 DE-MP重建信號(hào)

對(duì)比圖4和圖5，可以看出由DE-MP算法稀疏分解重建的信號(hào)與原始信號(hào)并無多大區(qū)別.

4.3 實(shí)驗(yàn)分析

通過對(duì)模擬雷達(dá)信號(hào)和語(yǔ)言信號(hào)測(cè)試，可知DE-MP算法具有良好的稀疏分解效果[11].為了進(jìn)一步驗(yàn)證DE-MP算法性能，采用傳統(tǒng)MP算法和DE-MP算法進(jìn)行對(duì)比，實(shí)驗(yàn)也采用語(yǔ)音信號(hào)“bird.wav”，選取第11000∶11256信號(hào)采樣點(diǎn)組成長(zhǎng)度N為256的音頻信號(hào)，M=80，其他參數(shù)如表1所示設(shè)置.

為了準(zhǔn)確地比較兩種算法性能.采用信號(hào)的均方誤差(MSE)，即原始信號(hào)和重建信號(hào)的誤差為衡量標(biāo)準(zhǔn)，來定量的比較信號(hào)稀疏分解的重建效果，MSE計(jì)算公式如公式(13)所示:

(13)

經(jīng)過稀疏分解以后得到的重建信號(hào)所計(jì)算的MSE值代表其與待處理的原始信號(hào)的表征程度，差異度越小即MSE值越小，說明算法的準(zhǔn)確度越高，分解結(jié)果越好.表2為MP和DE-MP的測(cè)試結(jié)果.

表2 兩種算法測(cè)試結(jié)果

由表2可知，本文算法與傳統(tǒng)MP算法相比，時(shí)間復(fù)雜度有著顯著下降，計(jì)算時(shí)間縮短了兩個(gè)數(shù)量級(jí)，此外，在算法精度上也有一定程度提高.

為了進(jìn)一步驗(yàn)證DE-MP算法的性能，選取了傅里葉變換匹配追蹤算法(FFT-MP)[12]、遺傳匹配追蹤算法(GA-MP)[13]、粒子群算法追蹤算法(PSO-MP)[14]進(jìn)行對(duì)比實(shí)驗(yàn)，所有算法采用相同參數(shù)設(shè)置，如表1所示，得到的結(jié)果如表3所示，由于運(yùn)行環(huán)境不一致無法進(jìn)行時(shí)間測(cè)試，故只比價(jià)算法MSE值.

表3 4種改進(jìn)算法結(jié)果對(duì)比

從表3看出，在與3種經(jīng)典改進(jìn)策略優(yōu)化的匹配追蹤算法相比時(shí)，DE-MP算法得到的MSE值最小，具有最高的計(jì)算精度.由此可見利用DE-MP算法，在準(zhǔn)確度與計(jì)算速度之間取得良好平衡，在確保算法稀疏分解準(zhǔn)確性的基礎(chǔ)上，大幅度地增強(qiáng)算法的計(jì)算速度及其實(shí)時(shí)性.

5 結(jié)束語(yǔ)

傳統(tǒng)的信號(hào)稀疏分解主要是使用遍歷搜索整個(gè)冗余字典而帶來巨大的計(jì)算量，導(dǎo)致整個(gè)分解過程需要較長(zhǎng)時(shí)間.將DE算法引入MP算法中，提出了一種DE-MP算法，充分利用差分算法具有較快的收斂速度和較強(qiáng)的尋優(yōu)能力的特點(diǎn)，來優(yōu)化MP算法每一次尋找稀疏分解最優(yōu)原子的過程，從而大大提高M(jìn)P算法的收斂速度和增強(qiáng)其全局搜索能力.經(jīng)過仿真實(shí)驗(yàn)證明：DE-MP算法與傳統(tǒng)MP算法相比有效降低了算法的運(yùn)算量，也在一定程度上提高了算法的求解精度.

[1]崔曉.自訓(xùn)練過完備字典和稀疏表示的語(yǔ)音增強(qiáng)[J].現(xiàn)代電子技術(shù),2015,38(13):56-58.

[2]周亞同,張偉,楊瑞霞.一維非均勻采樣信號(hào)可變稀疏度傅里葉重建算法研究[J].微電子學(xué)與計(jì)算機(jī),2012,29(7):188-191.

[3]王樹朋,王文祥,李宏偉.基于雙字典集的信號(hào)稀疏分解算法[J].計(jì)算機(jī)應(yīng)用,2012,32(9):2512-2515.

[4]王菊,王朝暉,劉銀.基于PSO和LM 的信號(hào)稀疏分解快速算法[J].激光與紅外,2012,42(2): 227-230.

[5]方輝,袁志剛,尹忠科,等.用模擬退火實(shí)現(xiàn)基于MP的信號(hào)稀疏分解[J].鐵道學(xué)報(bào),2009,31(2):65-68.

[6]侯坤,易正俊,何榮花.信號(hào)稀疏分解的人工蜂群-MP 算法[J].計(jì)算機(jī)仿真,2012,29(11):247-250.

[7]Mairal J.,Bach F.,Ponce J.,et al.On-line learning for matrix factorization and sparse coding [J].Journal of Machine Learning Research,2010,11(1):19-60.

[8]ARTHUR P L,PHILIPOS C L.Voiced/unvoiced speech discrimination in noise using Gabor atomic decomposition[C].Proc of IEEEInternational Conference on Acoustics,Speech,and Signal Processing,2003: 820-828.

[9]畢志升,王甲海,印鑒.基于差分演化算法的軟子空間聚類[J].計(jì)算機(jī)學(xué)報(bào),2012,35(10):2116-2128.

[10]黃麟舒,察豪,李洪科,等.小型化高頻地波雷達(dá)的波形及解調(diào)研究[J].測(cè)控技術(shù),2014,33(4):23-26.

[11]高峰.改進(jìn)的Hilbert變換無線網(wǎng)絡(luò)信道鄰階均衡算法[J].科技通報(bào),2014,30(8):47-49.

[12]楊勝利.基于FFT的信號(hào)MP分解改進(jìn)算法研究[D].西南交通大學(xué),2010.

[13]張靜,方輝,王建英,等.基于GA和MP的信號(hào)稀疏分解算法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(29): 79-81.

[14]李越雷,張?zhí)祢U,黃銚,等.利用粒子群算法實(shí)現(xiàn)PPS信號(hào)的稀疏分解[J].計(jì)算機(jī)仿真,2010,27(2): 200-203.

[責(zé)任編輯：王軍]

Fast signal sparse decomposition based on differential evolution -MP

WANG Xuerui,ZHOU Yan

(College of Computer,Henan Institute of Engineering,Zhengzhou 451191,China)

To resolves the problem of traditional sparse decomposition algorithm,which cost a huge computational complexity and a long time for sparse decomposition,a matching pursuit (MP) algorithm based on differential evolution (DE) is proposed.The algorithm based on the advantage of DE algorithm which has strong robustness and good global convergence.In the algorithm,DE algorithm replaces the traversing search strategy of the traditional MP algorithm.It greatly reduces the algorithm complexity by optimizing the process of finding the best sparse decomposition atomic.Also the special search strategy of DE algorithm is good to improve the global convergence of the MP and the accuracy of the sparse decomposition.The simulation results of the radar simulation signal and the speech signal test show that,compared with traditional algorithms of MP,the DE-MP increased two orders of magnitude in computing speed and improved obviously on the convergence accuracy,what is more,the convergence accuracy is superior to the other improve algorithms.

signal sparse decomposition; matching pursuit; differential evolution; orthogonal matching

2015-12-10；

2016-01-07

國(guó)家自然科學(xué)基金資助項(xiàng)目(U1304608)

王雪瑞(1977-)，女，河南登封人，河南工程學(xué)院副教授，碩士，主要從事計(jì)算機(jī)應(yīng)用與圖像處理的研究.

TP301.6

A

1672-3600(2016)12-0045-05