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算法,还有待于更深入的研究。
参考文献