YAMPA: Yet Another Matching Pursuit Algorithm for compressive sensing

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

doi:10.1117/12.2224334

4 May 2016 YAMPA: Yet Another Matching Pursuit Algorithm for compressive sensing

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

Proceedings Volume 9857, Compressive Sensing V: From Diverse Modalities to Big Data Analytics; 98570E (2016) https://doi.org/10.1117/12.2224334
Event: SPIE Commercial + Scientific Sensing and Imaging, 2016, Baltimore, MD, United States

Abstract

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.

Citation Download Citation

Muhammad A. Lodhi, Sergey Voronin, and Waheed U. Bajwa "YAMPA: Yet Another Matching Pursuit Algorithm for compressive sensing", Proc. SPIE 9857, Compressive Sensing V: From Diverse Modalities to Big Data Analytics, 98570E (4 May 2016); https://doi.org/10.1117/12.2224334

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available