Multipath Matching Pursuit

Suhyuk Kwon, Jian Wang, Byonghyo Shim

Abstract

Multipath Matching Pursuit (MMP) is a greedy algorithm designed for sparse signal recovery that mitigates the error propagation inherent in standard Orthogonal Matching Pursuit (OMP). By conceptualizing sparse recovery as a combinatorial tree search and branching into multiple promising directions at each iteration, MMP achieves significantly enhanced recovery performance and stronger theoretical guarantees. This paper details the breadth-first (MMP-BF) and depth-first (MMP-DF) variants, demonstrating their robustness in noisy environments and computational efficiency.

Introduction

Compressive Sensing (CS) aims to reconstruct a sparse signal $x$ from limited linear measurements $y = \Phi x$. While $\ell_1$-minimization techniques like Basis Pursuit offer high accuracy, their computational cost is often prohibitive. Conversely, greedy algorithms such as Orthogonal Matching Pursuit (OMP) are computationally efficient but lack robustness; a single incorrect index selection in early iterations can lead to total reconstruction failure due to error propagation. MMP addresses this by exploring multiple candidate "paths" in a tree-like structure, ensuring that the true support set remains within the search space.

Methodology

MMP transforms the greedy selection process into a structured tree search. The algorithm exists in two primary forms:

MMP-BF (Breadth-First)

In each iteration, every existing candidate path branches into $L$ new child paths. These children are generated by selecting the $L$ indices most correlated with the current residual. To maintain computational feasibility, the algorithm merges paths that converge on identical support sets.

Comparison of OMP (single path) and MMP (tree search) iterations.

MMP-DF (Depth-First)

To further optimize computational overhead, MMP-DF explores paths serially. It utilizes a "modulo strategy"—a clever indexing scheme—to diversify the search across different tree branches early on. The search terminates when a maximum number of candidates ($N_{max}$) is reached or the residual falls below a predefined threshold.

Theoretical Insights

The robustness of MMP is supported by a rigorous analysis using the Restricted Isometry Property (RIP). A key finding is that for a branching factor $L=K$, MMP is guaranteed to succeed if the RIP constant $\delta_{2K} < 0.33$. This condition is significantly more relaxed than those required by other state-of-the-art greedy algorithms like CoSaMP ($\delta_{4K} < 0.1$) or Subspace Pursuit, making MMP applicable to a wider range of sensing matrices.

Experimental Results

Evaluations using synthetic Gaussian sensing matrices and sparse signals demonstrate MMP's superiority over traditional methods.

Recovery Accuracy and Noise Robustness

In noiseless scenarios, MMP exhibits a higher "critical sparsity" compared to OMP, StOMP, and CoSaMP. In noisy environments (e.g., $K=20$ with AWGN), MMP achieves a Mean Squared Error (MSE) that approaches the "Oracle LS estimator"—the theoretical limit where the signal support is known a priori.

Computational Efficiency

While branching increases the search space, the depth-first approach (MMP-DF) maintains high accuracy while drastically reducing the number of candidates compared to an exhaustive search or even the breadth-first variant as sparsity $K$ increases.

Computational complexity comparison: Number of candidates vs. sparsity K for different search strategies.

Conclusion

Multipath Matching Pursuit provides a robust framework for sparse signal recovery by leveraging tree-search strategies. By relaxing RIP requirements and offering a computationally efficient depth-first variant, MMP bridges the gap between simple greedy methods and complex optimization-based recovery. Future work may involve advanced tree pruning techniques and hybrid strategies to further optimize the trade-off between latency and reconstruction accuracy.

Summary updated

BibTeX
@article{kwon2014multipath,
  author = {Suhyuk Kwon and Jian Wang and Byonghyo Shim},
  title = {{Multipath Matching Pursuit}},
  journal = {IEEE Trans. Information Theory},
  year = {2014},
  url = {https://openreview.net/forum?id=vWE7F4OlYW},
}
Figure