2013/07/19 by Vahid Aref, Aref, Vahid, Nicolas Macris +3
Computer Science · Engineering · #Cellular Automata and Applications #Error Correcting Code Techniques #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.1307.5210
openalex publication_date 2013/07/19 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28
We investigate an encoding scheme for lossy compression of a binary symmetric\nsource based on simple spatially coupled Low-Density Generator-Matrix codes.\nThe degree of the check nodes is regular and the one of code-bits is Poisson\ndistributed with an average depending on the compression rate. The performance\nof a low complexity Belief Propagation Guided Decimation algorithm is\nexcellent. The algorithmic rate-distortion curve approaches the optimal curve\nof the ensemble as the width of the coupling window grows. Moreover, as the\ncheck degree grows both curves approach the ultimate Shannon rate-distortion\nlimit. The Belief Propagation Guided Decimation encoder is based on the\nposterior measure of a binary symmetric test-channel. This measure can be\ninterpreted as a random Gibbs measure at a "temperature" directly related to\nthe "noise level of the test-channel". We investigate the links between the\nalgorithmic performance of the Belief Propagation Guided Decimation encoder and\nthe phase diagram of this Gibbs measure. The phase diagram is investigated\nthanks to the cavity method of spin glass theory which predicts a number of\nphase transition thresholds. In particular the dynamical and condensation\n"phase transition temperatures" (equivalently test-channel noise thresholds)\nare computed. We observe that: (i) the dynamical temperature of the spatially\ncoupled construction saturates towards the condensation temperature; (ii) for\nlarge degrees the condensation temperature approaches the temperature (i.e.\nnoise level) related to the information theoretic Shannon test-channel noise\nparameter of rate-distortion theory. This provides heuristic insight into the\nexcellent performance of the Belief Propagation Guided Decimation algorithm.\nThe paper contains an introduction to the cavity method.\n