 |
Center for Nonlinear Studies |
We investigate an encoding scheme for lossy compression of a binary symmetric source based on simple spatially coupled Low-Density Generator Matrix codes. The performance of a low complexity Belief Propagation Guided Decimation (BPGD) algorithm is excellent and approaches the optimum as the width of the coupling window grows. The BPGD encoder is based on the posterior measure of a Binary Symmetric test-channel. This measure can be interpreted as a random Gibbs measure of a diluted p-spin model at an inverse temperature related to the noise parameter of the test-channel. We investigate the links between the algorithmic performance of the BGDP encoder and the phase diagram of the Gibbs measure. The later is investigated thanks to the cavity method of spin glass theory, and in particular the dynamical and condensation phase transition temperature. This provides heuristic insight into the excellent performance of the BPGD algorithm.
Host: Misha Chertkov