Critical behavior in lossy source coding

DOI10.1109/18.915693MaRDI QIDQ4544563zbMATH OpenOpenAlexFDO

Authors Amir Dembo, Ioannis Kontoyiannis

Publication date 4 August 2002

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

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

zbMATH Keywords

compression ratiolossy data compressionrate-distortion theoryredundancy

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Source coding (94A29) Rate-distortion theory in information and communication theory (94A34)

Abstract: The following critical phenomenon was recently discovered. When a memoryless source is compressed using a variable-length fixed-distortion code, the fastest convergence rate of the (pointwise) compression ratio to the optimal $R(D)$ bits/symbol is either $O(sqrtn)$ or $O(logn)$. We show it is always $O(sqrtn)$, except for discrete, uniformly distributed sources.

Recommendations

• Fixed-rate universal lossy source coding and rates of convergence for memoryless sources
• The Empirical Distribution of Rate-Constrained Source Codes
• On critical distortion for Markov sources (Corresp.)
• scientific article; zbMATH DE number 763790
• The redundancy of source coding with a fidelity criterion. 1. Known statistics

Cited in

(2)

• A comment on "A rate of convergence result for a universal D-semifaithful code"
• Finite Blocklength Lossy Source Coding for Discrete Memoryless Sources

This page was built for publication: Critical behavior in lossy source coding

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