Improved RIP-based performance guarantees for multipath matching pursuit

The multipath matching pursuit (MMP) is a generalization of the orthogonal matching pursuit (OMP), which generates multiple child paths for every candidate in each iteration and selects the candidate having the minimal residual as the final support set when iteration ends. In this paper we analyze its performance in both noiseless and noisy cases. The restricted isometry property (RIP)-based condition of MMP that ensures accurate recovery of sparse signals in the noiseless case is derived by using a simple technique. The performance guarantees of the MMP for support recovery in noisy cases are also discussed. It is shown that under certain conditions on the RIP and minimum magnitude of nonzero components of the sparse signal, the MMP will exactly recover the true support of the sparse signal in cases of bounded noises and recover the true support with a high probability in the case of Gaussian noise. Our bounds on the RIP improve the existing results.