PaperlayerView exact revision on arXiv

Source-linked AI summary

Strong Functional Representation Lemma and Applications to Coding Theorems

Cheuk Ting Li, Abbas El Gamal

arXiv:1701.02827v4cs.IT

TL;DR

The paper addresses how to choose independent randomness Z so that Y is a function of (X,Z) while keeping the auxiliary dependence small. It introduces the SFRL and Poisson functional representation, obtaining a logarithmic conditional-mutual-information bound and applying it to one-shot channel and source coding, including Gelfand–Pinsker achievability.

  • Problem

    The functional representation lemma does not uniquely determine Z, motivating the question of whether an independent representation can make H(Y|Z) close to I(X;Y).

  • Method

    The paper uses a Poisson functional representation to construct Z independent of X with Y=g(X,Z), then combines SFRL with prefix coding and channel coding.

  • Results

    I(X;Z|Y) ≤ log(I(X;Y)+1)+4, and the SFRL yields one-shot variable-length achievability results across channel simulation and several source-coding settings.

  • Takeaways & Limitations

    The SFRL provides a common representation framework for arbitrary-distribution one-shot coding results and a simple achievability proof of the Gelfand–Pinsker theorem.

Abstract

from arXiv · show

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)\le\log(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.

I. INTRODUCTION

The paper strengthens the functional representation lemma by constructing independent auxiliary randomness Z that represents Y from X while keeping I(X;Z|Y) within a logarithmic bound plus 4 bits. It applies this result to one-shot channel and source coding, and to a simple achievability proof for the Gelfand–Pinsker theorem.

  • Motivation: The functional representation lemma represents Y as a function of X and an auxiliary Z independent of X, but Z need not be unique.Different valid choices of Z can reveal different amounts of information about Y.
  • Motivation: The paper asks whether an independent Z can make H(Y|Z) approach the lower bound I(X;Y).The motivating example shows that one valid representation can attain this lower bound.
  • Main contribution: The strong functional representation lemma guarantees I(X;Z|Y) ≤ log(I(X;Y)+1)+4 bits for arbitrary random variables.Equivalently, H(Y|Z) ≤ I(X;Y)+log(I(X;Y)+1)+4.
  • Applications: The SFRL yields one-shot variable-length achievability results for channel simulation, lossy source coding, multiple description coding, and Gray–Wyner coding.The resulting bounds can be stated using mutual information without information density.
  • Applications: The paper also combines SFRL with Shannon’s channel coding theorem to give a simple achievability proof of the Gelfand–Pinsker theorem.The paper further outlines the organization of its SFRL proof, coding applications, and lower-bound analysis.
  • Main contribution: The result generalizes prior bounds to arbitrary distributions and specifies an additive constant of 4 using a Poisson functional representation construction.The construction replaces the earlier rejection-sampling approach.

Notation

The paper uses base-2 logarithms and measures entropy in bits, with notation distinguishing discrete mass functions, continuous densities, and general probability measures.

  • Notation: Logarithms are base 2, and entropy is measured in bits.
  • Notation: For discrete variables the paper uses pX, for continuous variables fX, and for general variables PX denotes the probability measure induced by X.

II. STRONG FUNCTIONAL REPRESENTATION LEMMA

The SFRL constructs independent Poisson-based randomness Z so that Y is a function of (X,Z), while bounding the conditional dependence I(X;Z|Y) and the residual entropy H(Y|Z).

  • Strong functional representation lemma: Theorem 1 states that for arbitrary Polish-space random variables with finite I(X;Y), Y can be expressed as g(X,Z) for Z independent of X.
  • Strong functional representation lemma: I(X;Z|Y) ≤ log(I(X;Y)+1)+4.
  • Strong functional representation lemma: For discrete X and Y, the auxiliary variable satisfies |Z| ≤ |X|(|Y|−1)+2.
  • Conditional extension: Conditionally, SFRL gives Z independent of (X,U) with I(X;Z|Y,U) ≤ log(I(X;Y|U)+1)+4.The stronger joint independence is obtained by representing an intermediate auxiliary variable using fresh randomness independent of U.
  • Strong functional representation lemma: H(Y|Z) ≤ I(X;Y)+log(I(X;Y)+1)+4.Because Z is independent of X and Y is determined by (X,Z), this expresses the residual entropy of Y in terms of mutual information.
  • Poisson functional representation: The Poisson representation takes a marked Poisson point process Z={(Ỹi,Ti)} and selects an output through a function gX→Y(X,Z).For continuous examples, the construction selects the first point after scaling the conditional density relative to the marginal distribution.
  • Proof and coding interpretation: The proof bounds the selected index K using conditional relative entropy and entropy maximization, then encodes K with a Zipf-distribution prefix code.The expected codeword length is at most I(X;Y)+log(I(X;Y)+1)+5.

III. ONE-SHOT CHANNEL SIMULATION

The SFRL converts arbitrary one-shot channel simulation into prefix coding using common randomness Z, achieving an expected length within a logarithmic overhead of mutual information.

  • Problem setup: One-shot channel simulation seeks the minimum noiseless communication needed to simulate PY|X with unlimited shared randomness.
  • Bounds: The converse gives E[L(M)] ≥ I(X;Y), while prior discrete achievability bounds used an unspecified additive constant.
  • SFRL construction: The SFRL applies to arbitrary channels and provides Z independent of X with H(Y|Z) ≤ I(X;Y)+log(I(X;Y)+1)+4.
  • Achievability: Using Z as common randomness and a Huffman code for pY|Z, the scheme achieves E[L(M)] ≤ I(X;Y)+log(I(X;Y)+1)+5.
  • Common randomness: For discrete X and Y, the common-randomness size satisfies log|W| ≤ log(|X|(|Y|−1)+2).
  • Arbitrary-input setting: The Poisson construction also applies when X is an arbitrary channel input, with a Zipf-code parameter chosen using channel capacity.A cardinality bound |Z| ≤ |X||Y|+1 is obtained in that setting.

IV. LOSSY SOURCE CODING

The paper uses the SFRL to establish one-shot achievability results for three lossy source coding settings.

  • The SFRL yields one-shot achievability results for three lossy source coding settings.

A. Lossy source coding

The one-shot variable-length lossy source coding problem seeks short prefix-free descriptions of reproductions under an average distortion constraint. Using the SFRL and prefix coding, the paper obtains mutual-information-based rate guarantees that approach classical asymptotic performance.

  • The problem encodes a reproduction of arbitrary source X with a prefix-free description while constraining expected distortion.The expected description length is R̄, and the distortion constraint is E[d(X,Ỹ)]≤D.
  • Theorem 2 characterizes achievable expected length-distortion pairs through a mutual-information-based condition.
  • The proof applies the SFRL, selects a deterministic or two-point mixture satisfying rate and distortion constraints, and then uses a Huffman code.Carathéodory’s theorem supplies a mixture between two points when one point cannot satisfy both constraints simultaneously.
  • The achievability proof uses a stochastic encoder, but randomization between only two deterministic encoding functions suffices for Theorem 2.
  • R̄*(D)≤R(D)+log(R(D)+1)+6, so one-shot expected description length remains close to the asymptotic rate-distortion function.For R(D)=100, the paper states that R̄*(D) cannot be at least 113.
  • The construction can be viewed as soft random coding, where an infinite weighted sequence acts as a codebook and the selected index is prefix-coded.The scheme fixes the likelihood encoder’s randomness as part of the codebook.
  • Variable-length coding achieves the same (1+o(1))(1/n)log n redundancy as a finite-blocklength result under expected distortion rather than sure distortion.
  • The result also supports the asymptotic lossy source coding theorem when a reproduction symbol has finite distortion for every source symbol.

B. Multiple Description Coding

The SFRL gives a one-shot inner bound for variable-length multiple description coding. The resulting rate region provides alternative asymptotic achievability proofs, with only additive terms that do not affect asymptotic rates.

  • B. Multiple Description Coding: The scheme produces three prefix-free descriptions for reconstructions at two individual decoders and one central decoder under three distortion constraints.
  • B. Multiple Description Coding: Theorem 3 gives achievability conditions for (R̄1,R̄2,D0,D1,D2) in terms of mutual informations and SFRL overheads.The displayed constraints include individual-rate bounds and a sum-rate bound.
  • B. Multiple Description Coding: The region differs from the Zhang-Berger inner bound only by η, which grows like log n for X^n and does not affect asymptotic rate.
  • B. Multiple Description Coding: Time sharing between two corner points incurs a penalty of at most 1 bit, represented using the first bits of the descriptions.
  • B. Multiple Description Coding: The proof applies the SFRL successively to U, Y1 conditioned on U, Y2 conditioned on U, and Y0 conditioned on (Y1,Y2,U).
  • B. Multiple Description Coding: Carathéodory’s theorem reduces the auxiliary time-sharing variable to cardinality at most 7, after which Huffman codes encode the descriptions.

C. Lossy Gray–Wyner System

The SFRL yields a one-shot inner bound for lossy Gray–Wyner coding, with logarithmic overheads beyond the mutual-information terms. These overheads grow like log n for blocklength-n sources and do not affect asymptotic rates.

  • Theorem 4 establishes achievability for the lossy Gray–Wyner tuple under suitable auxiliary distributions and distortion constraints.
  • The common-description rate satisfies R̄0 ≥ I(X1, X2; U) + log(I(X1, X2; U) + 1) + 8.
  • The only difference from the asymptotic lossy Gray–Wyner region is the addition of logarithmic terms, which do not affect the asymptotic rate.
  • The one-shot construction applies the SFRL successively to U, Y1 conditioned on U, and Y2 conditioned on U, then uses Huffman codes for the resulting variables.
  • The shared message concatenates a 3-bit index with a conditional Huffman code, yielding expected length I(X1, X2; U) + log(I(X1, X2; U) + 1) + 8.

V. ACHIEVABILITY OF GELFAND–PINSKER

The paper proves Gelfand–Pinsker achievability by applying the SFRL to orthogonalize the auxiliary input and state. This produces a point-to-point channel whose achievable rate approaches I(U;Y) − I(U;S).

  • The target Gelfand–Pinsker capacity is CGP = max pU|S, x(u,s) (I(U; Y) − I(U; S)).
  • Applying the SFRL to S and U produces V independent of S with H(U | V) ≤ I(U; S) + log(I(U; S) + 1) + 4.
  • The construction yields a memoryless point-to-point channel pY|V with achievable rate close to I(U;Y) − I(U;S).
  • For n channel uses, the induced channel satisfies I(V;Y^n) ≥ nI(U;Y) − nI(U;S) − log(nI(U;S) + 1) − 4.
  • Using this channel l times and letting l, then n, grow establishes rates below CGP with vanishing error probability.
  • The reduction orthogonalizes the auxiliary input and state and can support code design for channels with state based on point-to-point codes.

VI. LOWER BOUND AND PROPERTIES OF I(X; Z|Y )

The paper studies excess functional information Ψ(X → Y), an equivalent formulation of the SFRL overhead, and develops lower bounds, tightness results, and structural properties. These include alternative characterizations, monotonicity, data processing, conditioning, and successive minimization.

  • The SFRL is equivalently Ψ(X → Y) ≤ log(I(X;Y) + 1) + 4, and the section establishes a lower bound on Ψ.
  • For binary Y, the lower-bound inequality is tight and the infimum is attained by the Poisson functional representation.
  • The SFRL bound is tight within 5 bits for a sequence of distributions with arbitrarily large mutual information.
  • Alternative characterization: The quantity Ψ(X → Y) equals the infimum of H(Y|Z) − I(X;Y) over Z independent of X.
  • Monotonicity: Ψ is monotone under the stated conditional-independence relation and remains unchanged when an independent component pair is appended.
  • Upper bound by common entropy: Ψ is bounded by common entropy minus mutual information, and hence by min{H(X|Y), H(Y|X)}.
  • Successive minimization: Ψ admits successive minimization as infimum over independent V of I(X;V|Y) + Ψ(X → Y | V).
  • When Ψ(X,Y)=0, one-shot zero-error channel coding can communicate a message with entropy at least I(X;Y) under the specified input distribution.

A. Proof of Theorem 1

The proof constructs the functional representation through a Poisson point process and bounds the entropy of the selected index. This yields the SFRL inequality with an additive constant below 4 and establishes finite-cardinality reductions.

  • Conditioning on X=x, the Poisson construction produces Y with distribution PY|X(·|x).
  • The conditional entropy H(Y | {(Ỹi, Ti)}) is bounded by the entropy of the selected Poisson index K.
  • The index satisfies K − 1 = |{i : Ti < TK}|, enabling a Poisson-distribution bound on its entropy.
  • The entropy calculation gives H(Y|Z) < I(X;Y) + log(I(X;Y) + 1) + 4.
  • For finite alphabets, the auxiliary variable can first be restricted to at most |Y|^|X| values before further reduction by Carathéodory-type theorems.

B. Proof of the Bound on Entropy in Theorem 1

The section proves an entropy upper bound for positive-integer-valued Θ using a maximum-entropy argument, then describes a corresponding Zipf-code implementation and a related Ψ(X → Y) bound.

  • Maximum-entropy proof: The proof uses a power-law distribution q(θ) = cθ^−λ with λ = 1 + 1/E[log Θ].The normalizing constant c is selected so that q is a probability distribution.
  • Entropy bound: H(Θ) ≤ E[log Θ] + log(E[log Θ] + 1) + 1 for Θ ∈ {1, 2, ...}.This is stated as Proposition 4.
  • Implementation: Operationally, Θ is encoded with the optimal prefix-free code for the Zipf distribution q(θ).
  • Related bound: Ψ(X → Y) is lower-bounded by log(I(X; Y) + 1) − 1 in the stated modular construction.The construction takes X uniformly and independently of V, sets Y = (X + V) mod 2^k, and derives Ψ(X → Y) ≥ 2H(V) − log γ before the final bound.
Loading 1701.02827v4…