Multiple Candidate Matching Pursuit

Seokbeop Kwon, Byonghyo ShimJournal of Broadcast Engineering 2012 · DOI

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.

Comparison of support set selection between OMP and MuCaMP over two iterations.

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.

Exact recovery ratio vs. sparsity level for various algorithms.

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

Abstract

Orthogonal matching pursuit (OMP) 알고리듬은 underdetermined 시스템에서 희소 신호를 복구하는 대표적인 greedy 알고리듬으로 많은 관심을 받고 있다. 본 논문에서는 OMP 알고리듬의 반복과정에서 후보 support 집합들을 구성하여 마지막 반복과정에서 최소 잔차를 이용하는 multiple candidate matching pursuit (MuCaMP) 기법을 제안한다. MuCaMP 가 완벽한 신호 복원을 보장하기 위한 restricted isometry property (RIP)를 이용한 충분조건, <TEX>${\delta}_{N+K}</TEX><TEX><</TEX><TEX>\frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$</TEX>을 제시한다. 실험을 통해 후보 support 집합들의 크기에 따른 성능과 MuCaMP의 복원 성능이 기존의 기법들에 비해 우수함을 확인하였다. As a greedy algorithm reconstructing the sparse signal from underdetermined system, orthogonal matching pursuit (OMP) algorithm has received much attention. In this paper, we multiple candidate matching pursuit (MuCaMP), which builds up candidate support set in every iteration and uses the minimum residual at last iteration. Using the restricted isometry property (RIP), we derive the sufficient condition for MuCaMP to recover the sparse signal exactly. The MuCaMP guarantees to reconstruct the K-sparse signal when the sensing matrix satisfies the RIP constant <TEX>${\delta}_{N+K}</TEX><TEX><</TEX><TEX>\frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$</TEX>. In addition, we show a recovery performance both noiseless and noisy measurements.
BibTeX
@article{kwon2012multiple,
  author = {Seokbeop Kwon and Byonghyo Shim},
  title = {{Multiple Candidate Matching Pursuit}},
  journal = {Journal of Broadcast Engineering},
  year = {2012},
  doi = {10.5909/jbe.2012.17.6.954},
}
Figure