In this paper, we propose a new sparse recovery algorithm referred to as the matching pursuit with a tree pruning (TMP) that performs efficient combinatoric search with the aid of greedy tree pruning. Two key ingredients of the TMP algorithm are pre-selection to put a restriction on the indices of columns in Φ being investigated and tree pruning to avoid the investigation of unpromising paths in the search. In the noisy setting, we show that TMP identifies the support (index set of nonzero elements) accurately when the signal power is larger than the constant multiple of noise power. In the empirical simulations, we confirm this results by showing that TMP performs close to an ideal estimator (often called Oracle estimate) for high signal-to-noise ratio (SNR) regime.

In this paper, we propose an algorithm referred to as multipath matching pursuit (MMP) that investigates multiple promising candidates to recover sparse signals from compressed measurements. Our method is inspired by the fact that the problem to find the candidate that minimizes the residual is readily modeled as a combinatoric tree search problem and the greedy search strategy is a good fit for solving this problem. In the empirical results as well as the restricted isometry property-based performance guarantee, we show that the proposed MMP algorithm is effective in reconstructing original sparse signals for both noiseless and noisy scenarios.

In this paper, we propose a sparse recovery algorithm, termed multiple path matching pursuit (MMP), that improves the recovery performance of sparse signals. By investigating the multiple paths and then choosing the most promising path in the final moment, the MMP algorithm improves the chance of finding the true support and therefore enhances the recovery performance. From the restricted isometry property (RIP) analysis, we show that the MMP algorithm can perfectly reconstruct any K-sparse (K >1) signals,√provided that the sensing matrix satisfies RIP with δK+L< √ L/√ K +3√ L. We demonstrate by empirical simulations that the MMP algorithm is very competitive in both noisy and noiseless scenarios.