YAMPA: Yet Another Matching Pursuit Algorithm for compressive sensing

Muhammad A. Lodhi, Sergey Voronin, Waheed U. Bajwa

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations


State-of-the-art sparse recovery methods often rely on the restricted isometry property for their theoretical guarantees. However, they cannot explicitly incorporate metrics such as restricted isometry constants within their recovery procedures due to the computational intractability of calculating such metrics. This paper formulates an iterative algorithm, termed yet another matching pursuit algorithm (YAMPA), for recovery of sparse signals from compressive measurements. YAMPA differs from other pursuit algorithms in that: (i) it adapts to the measurement matrix using a threshold that is explicitly dependent on two computable coherence metrics of the matrix, and (ii) it does not require knowledge of the signal sparsity. Performance comparisons of YAMPA against other matching pursuit and approximate message passing algorithms are made for several types of measurement matrices. These results show that while state-of-the-art approximate message passing algorithms outperform other algorithms (including YAMPA) in the case of well-conditioned random matrices, they completely break down in the case of ill-conditioned measurement matrices. On the other hand, YAMPA and comparable pursuit algorithms not only result in reasonable performance for well-conditioned matrices, but their performance also degrades gracefully for ill-conditioned matrices. The paper also shows that YAMPA uniformly outperforms other pursuit algorithms for the case of thresholding parameters chosen in a clairvoyant fashion. Further, when combined with a simple and fast technique for selecting thresholding parameters in the case of ill-conditioned matrices, YAMPA outperforms other pursuit algorithms in the regime of low undersampling, although some of these algorithms can outperform YAMPA in the regime of high undersampling in this setting.

Original languageEnglish (US)
Title of host publicationCompressive Sensing V
Subtitle of host publicationFrom Diverse Modalities to Big Data Analytics
EditorsFauzia Ahmad
ISBN (Electronic)9781510600980
StatePublished - 2016
EventCompressive Sensing V: From Diverse Modalities to Big Data Analytics - Baltimore, United States
Duration: Apr 20 2016Apr 21 2016

Publication series

NameProceedings of SPIE - The International Society for Optical Engineering
ISSN (Print)0277-786X
ISSN (Electronic)1996-756X


OtherCompressive Sensing V: From Diverse Modalities to Big Data Analytics
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Electronic, Optical and Magnetic Materials
  • Condensed Matter Physics
  • Computer Science Applications
  • Applied Mathematics
  • Electrical and Electronic Engineering


Dive into the research topics of 'YAMPA: Yet Another Matching Pursuit Algorithm for compressive sensing'. Together they form a unique fingerprint.

Cite this