Forward sequential algorithms for best basis selection

The problem of signal representation in terms of basis vectors from a large , overcomplete, spanning dictionary has been the focus of much research. Ac hieving 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 disti nct algorithm types have appeared in the literature which are here termed b asic matching pursuit (BMP), order recursive matching pursuit (ORMP) and mo dified matching pursuit (MMP). The algorithms are first described and then their computation is closely examined. Modifications are made to each of th e procedures which improve their computational efficiency. The complexity o f each algorithm is considered in two contexts; one where the dictionary is variable (time-dependent) and the other where the dictionary is fixed (tim e-independent). Experimental results are presented which demonstrate that t he ORMP method is the best procedure in terms of its ability to give the mo st compact signal representation, followed by MMP and then BMP which gives the poorest results. Finally, weighing the performance of each algorithm, i ts computational complexity and the type of dictionary available, recommend ations are made as to which algorithm should be used for a given problem.