王雪瑞,周岩

(河南工程学院 计算机学院，河南 郑州 451191)



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

王雪瑞,周岩

(河南工程学院 计算机学院，河南 郑州 451191)

针对传统的稀疏分解算法存在的计算量大和耗费时间长的缺点，利用差分演化算法具有鲁棒性强和全局收敛性好的优点，提出了一种基于差分演化的匹配追踪算法(DE-MP).算法使用差分演化(DE)算法替换传统匹配追踪(MP)算法中的遍历搜索策略，优化了寻找稀疏分解最优原子的过程，从而大大降低了算法复杂度.此外，DE算法特殊的搜索策略很好地提高MP的全局收敛性，进一步提高了稀疏分解的准确性.通过对雷达仿真信号和语音信号仿真实验结果表明：与传统MP算法相比，差分演化匹配追踪算法(DE-MP)在计算速度提高了两个数量级，在收敛精度上也有明显提高，且收敛精度优于其他改进MP算法.

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

0 引 言

信号稀疏分解理论由于具有显著的自适应性，灵活性等优点，因此在信号处理领域的研究发展迅速起来，并在信号压缩、特征提取、去噪、超分辨重建等领域有着广泛的应用[1-2].然而常用稀疏分解算法运算量都十分巨大，这是因为在过完备字典中选择信号的最优逼近方式被证明是一个NP问题，而这也成为阻碍其在信号处理领域进一步发展的致命缺[3-4].国内外许多研究者针对现有的稀疏分解算法的缺点进行了深入的研究，方辉等人[5]提出了一种模拟退火MP算法，该算法使用模拟退火处理的方法选择原子，提高信号稀疏分解速度.侯坤等[6]人提出一种ABC-MP算法，利用人工蜂群算法寻找近似最佳原子.Mariral[7]提出自适应学习算法构造稀疏表示学习字典，对样本集学习出稀疏表示原子，能较好地匹配信号的结构特征，但计算复杂度仍然很大.为此，本文将DE算法引入MP算法中，提出了一种DE-MP算法，利用差分算法来优化MP算法每一次寻找稀疏分解最优原子的过程，从而大大提高MP算法的收敛速度和增强其全局搜索能力.改进后的算法结构简单，易操作，大幅度减少了计算的复杂度，并进一步提高了收敛精度.

1 信号稀疏分解描述

在实际生活中，信号都是由很多种信号混合而成的.这种混合信号很难在完备正交基中有效地表示出来的，并且完备正交基的表示过于复杂，不利于信号处理的识别和压缩等.因此，这些混合信号采用稀疏表示对其处理非常有利，并且过完备系统比正交基也在非线性逼近理论中得到了证明.

1.1 稀疏逼近的定义

假设集合D={gk;k=1,2,...,K}，K≥N，集合D又称为原字库，其中元素称为原子，则Hilbert(H=RN)空间中单位矢量可以由原字库中原子表示.选取信号y∈H，在D中选取m个原子对信号y做m项逼近，具体表示如下：

(1)

其中，Im是gγ的下标集，cγ是展开系数，则A=span(gγ,γ∈Im)就是由m个原子在库D中组成的最佳子集，gγ是由参数组γ定义的原子，且每个原子的长度和待分解的信号长度一致，近似误差为：

(2)

由于m远远小于空间的维数N，所以这种逼近也被称作稀疏逼近.原子库是冗余的，导致gγ不能线性独立，故信号有多种表示方法.对不同的表示方法进行选择时，必须在满足公式(2)中近似误差定义的基础上，选出分解系数最为稀疏的组合.

1.2 过完备原字库

长度为N的信号y，且y=H∈RN，H=RN是N维Hilbert空间.信号的稀疏表示过程中，基在其构造空间中非常的密，导致其不绝对正交，此时的基称为原子，这些基组成的集合称为过完备原子库.

采用文献[8]中过完备原子库的生成方法，具体生成公式如下所示：

(3)

其中，g(t)=e-πt2是高斯窗函数，γ=(s,u,w,φ)是产生原子的4个时频参数，s代表伸缩因子、u代表位移因子、w代表频率、φ代表相位[6].将这些参数进行离散化的方法为：

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

