AuthorsY. Yakimenka and E. Rosnes
TitleOn failing sets of the interval-passing algorithm for compressed sensing
AfilliationCommunication Systems
Project(s)SARDS: Secure and Reliable Distributed Storage Systems
Publication TypeProceedings, refereed
Year of Publication2016
Conference Name54th Annual Allerton Conf. Commun., Control, and Computing
Date Published09/2016
PublisherIEEE Press

In this work, we analyze the failing sets of the interval-passing algorithm (IPA) for compressed sensing. The IPA is an efficient iterative algorithm for reconstructing a k-sparse nonnegative n-dimensional real signal x from a small number of linear measurements y. In particular, we show that the IPA fails to recover x from y if and only if it fails to recover a corresponding binary vector of the same support, and also that only positions of nonzero values in the measurement matrix are of importance for success of recovery. Based on this observation, we introduce termatiko sets and show that the IPA fails to fully recover x if and only if the support of x contains a nonempty termatiko set, thus giving a complete (graph-theoretic) description of the failing sets of the IPA. Finally, we present an extensive numerical study showing that in many cases there exist termatiko sets of size strictly smaller than the stopping distance of the binary measurement matrix; even as low as half the stopping distance in some cases.

Citation Key25102