The Generalized Asymptotic Equipartition Property: Necessary and Sufficient Conditions

DOI10.1109/TIT.2008.924668MaRDI QIDQ3604574zbMATH OpenDBLPWikidataFDO

Authors Matthew T. Harrison

Publication date 24 February 2009

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Suppose a string $X_1^n=(X_1,X_2,\mathrm{...},X_n)$ generated by a memoryless source $(X_n{)}_{ngeq1}$ with distribution $P$ is to be compressed with distortion no greater than $Dgeq0$, using a memoryless random codebook with distribution $Q$. The compression performance is determined by the ``generalized asymptotic equipartition property (AEP), which states that the probability of finding a $D$-close match between $X_1^n$ and any given codeword $Y_1^n$, is approximately $2^{-nR(P,Q,D)}$, where the rate function $R(P,Q,D)$ can be expressed as an infimum of relative entropies. The main purpose here is to remove various restrictive assumptions on the validity of this result that have appeared in the recent literature. Necessary and sufficient conditions for the generalized AEP are provided in the general setting of abstract alphabets and unbounded distortion measures. All possible distortion levels $Dgeq0$ are considered; the source $(X_n{)}_{ngeq1}$ can be stationary and ergodic; and the codebook distribution can have memory. Moreover, the behavior of the matching probability is precisely characterized, even when the generalized AEP is not valid. Natural characterizations of the rate function $R(P,Q,D)$ are established under equally general conditions.

Recommendations

• The role of the asymptotic equipartition property in noiseless source coding
• Source coding, large deviations, and approximate pattern matching
• Arbitrary source models and Bayesian codebooks in rate-distortion theory
• Universal almost sure data compression
• The Empirical Distribution of Rate-Constrained Source Codes

Cited in

(7)

• Limit theorems for random normalized distortion
• Necessary and sufficient conditions for the existence of the ε-Property (A.E.P.)
• A Short Note on Almost Sure Convergence of Bayes Factors in the General Set-Up
• An asymptotic equipartition property for measures on model spaces
• Lossy asymptotic equipartition property for hierarchical data structures
• The asymptotic equipartition property for a special Markov random field
• Source coding, large deviations, and approximate pattern matching

This page was built for publication: The Generalized Asymptotic Equipartition Property: Necessary and Sufficient Conditions

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