Approaching the Rate-Distortion Limit by spatial Coupling with Belief Propagation and Decimation
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.
Cite this item
Aref, V., Macris, N., & Vuffray, M. (2013). Approaching the Rate-Distortion Limit by spatial Coupling with Belief Propagation and Decimation. Proceedings of 2013 IEEE International Symposium on Information Theory, 1177–1181. https://doi.org/10.1109/ISIT.2013.6620412
Click Copy to copy the citation, or select the text manually.
2013
1177
1181
REVIEWED
EPFL
| Event name | Event place | Event date |
Istanbul, Turkey | July 2013 | |