Strong Functional Representation Lemma and Applications to Coding Theorems

DOI10.1109/TIT.2018.2865570zbMATH Open1432.60030arXiv1701.02827OpenAlexW2886523564WikidataQ124805605 ScholiaQ124805605MaRDI QIDQ4559570FDOQ4559570

Authors:

Publication date: 4 December 2018

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

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.

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

Mathematics Subject Classification ID

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

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)