Abstract Orthogonal matching pursuit (OMP) is a prominent greedy algorithm for reconstructing sparse signals in underdetermined systems. This paper introduces Multiple Candidate Matching Pursuit (MuCaMP), a novel technique that constructs multiple candidate support sets during each iteration and selects the one with the minimum residual at the final stage. We establish a sufficient condition for exact recovery using the Restricted Isometry Property (RIP): $\delta_{N+K} < \frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$, where $K$ is the sparsity level and $N$ is the number of candidates. Experimental results demonstrate that MuCaMP significantly outperforms existing greedy methods in terms of recovery performance across various sparsity levels and noise conditions.
Introduction
In the field of Compressive Sensing (CS), the goal is to recover a sparse signal—one where most entries are zero—from a limited number of linear measurements. Because there are more unknowns than equations, this is an underdetermined problem that requires specialized algorithms to solve.
Traditionally, researchers have relied on two main approaches: $\ell_1$-minimization and greedy algorithms. While $\ell_1$-minimization offers high accuracy, it is computationally intensive for large-scale applications. Conversely, greedy algorithms like Orthogonal Matching Pursuit (OMP) are fast and simple but suffer from a lack of robustness. If OMP selects an incorrect index (support) in an early iteration, that error propagates, often leading to a complete failure of the signal reconstruction. MuCaMP is designed to bridge this gap, offering the speed of greedy methods with the reliability of more complex optimization techniques.
The MuCaMP Algorithm
The fundamental innovation of MuCaMP is its transition from a single-path search to a multiple-candidate branching search. In standard OMP, the algorithm identifies the single column of the sensing matrix most correlated with the current residual at each step. MuCaMP, however, identifies the top $N$ most correlated columns.
As shown in the figure above, this creates a tree-like structure of potential support sets. To manage computational complexity and prevent an exponential explosion of candidates, the algorithm limits the search to a maximum number of candidate sets ($L$). In each iteration, existing sets are expanded, and the final selection is based on which candidate set yields the minimum residual—the best fit for the observed data. This "maybe" approach allows the algorithm to recover from early selection errors that would typically derail standard OMP.
Theoretical Guarantees
A critical contribution of this research is the derivation of a new sufficient condition for exact recovery using the Restricted Isometry Property (RIP). The authors prove that MuCaMP will perfectly reconstruct a $K$-sparse signal if the sensing matrix satisfies the following RIP constant condition:
$$\delta_{N+K} < \frac{\sqrt{N}}{\sqrt{K} + 3\sqrt{N}}$$
This theoretical bound suggests that as the number of candidates ($N$) increases, the requirements on the sensing matrix become more relaxed. This provides a mathematical foundation for why maintaining multiple candidates improves the probability of successful recovery.
Experimental Evaluation
The researchers evaluated MuCaMP using synthetic datasets, comparing it against $\ell_1$-minimization, OMP, Stagewise OMP (StOMP), and Compressive Sampling Matching Pursuit (CoSaMP). The simulations utilized $100 \times 256$ Gaussian sensing matrices and $K$-sparse signals.
As illustrated in the performance plot, MuCaMP (represented by the red lines) maintains a 100% exact recovery ratio at much higher sparsity levels than its counterparts. While standard OMP begins to fail when the sparsity $K$ exceeds 12, MuCaMP (with $N=4$) remains reliable up to $K \approx 24$. Furthermore, in noisy environments, MuCaMP consistently demonstrated a lower Mean Square Error (MSE) than other advanced greedy methods, particularly as the Signal-to-Noise Ratio (SNR) improved.
Conclusion
Multiple Candidate Matching Pursuit (MuCaMP) offers a significant advancement in greedy sparse signal recovery. By maintaining multiple candidate paths, it avoids the "fragility" of traditional OMP while remaining more computationally efficient than global optimization methods. While the algorithm introduces some overhead in managing multiple support sets, the gains in recovery threshold and noise robustness make it a compelling choice for practical Compressive Sensing applications. Future research may focus on adaptive parameter tuning to further optimize the balance between speed and accuracy in real-world scenarios like medical imaging or radar processing.
Summary updated