Adaptive Coding over Countable Alphabets
summary
Defines envelope classes for countable alphabets and shows a concrete thresholding/censoring code that uses a data-driven threshold plus a mixture coder on the small alphabet and Elias-style coding for large symbols. Proves this code attains the minimax redundancy rate for light-tail envelopes (nondecreasing hazard rate) and is weakly adaptive for regularly varying tails, losing at most a factor O(log n). Analysis uses extreme-value quantiles, concentration bounds, and links lower bounds to the expected number of distinct symbols.
AI-written summary · about
chapters (7)
- 0:00Intro
- 0:34Lossless compression over a countable alphabet
- 5:49Redundancies alphabet size matters
- 9:54Envelop classes
- 13:49Bounds on minimax redundancy
- 19:22Censuring codes sketch
- 20:48Envelopes with heavier tails
related talks
43mCoded matrix computation: numerical stability, partial stragglers and sparse input matrices
45mTeaching an old code a new trick
31mStatistical Estimation on Graphs
44mStochastic Integration via Error-Correcting Codes
33mGap to Capacity of Finite Length Polar Codes
37mSparse Superposition Codes for the AWGN Channel, Message Passing, Replica and Spatial Coupling
43mCapacity Analysis of Vector Symbolic Architectures
48mSpatial Coupling as a Proof Technique