Interval-passing algorithm for non-negative measurement matrices: Performance and reconstruction analysis

Vida Ravanmehr, Ludovic Danjean, Bane Vasic, David Declercq

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


We consider the Interval-Passing Algorithm (IPA), an iterative reconstruction algorithm for reconstruction of non-negative sparse real-valued signals from noise-free measurements. We first generalize the IPA by relaxing the original constraint that the measurement matrix must be binary. The new algorithm operates on any non-negative sparse measurement matrix. We give a performance comparison of the generalized IPA with the reconstruction algorithms based on 1) linear programming and 2) verification decoding. Then we identify signals not recoverable by the IPA on a given measurement matrix, and show that these signals are related to stopping sets responsible to failures of iterative decoding algorithms on the binary erasure channel (BEC). Contrary to the results of the iterative decoding on the BEC, the smallest stopping set of a measurement matrix is not the smallest configuration on which the IPA fails. We analyze the recovery of sparse signals on subsets of stopping sets via the IPA and provide sufficient conditions on the exact recovery of sparse signals. Reconstruction performance of the IPA using the IEEE 802.16e LDPC codes as measurement matrices are given to show the effect of stopping sets in the performance of the IPA.

Original languageEnglish (US)
Article number6317120
Pages (from-to)424-432
Number of pages9
JournalIEEE Journal on Emerging and Selected Topics in Circuits and Systems
Issue number3
StatePublished - 2012


  • '

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Interval-passing algorithm for non-negative measurement matrices: Performance and reconstruction analysis'. Together they form a unique fingerprint.

Cite this