A lower bound on compression of unknown alphabets

DOI10.1016/J.TCS.2004.10.038MaRDI QIDQ1770393zbMATH OpenOpenAlexFDO

Authors Nikola Jevtić, Alon Orlitsky, Narayana P. Santhanam

Publication date 6 April 2005

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2004.10.038

zbMATH Keywords

Hayman's theoremLarge and unknown alphabetsPatternsSaddle point approximationsUniversal compression

Mathematics Subject Classification ID

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

Recommendations

• Universal Compression of Memoryless Sources Over Unknown Alphabets
• Universal Lossless Compression With Unknown Alphabets—The Average Case
• Universal Compression of Markov and Related Sources Over Arbitrary Alphabets
• Speaking of Infinity
• A lower-bound for the maximin redundancy in pattern coding

Cites work

• A decision-theoretic extension of stochastic complexity and its applications to learning
• A game of prediction with expert advice
• A Generalisation of Stirling's Formula.
• A unified approach to weak universal source coding
• Always Good Turing: asymptotically optimal probability estimation
• Asymptotic minimax regret for data compression, gambling, and prediction
• Fisher information and stochastic complexity
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Multi-alphabet universal coding of memoryless sources
• On asymptotics of certain recurrences arising in universal coding
• One-way communication and error-correcting codes
• Precise Minimax Redundancy and Regret
• Speaking of Infinity
• Special issue: Average-case analysis of algorithms
• The performance of universal encoding
• Universal codes for finite sequences of integers drawn from a monotone distribution
• Universal codeword sets and representations of the integers
• Universal Compression of Memoryless Sources Over Unknown Alphabets
• Universal Lossless Compression With Unknown Alphabets—The Average Case
• Universal Portfolios
• Universal portfolios with side information
• Universal sequential coding of single messages

Cited in

(6)

• Speaking of Infinity
• Universal Compression of Memoryless Sources Over Unknown Alphabets
• Universal Compression of Markov and Related Sources Over Arbitrary Alphabets
• Universal Lossless Compression With Unknown Alphabets—The Average Case
• scientific article; zbMATH DE number 975330 (Why is no real title available?)
• A lower-bound for the maximin redundancy in pattern coding

This page was built for publication: A lower bound on compression of unknown alphabets

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