Global searching in dictionary with single atom being selected in each iteration leads to greedy algorithms’ high complexity in sparse decomposition. Given this, we propose an improved matching pursuit (MP) algorithm named local dictionary searching and multi-atoms matching pursuit (LMMP).

Calculation showed that the order of kernel atoms in the adjacent generation of MP algorithm is basically stable, the best atom just to search in local dictionary consisting of the front order atoms. Searching for multiple incoherent atoms on single iteration to further improve the speed of MP algorithm. Reduce the approximation error by updating the residual image one by one atom in turn.

Theoretical analysis indicates that the LMMP algorithm is convergent and its time complexity is  several orders of magnitude lower than the MP. Experimental results show that the LMMP algorithm outperforms other global searching methods in computational speed and approximation performance.