Accelerating Relative Entropy Coding with Space Partitioning

• URL: http://arxiv.org/abs/2405.12203v3
• Date: Tue, 29 Oct 2024 10:14:32 GMT
• Title: Accelerating Relative Entropy Coding with Space Partitioning
• Abstract summary: Relative entropy coding (REC) algorithms encode a random sample following a target distribution $Q$. REC algorithms suffer from prohibitive encoding times, at least on the order of $2D_textKL[Q||P]$. We introduce a REC scheme utilizing space partitioning to reduce runtime in practical scenarios.
• Score: 32.30151436903008
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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 method and demonstrate its effectiveness with both toy examples and practical applications. Notably, our method successfully handles REC tasks with $D_{\text{KL}}[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.

Related papers

• Turbo-DDCM: Fast and Flexible Zero-Shot Diffusion-Based Image Compression [54.1069581766925]
  This paper presents an efficient zero-shot diffusion-based compression method that runs substantially faster than existing methods.<n>Our method builds upon the recently proposed Denoising Diffusion Codebook Models (DDCMs) compression scheme.<n>We introduce two flexible variants of Turbo-DDCM, a priority-aware variant that prioritizes user-specified regions and a distortion-controlled variant that compresses an image based on a target PSNR rather than a target BPP.
  arXiv  Detail & Related papers  (2025-11-09T15:41:27Z)
• Reducing Storage of Pretrained Neural Networks by Rate-Constrained Quantization and Entropy Coding [56.066799081747845]
  The ever-growing size of neural networks poses serious challenges on resource-constrained devices.<n>We propose a novel post-training compression framework that combines rate-aware quantization with entropy coding.<n>Our method allows for very fast decoding and is compatible with arbitrary quantization grids.
  arXiv  Detail & Related papers  (2025-05-24T15:52:49Z)
• EoRA: Fine-tuning-free Compensation for Compressed LLM with Eigenspace Low-Rank Approximation [84.70637613266835]
  EoRA is a fine-tuning-free method that augments compressed Large Language Models with low-rank matrices.<n>EoRA consistently outperforms prior training-free low rank methods in recovering the accuracy of compressed LLMs.
  arXiv  Detail & Related papers  (2024-10-28T17:59:03Z)
• Bit-flipping Decoder Failure Rate Estimation for (v,w)-regular Codes [84.0257274213152]
  We propose a new technique to provide accurate estimates of the DFR of a two-iterations (parallel) bit flipping decoder. We validate our results, providing comparisons of the modeled and simulated weight of the syndrome, incorrectly-guessed error bit distribution at the end of the first iteration, and two-itcrypteration Decoding Failure Rates (DFR)
  arXiv  Detail & Related papers  (2024-01-30T11:40:24Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• Unrolled Compressed Blind-Deconvolution [77.88847247301682]
  sparse multichannel blind deconvolution (S-MBD) arises frequently in many engineering applications such as radar/sonar/ultrasound imaging. We propose a compression method that enables blind recovery from much fewer measurements with respect to the full received signal in time.
  arXiv  Detail & Related papers  (2022-09-28T15:16:58Z)
• Deep Lossy Plus Residual Coding for Lossless and Near-lossless Image Compression [85.93207826513192]
  We propose a unified and powerful deep lossy plus residual (DLPR) coding framework for both lossless and near-lossless image compression. We solve the joint lossy and residual compression problem in the approach of VAEs. In the near-lossless mode, we quantize the original residuals to satisfy a given $ell_infty$ error bound.
  arXiv  Detail & Related papers  (2022-09-11T12:11:56Z)
• Lossy Compression with Gaussian Diffusion [28.930398810600504]
  We describe a novel lossy compression approach called DiffC which is based on unconditional diffusion generative models. We implement a proof of concept and find that it works surprisingly well despite the lack of an encoder transform. We show that a flow-based reconstruction achieves a 3 dB gain over ancestral sampling at highs.
  arXiv  Detail & Related papers  (2022-06-17T16:46:31Z)
• Injecting Domain Adaptation with Learning-to-hash for Effective and Efficient Zero-shot Dense Retrieval [49.98615945702959]
  We evaluate LTH and vector compression techniques for improving the downstream zero-shot retrieval accuracy of the TAS-B dense retriever. Our results demonstrate that, unlike prior work, LTH strategies when applied naively can underperform the zero-shot TAS-B dense retriever on average by up to 14% nDCG@10.
  arXiv  Detail & Related papers  (2022-05-23T17:53:44Z)
• Implicit Neural Representations for Image Compression [103.78615661013623]
  Implicit Neural Representations (INRs) have gained attention as a novel and effective representation for various data types. We propose the first comprehensive compression pipeline based on INRs including quantization, quantization-aware retraining and entropy coding. We find that our approach to source compression with INRs vastly outperforms similar prior work.
  arXiv  Detail & Related papers  (2021-12-08T13:02:53Z)
• Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding [45.66971406567023]
  bits-back suffers from an increase in the equal to the KL divergence between the approximate posterior and the true posterior. We show how to remove this gapally by deriving bits-back coding algorithms from tighter variational bounds.
  arXiv  Detail & Related papers  (2021-02-22T14:58:01Z)
• Compressing Images by Encoding Their Latent Representations with Relative Entropy Coding [5.687243501594734]
  Variational Autoencoders (VAEs) have seen widespread use in learned image compression. We propose a novel method, Relative Entropy Coding (REC), that can directly encode the latent representation with codelength close to the relative entropy for single images.
  arXiv  Detail & Related papers  (2020-10-02T20:23:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.