Allerton 2015 Paper Abstract


Paper ThA6.4

Hosseinitoushmanlouei, Maryamsadat (University of Hawaii at Manoa), Santhanam, Narayana Prasad (University of Hawaii)

Single Letter Characterization of Average-Case Strong Redundancy of Compressing Memoryless Sequences

Scheduled for presentation during the Regular Session "Information Theory and Source Coding" (ThA6), Thursday, October 1, 2015, 09:30−09:50, Visitor Center

53rd Annual Allerton Conference on Communication, Control, and Computing, Sept 29-Oct 2, 2015, Allerton Park and Retreat Center, Monticello, IL, USA

This information is tentative and subject to change. Compiled on August 4, 2020

Keywords Information Theory, Source Coding and Compression


We obtain a condition that is both necessary and sufficient to characterize strong universal compressibility (in the average sense) of sequences generated by iid sampling from a collection $cP$ of distributions over a countably infinite alphabet. Contrary to the worst case regret formulation of universal compression, finite single letter (average case) redundancy of $cP$ does not automatically imply that the expected redundancy of describing length-$n$ strings sampled iid from $cP$ grows sublinearly with $n$. Instead, we prove that asymptotic per-symbol redundancy of universally compressing length-$n$ iid sequences from $cP$ is characterized by how well the tails of their single letter marginals can be universally described, and we formalize the later as the tail-redundancy of $cP$.



All Content © PaperCept, Inc..

This site is protected by copyright and trademark laws under US and International law.
All rights reserved. © 2002-2020 PaperCept, Inc.
Page generated 2020-08-04  07:08:13 PST  Terms of use