Nonasymptotic and Second-Order Achievability Bounds for Coding With Side-Information

DOI10.1109/TIT.2015.2400994MaRDI QIDQ2978663zbMATH OpenOpenAlexFDO

Authors Shun Watanabe, Shigeaki Kuzuoka, Vincent Y. F. Tan

Publication date 28 April 2017

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

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

Mathematics Subject Classification ID

Source coding (94A29) Bounds on codes (94B65)

Abstract: We present novel non-asymptotic or finite blocklength achievability bounds for three side-information problems in network information theory. These include (i) the Wyner-Ahlswede-Korner (WAK) problem of almost-lossless source coding with rate-limited side-information, (ii) the Wyner-Ziv (WZ) problem of lossy source coding with side-information at the decoder and (iii) the Gel'fand-Pinsker (GP) problem of channel coding with noncausal state information available at the encoder. The bounds are proved using ideas from channel simulation and channel resolvability. Our bounds for all three problems improve on all previous non-asymptotic bounds on the error probability of the WAK, WZ and GP problems--in particular those derived by Verdu. Using our novel non-asymptotic bounds, we recover the general formulas for the optimal rates of these side-information problems. Finally, we also present achievable second-order coding rates by applying the multidimensional Berry-Esseen theorem to our new non-asymptotic bounds. Numerical results show that the second-order coding rates obtained using our non-asymptotic achievability bounds are superior to those obtained using existing finite blocklength bounds.

Cited in

(7)

• Second-Order Slepian-Wolf Coding Theorems for Non-Mixed and Mixed Sources
• Adaptive sparse estimation with side information
• Non-Asymptotic Converse Bounds and Refined Asymptotics for Two Source Coding Problems
• Finite Blocklength Lossy Source Coding for Discrete Memoryless Sources
• Slepian-Wolf coding with quantum side information
• Channel simulation: theory and applications to lossy compression and differential privacy
• Second-order converses via reverse hypercontractivity

This page was built for publication: Nonasymptotic and Second-Order Achievability Bounds for Coding With Side-Information

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