Local Pseudo-Inverse Matching Pursuit of sparse overcomplete representations

In order to generate sparse representations of signals in a given overcomplete dictionary, a lot of optimal methods have been proposed. These methods are often based on convex relaxation or greedy search strategies. In general, convex relaxation methods have better preserved sparsity and superresolution than greedy methods, while greedy methods have lower computational complexity than convex relaxation methods. How to improve greedy methods and make them as good as convex relaxation methods is a long-term studied issue. We propose a Local Pseudo-Inverse Matching Pursuit (LPIMP) algorithm according to the mutual constraint property on the energy distribution of Method of Frame and Matching Pursuit and present LPIMP´s recovery condition. And then, based on local competitions, we improve LPIMP to make it have better preserved sparsity. Experiments show that LPIMP has better performance in preserved sparsity, superresolution and convergence than most of the existing algorithms, and break the limit of Tropp´s Exact Recovery Condition in a certain degree and is more practicable.