(4)

2 匹配追踪算法与差分演化算法

2.1 匹配追踪算法

匹配追踪(MP)算法原理是以贪婪算法为基础，采用不断逼近的方法求得信号的稀疏表示，具体的步骤如下：

首先在过完备原子库中匹配出与初始信号最为近似的原子gγ0，同时，gγ0要使公式(5)成立.

(5)

然后，再根据上式对信号进行匹配迭代，得出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的过程，都可看作是从原子库中取一个最优原子对原始信号进行重构的过程.这样经过n次迭代后，信号可以表示为如下的线性组合：

(9)

其中，Rny为n次分解后的误差值，该数值很小时，表明经特定数目n个过完备原子的线性组合已经很逼近原始信号了，而且n≪N，N为信号采样点数.

2.2 差分演化算法

差分演化(DE)是一种新兴的演化算法，算法中同样包含变异和、交叉和选择等操作[9].主要包括以下步骤：

1)种群初始.在定义域的范围内，随机产生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样本数值的融合交叉得到的，交叉规则如下：

(11)

其中，交叉概率PC∈[0,1]，用来控制变异样本数值对试验样本数值的替代概率，若小于PC，替代为试验样本，否则为原样本.

4)差分选择.比较Ui,m的目标函数值与Xi,m的目标函数值大小，选择较优者替换Xi,m.

5) 判断是否符合算法结束条件，不满足继续迭代，否则输出结果.

3 差分演化的分解策略

3.1 算法原理

由于传统MP算法进行信号稀疏分解时，实际上是使用遍历搜索的方法来寻找全局最优原子，即信号或信号残差需要和冗杂的原子库中的每一个原子做内积完成投影计算，而内积值计算是在一个高维空间上求解得到的，因此算法的计算复杂度非常高.本文利用分演化算法来替代MP算法中遍历搜索的方法寻找较优原子，进而减低算法的计算复杂度.

3.2 DE-MP算法流程

DE-MP算法的具体流程如下，其中差分演化算法找出最优原子的过程与标准差分演化算法一致.

1)MP算法初始化；

2)将原子参数编码.每个原子的4个参数作为算法中寻优样本的四维数值，适应度函数为待分解信号或者该信号残差和每个原子的投影内积值；

3)使用差分演化算法找出最优原子；

4)计算每个样本的适应值，即对应的投影内积值，求信号残差；

5)当达到了预设的残差阈值或算法迭代次数，就可以得到最优的结果，否则返回步骤2).这里使用迭代次数为终止条件.

4 仿真实验结果与分析

为了直观且定性地看出DE-MP算法的稀疏分解效果，将DE-MP算法分别进行了模拟雷达信号与语言信号两组测试.

4.1 模拟雷达信号仿真

实验采用长度N为128，由式(12)产生的模拟雷达信号，如图1所示.

图1 模拟雷达原始信号

图2 过完备

产生原子的4个时频参数γ=(s,u,w,φ)对应的个体范围最大值分别为N、N、2π、2π，最小值均为0.产生原子如图2所示.

使用上述的DE-MP算法对模拟信号进行仿真，相关参数如DE算法的种群规模Pop、迭代次数Loop、维度dim、尺度F、变异概率PC、形成过完备原子的4个参数最大值s,u,w,φ均按照表1设置.

表1 参数设置

算法的终止条件为稀疏分解得到的原子数M.

(12)

经过稀疏分解后得到的重建信号如图3所示.

图3 DE+MP重建信号

图4 语音原始信号

对比图1和图3可以看出由DE-MP算法稀疏分解重建的信号与原始信号十分接近.

4.2 语音信号仿真

采用Matlab自带的语音信号“bird.wav”进行仿真实验，选取第11000∶12023个信号采样点组成长度N为1024的音频信号，如图4所示.参数如表1所示设置.

采用DE-MP算法进行稀疏分解得到的语音重建如图5所示.

图5 DE-MP重建信号

对比图4和图5，可以看出由DE-MP算法稀疏分解重建的信号与原始信号并无多大区别.

