Critical Behavior in Lossy Source Coding
<|reference_start|>Critical Behavior in Lossy Source Coding: 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(\sqrt{n})$ or $O(\log n)$. We show it is always $O(\sqrt{n})$, except for discrete, uniformly distributed sources.<|reference_end|>
@article{dembo2000critical,
    title={Critical Behavior in Lossy Source Coding},
    author={Amir Dembo and Ioannis Kontoyiannis},
    journal={arXiv preprint arXiv:math/0009018},
    year={2000},
    archivePrefix={arXiv},
    eprint={math/0009018},
    primaryClass={math.PR cs.IT math.IT}
}