Non-Asymptotic and Second-Order Achievability Bounds for Coding With Side-Information
arXiv:1301.6467
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.
32 pages (two column), 8 figures, v2 fixed some minor errors in the WZ problem, v2 included cost constraint in the GP problem, v3 added cardinality bounds, v4 fixed an error of the numerical calculation in the GP problem, v5 is an accepted version for publication
References in corpus (5)
- Distributed Channel Synthesis
- A Tight Upper Bound for the Third-Order Asymptotics for Most Discrete Memoryless Channels
- The Dispersion of Lossy Source Coding
- A Technique for Deriving One-Shot Achievability Results in Network Information Theory
- The Gelfand-Pinsker Channel: Strong Converse and Upper Bound for the Reliability Function
Cited by in corpus (7)
- A Technique for Deriving One-Shot Achievability Results in Network Information Theory
- Strong Converse and Second-Order Asymptotics of Channel Resolvability
- Second-Order Coding Rates for Conditional Rate-Distortion
- On the Dispersions of the Gel'fand-Pinsker Channel and Dirty Paper Coding
- A Case Where Interference Does Not Affect The Channel Dispersion
- Random Number Conversion and LOCC Conversion via Restricted Storage
- A Formula for the Capacity of the General Gel'fand-Pinsker Channel