Computer Science and Application
Vol.4 No.11(2014), Article ID:14430,5 pages
DOI:10.12677/CSA.2014.411039

Matching Pursuit Based on PSO and Atomic Property

Jian Qian, Yizhi Zhao, Zhiwei Zhuang

School of Communication Engineering, Hangzhou Dianzi University, Hangzhou

Email: 847580813@qq.com

Copyright © 2014 by authors and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

Received: Oct. 2nd, 2014; revised: Nov. 4th, 2014; accepted: Nov. 12th, 2014

ABSTRACT

As sparse representation of signals has excellent characteristics, it has been applied in several fields of signal processing. But it has a large scale of computing, which hinders its application in practical signal processing. Particle swarm optimization is simple to be realized, and the searching result is good. In this paper, Matching Pursuit is used to realize sparse representation of signals, and particle swarm optimization is used to effectively search the best atom in the process of MP. According to the property of atoms, the improved algorithm is optimized. At last, the simulation results demonstrate the feasibility of the new algorithm.

Keywords:Sparse Representation, Computation, Particle Swarm Optimization, Atomic Property

基于粒子群优化和原子特性的匹配追踪算法

钱  建,赵毅智,庄智威

杭州电子科技大学通信工程学院,杭州

Email: 847580813@qq.com

收稿日期:2014年10月2日;修回日期:2014年11月4日;录用日期:2014年11月12日

摘  要

由于信号稀疏表示的优良特性,已被用于信号处理很多领域,但计算量大阻碍了它在实际中的应用。粒子群优化算法简单,易于实现,且搜索效果好。论文采用匹配追踪(Matching Pursuit, MP)算法实现信号稀疏分解,利用粒子群优化算法搜索MP过程中的最优原子。根据原子特性,优化改进后的算法。仿真结果证明了新算法的可行性。

关键词

稀疏表示,计算量,粒子群优化,原子特性

1. 引言

Mallat和Zhang[1] 在小波分析的基础上,于1993年提出信号在过完备原子库上分解的思想。用来表示信号的基,可以通过信号在过完备库上的分解,根据信号本身的特点自适应的选取,得到信号的稀疏表示。由于信号的稀疏表示所具有的优良特性,使其在信号处理领域的研究得到了长足发展。但稀疏分解的计算十分复杂,导致实际应用到信号处理上变得困难。

粒子群优化算法(Particle Swarm Optimization, PSO) [2] 源于对鸟类捕食过程的研究,算法通过先初始化一个种群,然后通过不断迭代寻优,实现全局搜索。算法实现简单,需调整参数少,得到了广泛应用。

针对稀疏分解计算复杂问题,本文在MP算法进行信号稀疏分解过程中,用粒子群优化算法进行原子寻优,结合原子特性,有效克服了稀疏分解计算量大的问题。

2. 匹配追踪算法

匹配追踪算法[3] 是一种通过逐步迭代来获得信号稀疏表示的贪婪算法。假设表示希尔伯特空间,采样信号,长度为是信号进行稀疏分解的过完备库,是参数组的集合,且

MP算法首先从过完备库中选出与信号最匹配的原子,即内积值最大的原子。满足如下式子:

(1)

其中,与原子的内积。则信号可分解为如下形式:

(2)

上式中,为信号的投影,而是信号的投影之后的残余。然后对残余分量进行一样的分解,在进过次迭代后,可以得到:

(3)

其中,满足:

(4)

将上述分解一直持续下去,直到满足的阈值要求。经过步分解后,得到:

(5)

文献[3] 指出,信号满足有限长度条件时,的增大而成指数衰减至0。从而用少数的原子就可以对信号逼近表示:

(6)

至此,完成了对信号的稀疏表示。但匹配追踪算法所做的计算量非常大,在每次的匹配中都要进行一次全局搜索,经过多次迭代后,计算量将非常惊人。耗时长、计算量大的缺点严重阻碍了匹配追踪算法的广泛应用。

3. 粒子群优化算法

粒子群优化算法[4] -[6] 源于鸟类协同捕食行为的研究,其具体实现过程如下:

假设一个维的向量表示参与稀疏分解的原子。首先,初始化一组大小为的随机种群,那么种群中第个粒子的位置则为:,速度则为:,最大迭代次数设为,开始进行迭代循环。每一代种群中的各个粒子通过计算适应值函数都可以找到两个极值:一个是个体自身变化过程中的最优解;另一个是在当前全部个体极值中整个种群的最优解。对于第个粒子,其个体自身变化过程中的最优解可表示为;相应的,整个种群的最优解为。完成个体和种群的寻优后,利用下式更新每个粒子的速度和位置,从而得到新一代的粒子。

(7)

(8)

其中,分别表示第个粒子在第维上的速度分量和位置分量;为经过第次迭代更新后的相关参数;是学习因子,一般为0到1的随机数;为粒子的惯性权重系数,。文献[1] 中指出可用来控制过去速度对当前速度的影响,直接影响到粒子的全局和局部搜索能力。当较大时,全局寻优能力强,局部寻优能力弱;当较小时,局部寻优能力强,全局寻优能力弱。不断进行迭代更新后,可将群体极值所对应的粒子,作为MP算法的最匹配原子,经过多次搜索最优原子,最终完成信号的稀疏分解。

