Strong Functional Representation Lemma and Applications to Coding Theorems

DOI10.1109/TIT.2018.2865570MaRDI QIDQ4559570zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 4 December 2018

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

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

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Source coding (94A29)

Abstract: This paper shows that for any random variables $X$ and $Y$, it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)lelog(I(X;Y)+1)+4$ bits. We use this strong functional representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding and Gray-Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand-Pinsker theorem.

Cited in

(1)

• Common Information, Noise Stability, and Their Extensions

This page was built for publication: Strong Functional Representation Lemma and Applications to Coding Theorems

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