Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2605.00579 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917453160775680 |
|---|---|
| author | Szewczyk, Kamila |
| author_facet | Szewczyk, Kamila |
| contents | Range coders and ANS replace empirical probabilities with integer frequencies summing to a fixed $M$; the resulting per-symbol code-length redundancy is exactly the KL divergence of the empirical distribution from the quantized one. Existing normalizers (Giesen, Bloom, Collet) are heuristic or only partially marginal-optimal. We give three provably KL-optimal algorithms: a bottom-up archetype, a bidirectional exchange repair of Bloom's heap correction, and a top-down window method that runs in $\mathcal{O}(r)$, asymptotically optimal in $r$, where $r$ is the number of positive-count symbols. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_00579 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization Szewczyk, Kamila Information Theory Range coders and ANS replace empirical probabilities with integer frequencies summing to a fixed $M$; the resulting per-symbol code-length redundancy is exactly the KL divergence of the empirical distribution from the quantized one. Existing normalizers (Giesen, Bloom, Collet) are heuristic or only partially marginal-optimal. We give three provably KL-optimal algorithms: a bottom-up archetype, a bidirectional exchange repair of Bloom's heap correction, and a top-down window method that runs in $\mathcal{O}(r)$, asymptotically optimal in $r$, where $r$ is the number of positive-count symbols. |
| title | Fast and Exact: Asymptotically Linear KL-Optimal Frequency Normalization |
| topic | Information Theory |
| url | https://arxiv.org/abs/2605.00579 |