Improved precision in lossy compression data limits and code sizes
Third-Order Asymptotics for Fixed-Length Lossy Compression of Discrete Memoryless Sources
Information Theory
Summary
This paper finds a more precise formula for how many bits you need when compressing data without losing too much quality. The researchers improved previous estimates by adding smaller correction terms, giving a sharper understanding of the limits of fixed-length compression of random data. Their approach uses advanced mathematical methods to handle difficult cases and proves that their estimates are tight and reliable. This helps better predict the trade-off between data size, compression quality, and probability of errors.
What this means in practice
- •For data compression engineers: Design fixed-length compression codes with more precise size and error guarantees for specific distortion levels.
- •For communications system designers: Improve system models predicting minimal codebook sizes needed for given distortion and reliability in digital communications.
A theory result. No direct application yet.
Authors
Vincent Y. F. Tan
Abstract
This paper determines the third-order asymptotics of the logarithm of the minimum codebook size for fixed-length lossy compression of discrete memoryless sources. For an excess-distortion probability constraint $\varepsilon\in(0,1)$ and every interior distortion level, we establish a third-order correction of $\frac12\log n+O(1)$, where $n$ is the blocklength. This sharpens the general bounds of Kostina and Verdú [IEEE Trans. Inf. Theory, 2012]. The main technical innovation lies in the converse for positive dispersion. Under a reverse change of measure, we retain the exponential weights associated with tilted information and distortion slack and control them jointly using the multivariate weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [Proc. IEEE ISIT, 2015]. A pairing argument verifies the required covariance nondegeneracy uniformly over all reconstruction words whose distortion balls meet a typical set, yielding the matching converse.