New Iterative Inference Algorithms for Source Coding based on Markov Random Fields
New Iterative Inference Algorithms For Source Coding Based On Markov Random FieldsJose M. Fernandez, Ph.D.Director: Phillip Regalia, Ph.D.The global deployment of wireless communication systems poses significant challenges for system designers which have to accommodate an ever-increasing number of users while simultaneously meet demands for increased levels of security and privacy. Many of these problems involve aspects of lossy source coding that are yet to be well understood. For instance, the nature and combined effectiveness of sparse graphs and message-passing algorithms in source coding continues to be the subject of debate and active research. This is in stark contrast to the channel coding case where specific capacity-approaching codes (i.e. Turbo Codes, Low-Density Parity Check Codes, etc.) and classical message-passing schemes (i.e. Belief Propagation) are clearly understood, widely accepted, and increasingly in use. Furthermore, the emergence of cavity methods drawn from statistical physics (i.e. Survey Propagation) gave rise to the widespread assumption that the source coding problem could not be solved by simple Belief Propagation-based iterations over Markov Random Fields. This notion is challenged heretofore by the introduction of two novel message-passing algorithms. These two simple schemes, namely Truthiness Propagation and Modified Truthiness Propagation, are developed based upon modified Bethe free energy approximations (equivalent to log-partition function approximations) and shown to be closely related to Belief Propagation, thus situating them on firm theoretical ground. The new algorithms exhibit rate-distortion performance near the Shannon limit even for modest codeword lengths when combined with both regular and irregular Low-Density Generator Matrix Codes. This feature offers a distinct advantage not seen with other message-passing schemes. Furthermore, their complexity is manageable since the decimation steps prevalent in other recently proposed techniques are not required. Finally, these modified instantiations of Belief Propagation are applied to a number of applications relevant to the codeword quantization problem (i.e. general decoding problem) via simple examples in dirty paper coding, data hiding, secrecy coding, and wireless sensor networks.
StatsViewed 30 times
Downloaded 2 times