ﻻ يوجد ملخص باللغة العربية
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.
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
Modern image and video compression codes employ elaborate structures existing in such signals to encode them into few number of bits. Compressed sensing recovery algorithms on the other hand use such signals structures to recover them from few linear
Approximate message passing (AMP) is an efficient iterative signal recovery algorithm for compressed sensing (CS). For sensing matrices with independent and identically distributed (i.i.d.) Gaussian entries, the behavior of AMP can be asymptotically
We consider the problem of sparse signal recovery from 1-bit measurements. Due to the noise present in the acquisition and transmission process, some quantized bits may be flipped to their opposite states. These sign flips may result in severe perfor
Compressed sensing (CS) exploits the sparsity of a signal in order to integrate acquisition and compression. CS theory enables exact reconstruction of a sparse signal from relatively few linear measurements via a suitable nonlinear minimization proce