On the Fundamental Limit of Multipath Matching Pursuit

Multipath matching pursuit (MMP) is a recent extension of the orthogonal matching pursuit algorithm that recovers sparse signals with a tree-searching strategy. In this paper, we present a new analysis for the MMP algorithm using the restricted isometry property. Our result shows that if the sampling matrixA ∈ Rm × nsatisfies the RIP of order$K + L$with isometry constantδ K+L<√LK + Lthen the MMP accurately recovers anyK-sparse signalx ∈ Rⁿfrom the samplesy=Ax, whereLis the number of child paths for each candidate of the algorithm. Moreover, through a counterexample, we show that the proposed bound is optimal in that the MMP algorithm may fail underδ K+L = √LK + L.