TY - GEN
T1 - Algebraic optimization of binary spatially coupled measurement matrices for interval passing
AU - Habib, Salman
AU - Kliewer, Jörg
N1 - Publisher Copyright:
© 2018 IEEE Information Theory Workshop, ITW 2018. All rights reserved.
PY - 2018/7/2
Y1 - 2018/7/2
N2 - We consider binary spatially coupled (SC) low density measurement matrices for low complexity reconstruction of sparse signals via the interval passing algorithm (IPA). The IPA is known to fail due to the presence of harmful sub-structures in the Tanner graph of a binary sparse measurement matrix, so called termatiko sets. In this work we construct array-based (AB) SC sparse measurement matrices via algebraic lifts of graphs, such that the number of termatiko sets in the Tanner graph is minimized. To this end, we show for the column-weight-three case that the most critical termatiko sets can be removed by eliminating all length-12 cycles associated with the Tanner graph, via algebraic lifting. As a consequence, IPA-based reconstruction with SC measurement matrices is able to provide an almost error free reconstruction for significantly denser signal vectors compared to uncoupled AB LDPC measurement matrices.
AB - We consider binary spatially coupled (SC) low density measurement matrices for low complexity reconstruction of sparse signals via the interval passing algorithm (IPA). The IPA is known to fail due to the presence of harmful sub-structures in the Tanner graph of a binary sparse measurement matrix, so called termatiko sets. In this work we construct array-based (AB) SC sparse measurement matrices via algebraic lifts of graphs, such that the number of termatiko sets in the Tanner graph is minimized. To this end, we show for the column-weight-three case that the most critical termatiko sets can be removed by eliminating all length-12 cycles associated with the Tanner graph, via algebraic lifting. As a consequence, IPA-based reconstruction with SC measurement matrices is able to provide an almost error free reconstruction for significantly denser signal vectors compared to uncoupled AB LDPC measurement matrices.
UR - http://www.scopus.com/inward/record.url?scp=85062107169&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85062107169&partnerID=8YFLogxK
U2 - 10.1109/ITW.2018.8613339
DO - 10.1109/ITW.2018.8613339
M3 - Conference contribution
AN - SCOPUS:85062107169
T3 - 2018 IEEE Information Theory Workshop, ITW 2018
BT - 2018 IEEE Information Theory Workshop, ITW 2018
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2018 IEEE Information Theory Workshop, ITW 2018
Y2 - 25 November 2018 through 29 November 2018
ER -