4. 原子特性

根据文献[2] 的方法,能产生一个用于稀疏分解的原子,如图1所示。从图中可以看出,该原子的能量几乎集中在原子中间,其余地方近似为零[2] 。这是个比较有代表性的原子,其它原子的能量可能更加集中,或者比它分散。原子的这种能量集中的特性,主要是因为形成原子的公式中都包含一个高斯窗函数,比如Gabor字典。

根据原子的这种结构特性[7] ,则可以简化式(4)的计算。因为内积的计算量随着信号长度的增加而迅速增加。但由于原子能量集中这种结构特性,则不需要按信号的长度来计算。假设信号能量集中区域的长度为,其它区域为零,那么只需正确确定能量集中区域,就可以使得在长度上的内积和在长度上的内积完全相等,从而达到有效降低计算量的目的。

5. 基于粒子群优化和原子特性的MP改进算法

由上文分析可知,MP算法中,过完备字典的产生和全局搜索是造成稀疏分解计算复杂且占用大量内存的主因。以Gabor字典[2] 为例,其原子生成函数为:

(9)

其中,是高斯窗函数,是尺度参数,是位移参数,是频率参数,是相位参数。表示时频参数。将这些参数离散化可得到Gabor原子库。离散方式为:,其中为信号长度。匹配追踪算法要遍历内积字典,选取内积最大的原子,因此搜索算法的计算量非常大。

粒子群优化算法实现简单,需调整的参数少,将匹配追踪的投影准则作为粒子群优化算法的适应度函数,并在投影准则中运用原子特性。仿真证明,改进后的算法能很快收敛到全局最优值,并有效减少计算量。把Gabor函数中的参数分别作为粒子搜索空间中的一维,在参数空间中进行搜索,这样就避免了在稀疏分解前生成过完备原子库,而仅仅只用种群中各参数向量代表原子。

6. 实验结果与分析

为了验证改进算法的可行性,通过软件仿真来检验其性能。实验中,待分解信号的长度为256,取值范围[0, 255],采样频率为800 Hz。粒子群优化算法的种群规模设为50个粒子,迭代次数100,惯性权重系数,并随着迭代次数线性递减,。仿真结果如图2所示。

图2中可以看出,本文提出的利用粒子群优化和原子特性对匹配追踪算法改进能完成对信号的重构,且重构效果良好,说明该算法的可行性得到验证。

图3图4分别为改进算法和MP算法在运行时间和信号重建概率上进行对比,对比结果都是在同一版本的Matlab软件和计算机上获得,不同的计算机可能获得的结果不一样。

图3可以看出,由于粒子群优化算法实现简单,所需调整的参数少,运行时间明显比MP算法低。

Figure 1. Atomic waveform

图1. 原子波形

Figure 2. Signal reconstruction of improved algorithm

图2. 改进算法信号重构图

Figure 3. Algorithm running time comparison

图3. 算法运行时间对比

Figure 4. Comparison of the two algorithms’ reconstruction probability

图4. 两种算法重建概率对比

MP算法因为信号或信号残差每一次都要完成和过完备库中最优原子的投影计算,导致了MP计算量庞大,运行时间长。从图4的对比中,可以看出在相同的采样点下,改进算法的信号重构概率高于MP算法,且信号重构概率最先接近1,即收敛速度快。

7. 结束语

根据上述分析和仿真结果得出,利用粒子群优化算法寻找最优原子和原子能量集中的特性,可有效克服MP算法计算复杂,难以在信号领域广泛应用的缺点。仿真结果表明,本文提出的改进算法的计算时间比匹配追踪算法有大幅降低,为MP算法在信号领域的运用提供了新的思路。但改进算法仍存在较多问题,如:在原子特性上仍不可避免地进行内积计算;与MP算法相比,在运行时间上虽提升180倍左右,但用于实际信号领域仍存在计算复杂的问题。因此,对于如何广泛应用MP算法,还有待于更深入的研究。

参考文献 (References)

  1. [1]   Shi, Y.H. and Eberhart, R.C. (1998) A modified particle swarm optimizer. IEEE International Conference on Evolutionary Computation, 4-9 May 1998, Anchorage, 69-73.

  2. [2]   Arthur, P.L. and Philips, C.L. (2003) Voiced/unvoiced speech discrimination in noise using Gabor atomic decomposition. Proceedings of IEEE ICASSP, Hong Kong, 820-828.

  3. [3]   Mallat, S. and Zhang Z. (1993) Matching pursuit with time-frequency dictionaries. IEEE Transactions on Signal Processing, 41, 3397-3415.

  4. [4]   Kennedy, J. and Eberhart, R. (2001) Swarm intelligence. Morgan Kaufmann Publishers, San Francisco.

  5. [5]   高鹰, 谢胜利 (2004) 免疫粒子群优化算法. 计算机工程与应用, 6, 47-50.

  6. [6]   高鹰, 谢胜利 (2004) 混沌粒子群优化算法. 计算机科学, 8, 13-15.

  7. [7]   尹忠科, 王建英 (2006) 由图像的稀疏分解重建图像的快速算法. 电子科技大学学报, 4, 448-449.

期刊菜单