Accelerating the convergence of message passing on loopy graphs using eigenmessages

We present the "\´eigenmessage algorithm" for accelerating the convergence of message passing algorithms used for decoding LDPC codes. In the eigenmessage step, elements of a message along a cycle of edges are expressed as a linear combination of that message itself, giving rise to an eigenequation whose solution - the eigenmessage - is equivalent to the fixed point of the closed loop message passing algorithm, where the other edges incident on the nodes in the cycle are held fixed. The decoding algorithm iterates among the eigenmessage steps for the cycles in the graph and conventional message passing for edges not in the cycles. The eigenmessage algorithm results in faster convergence (approximately 70 percent) without any compromise in error performance compared with conventional message passing algorithms.