Accelerating Relative Entropy Coding with Space Partitioning

arXiv:2405.12203v1 Announce Type: cross
Abstract: Relative entropy coding (REC) algorithms encode a random sample following a target distribution $Q$, using a coding distribution $P$ shared between the sender and receiver. Sadly, general REC algorithms suffer from prohibitive encoding times, at least on the order of $2^{D_{\text{KL}}[Q||P]}$, and faster algorithms are limited to very specific settings. This work addresses this issue by introducing a REC scheme utilizing space partitioning to reduce runtime in practical scenarios. We provide theoretical analyses of our …

abstract algorithms arxiv coding cs.it cs.lg distribution encode encoding entropy faster general least math.it partitioning random sample space text type