Fast Sparse Signal Approximation Via Matching Pursuit

Matching pursuit (MP) is a fundamental technique for a sparse solution to underdetermined inverse problems and signal approximation with a long and multi-rooted history. However, conventional MP suffers from a slow convergence rate and has been considered still inefficient when applied to high-dimensional signals due to its single element selection and coefficient update pattern in each iteration. This paper proposed a new elements selection strategy and coefficients update scheme with the aim of providing a fast convergence speed and an accurate recovery for application of large scale problems. Instead of selecting a single element in each iterative step, the new algorithm efficiently chooses several elements that satisfy certain condition and update all the selected coefficients. Simulation studies show that the development of the new elements selection and coefficients update strategy can lead to a substantial acceleration and sharp convergence rate while keeps the algorithm with an accurate and robust recovery.