A Unified Framework for Linear-Programming Based Communication Receivers
It is shown that a large class of communication systems which admit a Sum-Product Algorithm (SPA) based receiver also admit a corresponding Linear-Programming (LP) based receiver. The two receivers have a relationship defined by the local structure of the underlying graphical model, and are inhibited by the same phenomenon, which the authors call pseudo-configurations. This concept is a generalization of the concept of pseudo-codewords for linear codes. It is proved that the LP receiver has the 'maximum likelihood certificate' property, and that the receiver output is the lowest cost pseudo-configuration. Equivalence of graph-cover pseudo-configurations and linear-programming pseudo-configurations is also proved.