Forward sequential algorithms for best basis selection
Forward sequential algorithms for best basis selection
复制标题
DOI：
10.1049/ip-vis:19990445
复制
发表时间：
1999-10-01
期刊：
影响因子：
--
通讯作者：
Kreutz-Delgado, K
中科院分区：
文献类型：
--
作者：
Cotter, SF;Adler, J;Kreutz-Delgado, K
从一个大的，过完备的，跨越字典的基向量的信号表示的问题一直是许多研究的焦点。实现简洁或“稀疏”的表示被称为最佳基表示问题。方法被认为是寻求解决这个问题，依次建立一个基础的信号。在文献中出现了三种不同的算法类型，在这里被称为基本匹配追踪（BMP），顺序递归匹配追踪（ORMP）和修改的匹配追踪（MMP）。首先描述的算法，然后仔细检查他们的计算。对每个程序进行了修改，以提高其计算效率。每个算法的复杂性被认为是在两个上下文中;一个字典是可变的（时间相关的），另一个字典是固定的（时间无关的）。实验结果表明，ORMP方法是最好的程序，在其能力，以提供最紧凑的信号表示，其次是MMP，然后BMP，它给出了最差的结果。最后，权衡每个算法的性能，其计算复杂性和可用的字典的类型，建议应该使用哪种算法来解决给定的问题。
The problem of signal representation in terms of basis vectors from a large, overcomplete, spanning dictionary has been the focus of much research. Achieving a succinct, or 'sparse', representation is known as the problem of best basis representation. Methods are considered which seek to solve this problem by sequentially building up a basis set for the signal. Three distinct algorithm types have appeared in the literature which are here termed basic matching pursuit (BMP), order recursive matching pursuit (ORMP) and modified matching pursuit (MMP). The algorithms are first described and then their computation is closely examined. Modifications are made to each of the procedures which improve their computational efficiency. The complexity of each algorithm is considered in two contexts; one where the dictionary is variable (time-dependent) and the other where the dictionary is fixed (time-independent). Experimental results are presented which demonstrate that the ORMP method is the best procedure in terms of its ability to give the most compact signal representation, followed by MMP and then BMP which gives the poorest results. Finally, weighing the performance of each algorithm, its computational complexity and the type of dictionary available, recommendations are made as to which algorithm should be used for a given problem.