Strong functional representation lemma and applications to coding theorems
Authors:
- 1 June 2017
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 589-593
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) ≤ log(I(X; Y)+1)+4. We use this strong functional representation lemma (SFRL) to establish a tighter bound on the rate needed for one-shot exact channel simulation than was previously established by Harsha et. al., and to establish achievability results for one-shot variable-length lossy source coding and multiple description coding. 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. Finally we present an example in which the SFRL inequality is tight to within 5 bits.Keywords
All Related Versions
This publication has 26 references indexed in Scilit:
- One-shot mutual covering lemma and Marton's inner bound with a common message2015
- Resolvability in Eγ with applications to lossy compression and wiretap channels2015
- One-Shot Lossy Quantum Data CompressionIEEE Transactions on Information Theory, 2013
- Non-asymptotic and second-order achievability bounds for source coding with side-information2013
- A technique for deriving one-shot achievability results in network information theory2013
- Non-asymptotic achievability bounds in multiuser information theory2012
- Universal Almost Sure Data CompressionThe Annals of Probability, 1990
- A coding theorem for the discrete memoryless broadcast channelIEEE Transactions on Information Theory, 1979
- Variable-rate universal block source coding subject to a fidelity constraintIEEE Transactions on Information Theory, 1978
- Variable rate coding for nonergodic sources and classes of ergodic sources subject to a fidelity constraintIEEE Transactions on Information Theory, 1976