On the Fundamental Limit of Multipath Matching Pursuit

IEEE Multipath matching pursuit (MMP) is a recent extension of the orthogonal matching pursuit (OMP) algorithm that recovers sparse signals with a tree-searching strategy[1]. In this paper, we present a new analysis for the MMP algorithm using the restricted isometry property (RIP). Our result shows that if the sampling matrix formula > tex > $mathbf{A} in mathbb{R}^{m times n}$ /tex > /formula > satisfies the RIP of order formula > tex > $K + L$ /tex > /formula > with isometry constant formula > tex > $$delta_{K+L} & lt;sqrt{frac{L}{{K} + {L}}},$$ /tex > /formula > then MMP accurately recovers any $K$-sparse signal formula > tex > $mathbf{x} in mathbf{R}^n$ /tex > /formula > from the samples formula > tex > $mathbf{y}=mathbf{A}mathbf{x}$ /tex > /formula > , where formula > tex > $L$ /tex > /formula > is 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 formula > tex > $$delta_{K+L} = sqrt{frac{L}{{K} + {L}}}$$. /tex > /formula >