| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
16 February 2025 |
|
| | | |
|
Article overview
| |
|
Pattern Coding Meets Censoring: (almost) Adaptive Coding on Countable Alphabets | Anna Ben-Hamou
; Stephane Boucheron
; Elisabeth Gassiat
; | Date: |
1 Sep 2016 | Abstract: | Adaptive coding faces the following problem: given a collection of source
classes such that each class in the collection has non-trivial minimax
redundancy rate, can we design a single code which is asymptotically minimax
over each class in the collection? In particular, adaptive coding makes sense
when there is no universal code on the union of classes in the collection. In
this paper, we deal with classes of sources over an infinite alphabet, that are
characterized by a dominating envelope. We provide asymptotic equivalents for
the redundancy of envelope classes enjoying a regular variation property. We
finally construct a computationally efficient online prefix code, which
interleaves the encoding of the so-called pattern of the message and the
encoding of the dictionary of discovered symbols. This code is shown to be
adaptive, within a $loglog n$ factor, over the collection of regularly
varying envelope classes. The code is both simpler and less redundant than
previously described contenders. In contrast with previous attempts, it also
covers the full range of slowly varying envelope classes. | Source: | arXiv, 1608.8367 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|