4.3 实验分析

通过对模拟雷达信号和语言信号测试，可知DE-MP算法具有良好的稀疏分解效果[11].为了进一步验证DE-MP算法性能，采用传统MP算法和DE-MP算法进行对比，实验也采用语音信号“bird.wav”，选取第11000∶11256信号采样点组成长度N为256的音频信号，M=80，其他参数如表1所示设置.

为了准确地比较两种算法性能.采用信号的均方误差(MSE)，即原始信号和重建信号的误差为衡量标准，来定量的比较信号稀疏分解的重建效果，MSE计算公式如公式(13)所示:

(13)

经过稀疏分解以后得到的重建信号所计算的MSE值代表其与待处理的原始信号的表征程度，差异度越小即MSE值越小，说明算法的准确度越高，分解结果越好.表2为MP和DE-MP的测试结果.

表2 两种算法测试结果

由表2可知，本文算法与传统MP算法相比，时间复杂度有着显著下降，计算时间缩短了两个数量级，此外，在算法精度上也有一定程度提高.

为了进一步验证DE-MP算法的性能，选取了傅里叶变换匹配追踪算法(FFT-MP)[12]、遗传匹配追踪算法(GA-MP)[13]、粒子群算法追踪算法(PSO-MP)[14]进行对比实验，所有算法采用相同参数设置，如表1所示，得到的结果如表3所示，由于运行环境不一致无法进行时间测试，故只比价算法MSE值.

表3 4种改进算法结果对比

从表3看出，在与3种经典改进策略优化的匹配追踪算法相比时，DE-MP算法得到的MSE值最小，具有最高的计算精度.由此可见利用DE-MP算法，在准确度与计算速度之间取得良好平衡，在确保算法稀疏分解准确性的基础上，大幅度地增强算法的计算速度及其实时性.

5 结束语

传统的信号稀疏分解主要是使用遍历搜索整个冗余字典而带来巨大的计算量，导致整个分解过程需要较长时间.将DE算法引入MP算法中，提出了一种DE-MP算法，充分利用差分算法具有较快的收敛速度和较强的寻优能力的特点，来优化MP算法每一次寻找稀疏分解最优原子的过程，从而大大提高MP算法的收敛速度和增强其全局搜索能力.经过仿真实验证明：DE-MP算法与传统MP算法相比有效降低了算法的运算量，也在一定程度上提高了算法的求解精度.

[1]崔晓.自训练过完备字典和稀疏表示的语音增强[J].现代电子技术,2015,38(13):56-58.

[2]周亚同,张伟,杨瑞霞.一维非均匀采样信号可变稀疏度傅里叶重建算法研究[J].微电子学与计算机,2012,29(7):188-191.

[3]王树朋,王文祥,李宏伟.基于双字典集的信号稀疏分解算法[J].计算机应用,2012,32(9):2512-2515.

[4]王菊,王朝晖,刘银.基于PSO和LM 的信号稀疏分解快速算法[J].激光与红外,2012,42(2): 227-230.

[5]方辉,袁志刚,尹忠科,等.用模拟退火实现基于MP的信号稀疏分解[J].铁道学报,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].计算机学报,2012,35(10):2116-2128.

[10]黄麟舒,察豪,李洪科,等.小型化高频地波雷达的波形及解调研究[J].测控技术,2014,33(4):23-26.

[11]高峰.改进的Hilbert变换无线网络信道邻阶均衡算法[J].科技通报,2014,30(8):47-49.

[12]杨胜利.基于FFT的信号MP分解改进算法研究[D].西南交通大学,2010.

[13]张静,方辉,王建英,等.基于GA和MP的信号稀疏分解算法的改进[J].计算机工程与应用,2008,44(29): 79-81.

[14]李越雷,张天骐,黄铫,等.利用粒子群算法实现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

国家自然科学基金资助项目(U1304608)

王雪瑞(1977-)，女，河南登封人，河南工程学院副教授，硕士，主要从事计算机应用与图像处理的研究.

TP301.6

A

1672-3600(2016)12-0045-05