  In this work, we perform a complete failure analysis of the interval-passing
algorithm (IPA) for compressed sensing, an efficient iterative algorithm for
reconstructing a $k$-sparse nonnegative $n$-dimensional real signal
$\boldsymbol{x}$ from a small number of linear measurements $\boldsymbol{y}$.
In particular, we show that the IPA fails to recover $\boldsymbol{x}$ from
$\boldsymbol{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 to the success of recovery. Based on
this observation, we introduce termatiko sets and show that the IPA fails to
fully recover $\boldsymbol x$ if and only if the support of $\boldsymbol x$
contains a nonempty termatiko set, thus giving a complete (graph-theoretic)
description of the failing sets of the IPA. Two heuristics to locate small-size
termatiko sets are presented. For binary column-regular measurement matrices
with no $4$-cycles, we provide a lower bound on the termatiko distance, defined
as the smallest size of a nonempty termatiko set. For measurement matrices
constructed from the parity-check matrices of array LDPC codes, upper bounds on
the termatiko distance are provided for column-weight at most $7$, while for
column-weight $3$, the exact termatiko distance and its corresponding
multiplicity are provided. Next, we show that adding redundant rows to the
measurement matrix does not create new termatiko sets, but rather potentially
removes termatiko sets and thus improves performance. An algorithm is provided
to efficiently search for such redundant rows. Finally, we present numerical
results for different specific measurement matrices and also for
protograph-based ensembles of measurement matrices, as well as simulation
results of IPA performance, showing the influence of small-size termatiko sets.
