基于互相关运算的信号稀疏分解算法研究

姚建峰 郭旭展

摘要：分析了MP算法实现过程，并针对MP算法计算量大等问题，提出了一种信号稀疏分解的快速算法，它利用一种基于互相关运算的信号稀疏分解算法。该算法用互相关运算来代替MP算法中耗时最多的内积运算，并通过提高互相关运算的速度，提高信号稀疏分解的速度。通过实验表明，在保证稀疏分解精度的情况下，可以将信号稀疏分解速度提高到MP算法的10倍以上。

关键词：稀疏分解;MP算法;互相关运算

中图分类号：G642.0     文献标志码：A     文章编号：1674-9324（2015）24-0183-02

对信号进行处理时，一般先要对信号进行分解或变换，传统方法将信号在一组正交基上进行分解。正交基分解的不足之处是信号表示是唯一的，如果待分解信号的特征与正交基不完全相同时，分解后的信号就不能较稀疏地表示出原信号。用稀疏逼近取代原始信号可以降低信号处理的成本，提高压缩效率。目前，信号稀疏表示主要使用的算法是Mallat等人提出的匹配跟踪算法（Matching Pursuit，MP算法）。MP算法在计算复杂度和逼近效果方面要优于其他算法，但是MP算法每一步都要计算残余信号在完备元子库中每一个原子上的投影，因此计算量非常大。笔者在文中提出一种信号稀疏分解算法，该算法将MP算法中耗时最多的内积运算转换成一次互相关运算，此外，通过提高互相关运算的速度来提高信号稀疏分解的速度，可以缩短信号分解的时间。

一、信号的表示

一组线性独立的矢量φ={φ1}1∈T组成基，它能张开整个空间。任意一个在空间中的矢量S，可以通过线性组合来展开。

s在基矢量φ1上的展开系数是αi=〈s，φi〉。因为基具有独立性，所以它是唯一的一种展开方式。如果φi⊥φj，i≠j，则基？鬃为空间S的一组正交基。式（1.1）可转化成如下矩阵：

基矢量组成φ∈RM×N矩阵。如果N

信号也是采用一组矢量{ti}    来进行表示的。给定信号f∈RN，通过基矢量{ti}    的线性组合展开。f在基矢量ti上的展开系数是f=∑    αiti=Tα，αi=〈f，ti〉，T为合成矩阵。目前常用的基有余弦基、傅里叶基和小波基，这些基对应的合成矢量形成完备正交基。采用超完备的冗余基函数代替正交基函数来使表示形式多样化。此时，基矢量ti组成一个超完备集{ti}    ，且N

给定f和D，式（1.3）是一个欠定问题，有无穷多个解α，因此信号的稀疏表示是可行的。

二、MP算法

MP算法通过迭代方式从超完备元子库中选出与信号或者是残余信号最匹配的原子，从而将信号表示为这些原子的线性组合，实现信号的稀疏分解。设D={gm}0≤m

由于g0与R1s正交，因此：

为了极小化||R1s||，即让残余能量最小化，必须选定原子g0，使|<g0，R0s>|最大化。

用同样的方法，得到：

经过M次迭代后，信号s可以表示为：

其中RMs为M项近似残差，并且满足：

三、一种基于互相关的快速匹配算法

（一）算法思想

在信号稀疏表示中，一般使用Gabor原子库。一个Gabor原子由尺度因子s、原子频率v、原子相位w和位移因子u共同决定，且s、v、w三个参数决定原子形状，u只是决定原子的中心位置。如果对超完备原子库中的某一个原子gi（参数为si、vi、wi）的选取方法保持不变，信号长度为N，取u=N/2，通过平移就可以得到参数为（参数为si、vi、wi、ui）的原子（ui≠N/2）。为了不影响信号稀疏分解的效果，尽量使ui的值在区间[0，N-1]上。这相当扩大了元子库中原子的数目。由于ui从0到N-1连续取值，所有的N次内积运算<Rks，gk>都可以转化成两个列向量Rks和gk的一次互相关运算。内积运算的过程实际上是找互相关运算最大值的过程。如果提高了互相关运算的速度，就提高了信号稀疏分解的速度。

（二）算法描述

对两列长为N的数字信号，其互相关函数为：

两列数字信号在互相关运算的结果附近存在着一个明显的峰值特征，为了快速求出互相关运算的最大值，可以间隔一定距离进行互相关运算，确定最大值出现的区间，然后再在这个区间内进行相关运算，求出最大值和最大值点所在的位置。

假设每次间隔m个点进行计算，式3.1可表达为：

将得到的+1个点互相关运算的值进行比较，找出最大值（此最大值可能不是实际的最大值）。根据峰值特性，最大值点应在区间[m-1，m+1]上。如果N比较大，改进后互相关运算的计算量是原互相关运算的计算量的1/m。改进后互相关流程如图1。

四、实验结果与仿真

利用Matlab进行算法仿真，取不同长度的信号和步进点数进行互相关运算，求得的最大值与MP算法求得的内积最大值的誤差，算法速度与MP算法速度的比值。从实验结果可以看出，当步进点数为2、4时，误差很小，当步进点数大于或等于6时，误差开始变大。因此，在实际运用中，步进点数不能太大，即使步进点数为1，互相关算法比MP算法的速度要快。

本文针对信号稀疏分解中计算量大、分解速度缓慢等问题，提出了一种信号稀疏分解的快速算法。它利用一种互相关的快速运算来代替稀疏分解中计算量巨大的内积运算，提高了运算速度。通过理论仿真和实验表明，在保证稀疏精度的情况下，可以将信号稀疏分解的速度提高至普通MP算法速度的10倍以上。

参考文献：

[1]张春梅，尹忠科，肖明霞.基于冗余字典的信号超完备表示与稀疏分解[J].科学通报，2006，（6）：628-633.

[2]何虹丽，嵇银辉，等.基于差分进化算法的交通图像稀疏分解[J].电子元器件应用，2011，（3）：35-37.

[3]余付平，冯有前，等.基于稀疏分解的雷达信号抗噪声干扰方法研究[J].系统工程与电子技术，2011，（8）：1775-1769.