An Accelerated MMP With a Pruning Tree Strategy

Abstract

Multipath matching pursuit (MMP) has been developed to solve the sparse signal recovery problems in compressed sensing, which can generate recovery error less than the traditional orthogonal matching pursuit type algorithms in terms of mean square error. However, the computational burden of MMP is seriously heavy, and limits itself in applications, finding the need to be improved urgently. To lighten the burden, in this paper, an accelerated version of the MMP is proposed based on pruning tree strategy for sparse signal recovery, that attempts to reduce some of the paths in subsequent searching. By this strategy, an accelerated MMP is established in the scenarios where the MMP works. It retains the desirable performance as MMP and can shorten the running time. We demonstrate the acceleration ability of the proposed algorithm with almost the same accuracy of the original MMP, for the reconstruction of both synthetic data and images.

Keywords

• Compressed sensing
• multipath matching pursuit
• sparse recovery
• pruning tree strategy
• restricted isometry constant