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

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.