Discrete Wyner Ziv problem second order coding rates improved
Exact Second-Order Asymptotics for the Discrete Wyner--Ziv Problem
Information Theory
Summary
The Wyner-Ziv problem deals with compressing data when some related information is available to the decoder but not the encoder. The authors improved the understanding of how precisely such compression performs by finding exact second-order terms that describe coding rates more accurately. They showed previous best methods were not always optimal and provided better coding bounds by adapting the compression method depending on the data type. This result helps refine limits on how efficiently data can be compressed in certain settings with side information.
What this means in practice
- •For data compression engineers: Implement improved compression schemes for sources with decoder side information that achieve tighter performance guarantees at finite blocklengths.
- •For network protocol designers: Design communication systems with informed decoder compression that better balance rate and distortion under practical constraints.
Authors
Lin Zhou
Abstract
We revisit the discrete Wyner--Ziv problem and establish exact second-order asymptotics. Our main contribution is a second-order converse bound, which is derived using posterior decomposition, concentration inequalities, and a conditional Gaussian approximation for martingales. Furthermore, we extend the previous best known achievability result of Li and Li (arXiv 2025) by allowing the test channel to depend on the type of the observed source sequence. Exact second-order asymptotics are established by combining our achievability and converse bounds. In particular, we show that the achievability bound of Li and Li (arXiv 2025) is not optimal in general. Specifically, we provide two numerical examples to illustrate our results: a binary asymmetric source and a quaternary source. For the first example, the achievability bound of Li and Li (arXiv 2025) achieves the optimal second-order asymptotics. However, in the second example, we show that our achievability result is optimal, which reduces the second-order coding rate of Li and Li (arXiv 2025) by $10.77\%$ at the excess-distortion probability of $0.1$ and by $21.35\%$ at the excess-distortion probability of $0.2$.