mlsanityData to 14 Oct 2026

Accelerating Relative Entropy Coding with Space Partitioning

arXiv 2405.12203 ↗First posted 20 May 2024cs.IT cs.LG math.ITcited by 4

Not on the map. Why?

Abstract (arXiv)

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^DKL[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 method and demonstrate its effectiveness with both toy examples and practical applications. Notably, our method successfully handles REC tasks with DKL[Q||P] about three times greater than what previous methods can manage, and reduces the bitrate by approximately 5-15% in VAE-based lossless compression on MNIST and INR-based lossy compression on CIFAR-10, compared to previous methods, significantly improving the practicality of REC for neural compression.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 17 of its 35 references that are in the map. First posted on arXiv 20 May 2024.

Builds on

17 of 35 references.

References · 17

  1. 2018Variational image compression with a scale hyperpriorcited by 935
  2. 2016End-to-end Optimized Image Compressioncited by 696
  3. 2020Learned Image Compression with Discretized Gaussian Mixture Likelihoods and Attention Modulescited by 590
  4. 2017The Perception-Distortion Tradeoffcited by 587
  5. 2014A* Samplingcited by 151
  6. 2020Nonlinear Transform Codingcited by 136
  7. 2018Practical Full Resolution Learned Lossless Image Compressioncited by 94
  8. 2022Lossy Compression with Gaussian Diffusioncited by 90
  9. 2019Practical Lossless Compression with Latent Variables using Bits Back Codingcited by 86
  10. 2018Minimal Random Code Learning: Getting Bits Back from Compressed Model Parameterscited by 58
  11. 2020Compressing Images by Encoding Their Latent Representations with Relative Entropy Codingcited by 39
  12. 2021Algorithms for the Communication of Samplescited by 34
5 more
  1. 2021On the advantages of stochastic encoderscited by 28
  2. 2023Compression with Bayesian Implicit Neural Representationscited by 25
  3. 2023Modality-Agnostic Variational Compression of Implicit Neural Representationscited by 22
  4. 2023RECOMBINER: Robust and Enhanced Compression with Bayesian Implicit Neural Representationscited by 9
  5. 2024Some Notes on the Sample Complexity of Approximate Channel Simulationcited by 4

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 3.

4 papers.

  1. 2026Compression as Adaptation: Implicit Visual Representation with Diffusion Foundation Modelscited by 2
  2. 2026Accelerating Diffusion Sampling via Speculative Draft Treescited by 2
  3. 2025Training-Free Vector Quantization via Gaussian VAEscited by 1
  4. 2026Watermarkable Multi-Draft Speculative Sampling via Poisson Processescited by 0