改进的基于树型搜索的正交匹配追踪算法

Modified Tree-Search Based Orthogonal Matching Pursuit Algorithm

正交匹配追踪算法(OMP)是一种利用一个超完备的字典进行信号分解的非线性自适应算法.文献[2]提出了基于树型搜索的正交匹配追踪算法(TB-OMP),尽管TB-OMP算法能够改进向量的逼近性能,但使计算的复杂度成指数倍的增加,严重限制了该算法在许多领域里的应用.在本文中将介绍一种灵活的基于树型搜索的正交匹配追踪算法(FTB-OMP)[5],算法通过设置参数,能够在算法逼近性能和计算复杂度之间找到一个灵活的折衷方案.

The orthogonal matching pursuit(OMP) algorithm is an adaptive nonlinear Algorithm for signal decomposition using an over complete dictionary.In [1],a tree-search based orthogonal matching pursuit(TB-OMP) is proposed.Although the TB-OMP algorithm improves the approximation performance,its computation time requirement increases exponentially making the algorithm impractical for certain applications.In this paper,we propose the flexible tree-search based orthogonal matching pursuit(FTB-OMP).The algorithm provides design parameters that give flexibility to establish a tradeoff between approximation performance and experimental time complexity.