Problems of robustness for universal coding schemes

DOI10.1023/A:1023626414365MaRDI QIDQ2487076zbMATH OpenOpenAlexFDO

Authors Vladimir V. V'yugin

Publication date 17 August 2005

Published in Problems of Information Transmission (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.4572

zbMATH Keywords

compressionsource codingcoding and information theory

Mathematics Subject Classification ID

Source coding (94A29) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: The Lempel-Ziv universal coding scheme is asymptotically optimal for the class of all stationary ergodic sources. A problem of robustness of this property under small violations of ergodicity is studied. A notion of deficiency of algorithmic randomness is used as a measure of disagreement between data sequence and probability measure. We prove that universal compressing schemes from a large class are non-robust in the following sense: if the randomness deficiency grows arbitrarily slowly on initial fragments of an infinite sequence then the property of asymptotic optimality of any universal compressing algorithm can be violated. Lempel-Ziv compressing algorithms are robust on infinite sequences generated by ergodic Markov chains when the randomness deficiency of its initial fragments of length $n$ grows as $o(n)$.

Recommendations

• Universal almost sure data compression
• scientific article; zbMATH DE number 4132084
• Redundancy estimates for the Lempel–Ziv algorithm of data compression
• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
• Publication:3199318

Cited in

(10)

• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
• Redundancy estimates for the Lempel–Ziv algorithm of data compression
• On stability of probability laws with respect to small violations of algorithmic randomness
• scientific article; zbMATH DE number 4132084 (Why is no real title available?)
• The coding complexity of Lévy processes
• An adaptive compression algorithm in a deterministic world
• On the stability property of asymptotic laws of ergodic theory and universal compression schemes
• Universal almost sure data compression
• scientific article; zbMATH DE number 78498 (Why is no real title available?)
• Robustness of the decomposition functional for a sequence of symbols in a given dictionary of standard fragments

This page was built for publication: Problems of robustness for universal coding schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2487076)