Alternating direction method of multipliers (ADMM) is a popular technique for linear-programming (LP) decoding of low-density parity-check (LDPC) codes. The computational complexity of ADMM is dominated by the Euclidean projection of a real-valued vector onto a parity-check polytope. Existing algorithms for such a projection all require sorting operations, which happen to be the most complex part of the projection. In this letter, we propose an iterative algorithm, without sorting operation, for projection onto the parity-check polytope. The proposed algorithm has a worst case complexity linear in the input dimension compared to the super-linear complexity of existing algorithms.

Additional Metadata
Keywords Alternating direction method of multipliers (ADMM), check polytope projection, Complexity theory, Convex functions, Euclidean projection, Iterative algorithms, Iterative decoding, linear-programming (LP) decoding of LDPC codes, low-density parity-check (LDPC) codes, Projection algorithms, Sorting
Persistent URL dx.doi.org/10.1109/LCOMM.2017.2766223
Journal IEEE Communications Letters
Citation
Wei, H. (Haoyuan), & Banihashemi, A. (2017). An Iterative Check Polytope Projection Algorithm for ADMM-Based LP Decoding of LDPC Codes. IEEE Communications Letters. doi:10.1109/LCOMM.2017.2766223