基于差分演化-MP的快速信號稀疏分解

王雪瑞,周巖

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

?

基于差分演化-MP的快速信號稀疏分解

王雪瑞,周巖

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

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

信號稀疏分解；匹配追蹤；差分演化算法；正交匹配

0 引 言

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

1 信號稀疏分解描述

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

1.1 稀疏逼近的定義

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

(1)

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

(2)

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

1.2 過完備原字庫

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

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

(3)

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

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

(4)

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

2.1 匹配追蹤算法

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

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

(5)

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

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

(6)

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

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

(7)

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

(8)

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

(9)

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

2.2 差分演化算法

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

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

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

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

(10)

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

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

(11)

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

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

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

3 差分演化的分解策略

3.1 算法原理

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

3.2 DE-MP算法流程

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

1)MP算法初始化；

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

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

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

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

4 仿真實驗結(jié)果與分析

為了直觀且定性地看出DE-MP算法的稀疏分解效果，將DE-MP算法分別進行了模擬雷達信號與語言信號兩組測試.

4.1 模擬雷達信號仿真

實驗采用長度N為128，由式(12)產(chǎn)生的模擬雷達信號，如圖1所示.

圖1 模擬雷達原始信號

圖2 過完備

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

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

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

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

(12)

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

圖3 DE+MP重建信號

圖4 語音原始信號

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

4.2 語音信號仿真

采用Matlab自帶的語音信號“bird.wav”進行仿真實驗，選取第11000∶12023個信號采樣點組成長度N為1024的音頻信號，如圖4所示.參數(shù)如表1所示設(shè)置.

采用DE-MP算法進行稀疏分解得到的語音重建如圖5所示.

圖5 DE-MP重建信號

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

4.3 實驗分析

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

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

(13)

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

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

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

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

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

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

5 結(jié)束語

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

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

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

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

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

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

[6]侯坤,易正俊,何榮花.信號稀疏分解的人工蜂群-MP 算法[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].計算機學(xué)報,2012,35(10):2116-2128.

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

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

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

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

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

[責任編輯：王軍]

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

國家自然科學(xué)基金資助項目(U1304608)

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

TP301.6

A

1672-3600(2016)12-0045-05