4 May 2016 YAMPA: Yet Another Matching Pursuit Algorithm for compressive sensing
Author Affiliations +
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.
© (2016) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Muhammad A. Lodhi, Muhammad A. Lodhi, Sergey Voronin, Sergey Voronin, Waheed U. Bajwa, 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); doi: 10.1117/12.2224334; https://doi.org/10.1117/12.2224334
PROCEEDINGS
18 PAGES


SHARE
RELATED CONTENT

Lie EM ICP algorithm a novel frame for 2D...
Proceedings of SPIE (November 18 2012)
Sublinear constant multiplication algorithms
Proceedings of SPIE (August 24 2006)
Circulant preconditioners from B-splines
Proceedings of SPIE (October 23 1997)
Decomposition of quantics in sums of powers
Proceedings of SPIE (October 27 1994)

Back to Top