MP 算法概述
富爽
邸国辉高飞（黑龙江八一农垦大学，黑龙江大庆163319）引言在信号处理理论研究和工程应用中，信号分解是一个基础的问题，具有非常重要的意义，在信号处理与分析中起着很重要的作用，是一种常用、有效的分析手段。
传统的信号分解变换是将信号分解在一组完备的正交基上，而且这种变换必然是可逆的，如傅立叶变换，短时傅立叶变换，小波变换等。
然而这些变换方式却有着自身难以克服的缺点。
随着信号分解理论的发展，近年来信号的非正交分解引起研究者越来越多的兴趣。
为了实现对信号更加灵活、简洁和自适应的表示，在小波分析的基础上，
Mallat 和Zhang [1]提出了信号在过完备库上分解的思想，开创了信号稀疏分解这一信号分析的新方向。
目前，信号的稀疏分解已经发展了多种算法，如MP 、
基本跟踪(BP)算法、框架方法(MOF)和最佳正交基方法(BOB)等，其中M P 最为常用。
1MP 算法原理假定H 表示Hilbert 空间，定义H 中的原子库，且。
令信号，为了逼近f ，MP 首先从过完备原子库中选择最为匹配的一个原子，即满足。
这样信号f 可以分解为如下形式：，表示用原子，表示信号f 所产生的误差。
显然与是正交的，所以可以得到。
为了使得逼近误差的能量最小，必须选择使得最大。
在无穷维或高维的情况下，由于计算复杂度的限制，通常无法找到的极值,只可能选择在某种意义上的近似最佳原子，使得，其中α为优化因子，满足。
下一步对残差进行同样的步骤，得到，满足。
MP 算法是一个迭代过程，它通过不断地将信号残差投影到原子库中一个最匹配它的向量上，从而继续对它进行分解。
将上述分解过程一直执行到n 阶，
就可以得到：。
这样就获得f 在原子库D 中的n 阶逼近形式，而逼近误差记为R n f ，随着分解的进行误差能量呈逐渐衰减趋势。
MP 算法是收敛的，在不限制分解迭代次数的前提下，如果原子库是完备的，那
么分解式中原子向量的线性组合能够以任意精度逼近原始信号[2]。
2MP 算法改进MP 算法以其对信号灵活的自适应分解方式等优点，被迅速的应用与信号处理的多个领域。
但该算法在应用上仍存在瓶颈问题，主要是过为巨大的计算量。
因此国内外学者对其进行了各种改进。
近年来，高强等人提出了采用遗传算法，范虹等采用混合编码的遗传算法有效降低了M P 算法的计算量，但GA 存在早熟的问题；
李恒建等采用量子遗传优化来降低匹配追踪算法的计算量，而量子遗传算法本身的搜索速度较慢，此外，Silva 将遗传算法用于匹配追踪，提出了“进化追踪原子分解”
，并提出一种多字典原子分解实现方法，该方法存在字典存储量大的问题[3]；
西南交大的尹忠科教授对此提出了使用原子库划分的方法解决字典存储量大的问题，并针对计算量大的问题提出了使用FFT 快速算法，通过用互相关运算代替内积运算来加快运算速度，而且还利用蚁群算法实现快速寻找M atching Pursuit (M P)过程每一步的
最优原子,大大提高了信号稀疏分解的速度。
随着研究的不断深入，运算速度比传统的MP 算法得到了成百上千倍的提高，但是计算量大的问题仍然是MP 算法在应用方面的瓶颈问题，有待继续得到解决。
3M P 算法应用M P 算法对信号自适应的灵活表达是传统的傅立叶变化或小波变换所无法比拟的,因其效率和逐步求精的框架使它的发展和应用赢得了广泛的关注和重视，涉及的主要应用场合有：3.1视频编码和视频压缩，特别是运动图像的估计与补偿。
许多文献针对视频压缩与编码问题，提出了许多新的字典以及字典搜索算法，在低位率的视频编码压缩中取得了比较成功的应用。
这也是M P 算法形成不久后就得到实际应用的领域。
3.2图像表示、分析和编码。
MP 算法在图像处理领域的应用不断得到研究人员的重视。
人们不仅从数学上证明了图像信息表示的稀疏性，并在生物视觉的初级过程中找到了这种“过完备-稀疏”
表达的证据，从另一个方面推动了利用MP 算法对图像进行稀疏分解的研究进展。
3.3医学信号处理领域。
医学信号分析处理一直是信号处理中非常活跃的领域，M P 就被应用于其中，如EEG 信号的时频分析与压缩，
呼吸与心跳速率的分析检测等。
3.4语音与音频信号处理。
MP 的思想最初出现于统计数据处理与语音信号处理领域，在其完善的过程中也是以语音信号作为研究实例，如高分辨率的声音信号分析，自适应的音频分解。
高分辨率MP 就是为特征提取发展起来的。
3.5特征提取与目标识别领域。
1997年K .Wang 和D .M .Goblirsch 将随机匹配跟踪算法用于动态语音特征的提取，增强了语音识别的效果。
1999年P.Runkle 等人将其与连续的隐M arkov 模型结合起来进行多特征目标识别。
在模糊系统识
别和人脸识别中也有学者进行了研究。
3.6电磁信号处理。
1997年M .R.M cClure 和L .Carin 报道了匹配跟踪对电磁散射问题(Scatter-ing Problem )的处理。
最近，Pascal Vincent 和Yoshua 还将其用于机器学习问题的求解，并提出了内核匹配跟踪的概念；T .Sato 和Y .Tada 则把匹配跟踪算法引入到雷达图像信号增强和识别中[4]。
3.7地震信号处理。
MP 算法一经提出,便很
快被应用于地球物理的地震信号处理领域。
在
1996年应用MP 分解算法对压缩的地震信号进行Kirchhoff 偏移计算；在2003年独立多分辨率分析和MP 算法对计算量和数据进行统计与行分析；在2004年以Ricker 子波为原子对地震信号进行时频分解；在2005年采用Morlet 小波为原子对地震信号进行MP 分解等[5]。
4结论MP 的基本思想是基于信号的可分解和重构，通过在过完备的库中自适应地搜索匹配能够表达信号局部特征的时频原子，最终将信号表示
为时频原子的线性组合。
正是由于其基本理念的广泛性以及灵活的自适应性，自从匹配追踪算法首次被提出之后，便引起了各界学者的重视。
国内
外很多高校和科研机构对基于MP 的信号稀疏分解的理论和应用进行了大量的研究，通过各种方法对算法进行优化，以减少其计算量和存储量的
应用瓶颈问题，以及其在图像、视频、语音、特征提取与目标识别等方面的应用，取得了重大的成果。
同时也是由于其普遍的适用性，所以根据不同行业对信号的先验知识，才呈现出了MP 算法的多
样性和特殊性，出现了针对不同信号的原子类别，产生了旨在提高迭代计算速度和面对实际应用的各种快速算法。
但过为庞大的原子库和过为巨大的数据计算量仍然是急需解决的主要问题。
这些阻碍MP 实际应用的制约因素同时也确切地体现着MP 算法自适应的灵活特征。
相信随着科学技术的不断发展以及广大学者的深入研究，更为丰
富的现实世界的信息一定会促进MP 算法的进一步发展。
参考文献[1]Mallat S ,Zhang Z.Matching pursuit with
time -frequency dictionaries [J].IEEE Trans.Signal Process ,1993,41(12):3397～3421.[2]邵君.基于MP 的信号稀疏分解算法研究[D].西
南交通大学,2006.[3]缑水平,焦李成,张向荣,李阳阳.基于免疫克隆与核匹配追踪的快速图像目标识别[J].电子与信息学报,2008,30(5):1104-1108.
[4]张文耀.基于匹配跟踪的低位率语音编码研究[D].中国科学院研究生院(软件研究所),2002.[5]陈发宇,尚永生,杨长春.Matching Pursuit 方法
综述[J].地球物理学进展,2007,22(5):1466-1473.
作者简介：富爽(1982~),女,伊春,研究方向为信号与信息处理。
邸国辉(1979~),男,大庆,研究方向为信号与信息处理、图像传输与处理。
高飞(1982~),女,松原,研究方向为信号与信息处理。
责任编辑：于会兰摘要：MP 算法以其理念的广泛性和灵活的自适应性，提出后便迅速发展并在图像、视频、语音、特征提取与目标识别、医学、地震信号处理等
方面取得了广泛应用。
首先对MP 算法的原理进行了简单介绍，
然后总结了国内外学者对其进行的各种改进的方法及思路，介绍了MP 算法的国内外研究现状，最后总结了MP 算法在众多领域的广泛应用，并展望了其广阔的发展前景。
关键词：匹配追踪；稀疏分解；
信号处理－23－科技论坛。