Non-Asymptotic Converse Bounds and Refined Asymptotics for Two Source Coding Problems

DOI10.1109/TIT.2019.2920893MaRDI QIDQ5211452zbMATH OpenOpenAlexWikidataFDO

Authors Lin Zhou, Mehul Motani

Publication date 28 January 2020

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

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

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: In this paper, we revisit two multi-terminal lossy source coding problems: the lossy source coding problem with side information available at the encoder and one of the two decoders, which we term as the Kaspi problem (Kaspi, 1994), and the multiple description coding problem with one semi-deterministic distortion measure, which we refer to as the Fu-Yeung problem (Fu and Yeung, 2002). For the Kaspi problem, we first present the properties of optimal test channels. Subsequently, we generalize the notion of the distortion-tilted information density for the lossy source coding problem to the Kaspi problem and prove a non-asymptotic converse bound using the properties of optimal test channels and the well-defined distortion-tilted information density. Finally, for discrete memoryless sources, we derive refined asymptotics which includes the second-order, large and moderate deviations asymptotics. In the converse proof of second-order asymptotics, we apply the Berry-Esseen theorem to the derived non-asymptotic converse bound. The achievability proof follows by first proving a type-covering lemma tailored to the Kaspi problem, then properly Taylor expanding the well-defined distortion-tilted information densities and finally applying the Berry-Esseen theorem. We then generalize the methods used in the Kaspi problem to the Fu-Yeung problem. As a result, we obtain the properties of optimal test channels for the minimum sum-rate function, a non-asymptotic converse bound and refined asymptotics for discrete memoryless sources. Since the successive refinement problem is a special case of the Fu-Yeung problem, as a by-product, we obtain a non-asymptotic converse bound for the successive refinement problem, which is a strict generalization of the non-asymptotic converse bound for successively refinable sources (Zhou, Tan and Motani, 2017).

Recommendations

• Asymptotics and Non-Asymptotics for Universal Fixed-to-Variable Source Coding
• Nonasymptotic and Second-Order Achievability Bounds for Coding With Side-Information
• Refinement of the Random Coding Bound
• The strong converse for source coding with a fidelity criterion
• An Improvement of the Asymptotic Elias Bound for Non-Binary Codes
• Tight Bounds for Symmetric Divergence Measures and a Refined Bound for Lossless Source Coding
• A random coding bound for fixed convolutional codes of rate 1/n
• Strong converses in source coding relative to a fidelity criterion
• Refined Asymptotics for Rate-Distortion Using Gaussian Codebooks for Arbitrary Sources
• scientific article; zbMATH DE number 493088

Cited in

(3)

• Heegard–Berger and Cascade Source Coding Problems With Common Reconstruction Constraints
• Simple one-shot bounds for various source coding problems using smooth Rényi quantities
• Finite Blocklength Lossy Source Coding for Discrete Memoryless Sources

This page was built for publication: Non-Asymptotic Converse Bounds and Refined Asymptotics for Two Source Coding Problems

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