Multipath matching pursuit

Suhyuk Kwon, Jian Wang, Byonghyo Shim

Research output: Contribution to journalArticlepeer-review

152 Citations (Scopus)


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.

Original languageEnglish
Article number6762942
Pages (from-to)2986-3001
Number of pages16
JournalIEEE Transactions on Information Theory
Issue number5
Publication statusPublished - 2014 May


  • Compressive sensing (CS)
  • Oracle estimator
  • greedy algorithm
  • orthogonal matching pursuit
  • restricted isometry property (RIP)
  • sparse signal recovery

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Multipath matching pursuit'. Together they form a unique fingerprint.

Cite this