Universal Compression of Envelope Classes: Tight Characterization via Poisson Sampling
This work addresses the problem of characterizing redundancy in universal compression for envelope classes, which is incremental but provides tighter bounds and resolves a known question in information theory.
The authors tackled the problem of universal compression for envelope classes by applying Poisson sampling to relate redundancies of fixed-length and Poisson-sampled sequences, resulting in a simple single-letter formula that approximates redundancy to within an additive logarithmic term. They used this to tighten bounds on redundancies for exponential and power-law classes, answering a specific open question.
The Poisson-sampling technique eliminates dependencies among symbol appearances in a random sequence. It has been used to simplify the analysis and strengthen the performance guarantees of randomized algorithms. Applying this method to universal compression, we relate the redundancies of fixed-length and Poisson-sampled sequences, use the relation to derive a simple single-letter formula that approximates the redundancy of any envelope class to within an additive logarithmic term. As a first application, we consider i.i.d. distributions over a small alphabet as a step-envelope class, and provide a short proof that determines the redundancy of discrete distributions over a small al- phabet up to the first order terms. We then show the strength of our method by applying the formula to tighten the existing bounds on the redundancy of exponential and power-law classes, in particular answering a question posed by Boucheron, Garivier and Gassiat.