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.


Published in:
Proceedings of 2013 IEEE International Symposium on Information Theory
Presented at:
2013 IEEE International Symposium on Information Theory, Istanbul, Turkey, July 2013
Year:
2013
Keywords:
Laboratories:


Note: PRIVATE


 Record created 2013-09-04, last modified 2018-03-17

Publisher's version:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)