Approaching the Rate-Distortion Limit by spatial Coupling with Belief Propagation and Decimation

• Presented at: 2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, July 2013
• Published in: Proceedings of 2013 IEEE International Symposium on Information Theory
• Publication date: 2013

We investigate an encoding scheme for lossy compression based on spatially coupled Low-Density Generator-Matrix codes. The degree distributions are regular, or are Poisson on the code-bit side and check-regular which allows use for any compression rate. The performance of a low complexity Belief Propagation Guided Decimation algorithm is excellent, and for large check degrees it gets close to Shannon's rate-distortion limit. We investigate links between the algorithmic performance and the phase diagram of a relevant random Gibbs measure. The associated dynamical and condensation thresholds are computed within the framework of the cavity method. We observe that: (i) the dynamical threshold of the spatially coupled construction saturates towards the condensation threshold; (ii) for large degrees the condensation threshold approaches the information theoretic test-channel parameter of rate-distortion theory. This provides heuristic insight into the excellent performance of the BPGD algorithm.

Keywords: Lossy source coding ; spatial coupling ; LDGM ; belief propagation guided decimation ; rate distortion bound

Reference

• EPFL-CONF-188376

Record created on 2013-09-04, modified on 2017-05-12