TY - JOUR
T1 - Interval-passing algorithm for non-negative measurement matrices
T2 - Performance and reconstruction analysis
AU - Ravanmehr, Vida
AU - Danjean, Ludovic
AU - Vasic, Bane
AU - Declercq, David
N1 - Funding Information:
Manuscript received March 01, 2012; revised August 03, 2012; accepted September 02, 2012. Date of publication October 02, 2012; date of current version December 05, 2012. This work is supported by DARPA Knowledge Enhanced Compressive Measurements Project (KECoM) under Contract N66001-10-1-4079 and by the National Science Foundation (NSF) under Grant CCF-0830245 and Grant CCF-0963726. This work was presented in part at the 7th International Symposium on Turbo-Codes and Iterative Processing, Gothenburg, Sweden, August 2012. This paper was recommended by Guest Editor G. Setti.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
KW - '
UR - http://www.scopus.com/inward/record.url?scp=84871016333&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84871016333&partnerID=8YFLogxK
U2 - 10.1109/JETCAS.2012.2218512
DO - 10.1109/JETCAS.2012.2218512
M3 - Article
AN - SCOPUS:84871016333
SN - 2156-3357
VL - 2
SP - 424
EP - 432
JO - IEEE Journal on Emerging and Selected Topics in Circuits and Systems
JF - IEEE Journal on Emerging and Selected Topics in Circuits and Systems
IS - 3
M1 - 6317120
ER -