Source-linked AI summary
Multiterminal Source Coding under Logarithmic Loss
Thomas Courtade, Tsachy Weissman
TL;DR
The paper studies the two-encoder multiterminal source coding problem under logarithmic loss, where soft reconstructions are relevant to learning and estimation. It develops single-letter characterizations for arbitrary finite-alphabet sources and the m-encoder CEO problem, while identifying a boundary for extending the approach beyond two encoders.
Problem
The paper addresses the open characterization of the two-encoder multiterminal rate distortion region for general sources under logarithmic loss.
Method
The paper couples multiterminal source coding to parametrized CEO problems and analyzes soft probability-distribution reconstructions under logarithmic loss.
Results
The paper gives the achievable rate distortion regions for the two-encoder multiterminal and m-encoder CEO problems for arbitrarily correlated finite-alphabet sources.
Takeaways & Limitations
The Berger-Tung inner bound is tight in both settings, and allowing general block reconstructions does not enlarge the CEO rate distortion region.
Takeaways & Limitations
Extending the result to more than two encoders is challenging, and a simple interpolation fix would incorrectly imply Berger-Tung tightness beyond two encoders.
Abstract
from arXiv · showhide
We consider the classical two-encoder multiterminal source coding problem where distortion is measured under logarithmic loss. We provide a single-letter characterization of the achievable rate distortion region for arbitrarily correlated sources with finite alphabets. In doing so, we also give the rate distortion region for the $m$-encoder CEO problem (also under logarithmic loss). Several applications and examples are given.
1 Introduction
The paper addresses a decades-old open problem by characterizing the two-encoder multiterminal source coding rate distortion region for arbitrary finite-alphabet sources under logarithmic loss. It also derives the m-encoder CEO region and establishes tightness of the Berger-Tung inner bound in both settings.
- Open problem: A complete characterization of the two-encoder rate distortion region had remained open for over three decades.
- Prior results: Earlier solutions covered special cases such as lossless coding, side information, Wyner-Ziv coding, and the Berger-Yeung setting.
- Prior results: The quadratic Gaussian case was previously the only setting with a fully known achievable rate distortion region.
- Contributions: The paper determines the achievable rate distortion region for arbitrarily correlated finite-alphabet sources under a specific distortion measure.
- Proof strategy: The argument couples the multiterminal problem to parametrized CEO problems and tunes the CEO parameter to obtain the converse.
- Contributions: Under logarithmic loss, the paper gives single-letter regions for the multiterminal and m-encoder CEO problems, with the Berger-Tung inner bound tight in both settings.
2 Problem Definition
The paper formulates multiterminal source coding with finite-alphabet iid sources, soft probability-distribution reconstructions, and logarithmic-loss distortion. It seeks a single-letter characterization of the resulting achievable rate distortion region using a CEO-problem-based proof roadmap.
- Source model: The sources are iid with finite alphabets and joint pmf p(y1, y2).
- Reproduction model: Each reproduction symbol is a probability distribution over the corresponding source alphabet, so decoding produces soft estimates.
- Distortion measure: Logarithmic loss measures the relative entropy between the empirical event distribution and its estimate.
- Distortion measure: Sequence distortion is defined from symbol-wise logarithmic loss across the block for both sources.
- Achievability: A rate distortion vector is defined through blocklength-n encoding functions and the closure of strictly achievable vectors.
- Proof roadmap: The paper's goal is a single-letter characterization of the achievable region, using a parametrized CEO problem whose parameter is tuned for the converse.
3 The CEO problem
The CEO problem is analyzed under logarithmic loss using a Berger–Tung inner bound and a matching converse, yielding a single-letter rate-distortion characterization. The converse remains valid for arbitrary reproduction distributions, while product distributions are sufficient and extend naturally to m encoders.
- Problem setup: The CEO model assumes X is observed through conditionally independent terminals satisfying Y1 ↔ X ↔ Y2, with probabilistic reproductions under logarithmic loss.The reproduction alphabet consists of probability distributions over the source alphabet.
- Inner bound: The Berger–Tung inner bound specializes to logarithmic loss through the constraint D ≥ H(X|U1, U2, Q).The corresponding auxiliary distribution factors as p(x)p(y1|x)p(y2|x)p(u1|y1,q)p(u2|y2,q)p(q).
- Matching outer bound: The matching converse gives the CEO rate constraints R1 ≥ I(Y1; U1|X,Q) + H(X|U2,Q) − D, R2 ≥ I(Y2; U2|X,Q) + H(X|U1,Q) − D, and R1 + R2 ≥ I(U1;Y1|X,Q) + I(U2;Y2|X,Q) + H(X) − D.It also requires D ≥ H(X|U1,U2,Q) for a compatible joint distribution.
- Characterization: The achievable CEO region is the convex hull of rate-distortion points generated by the allowed auxiliary distributions.Timesharing supplies the convexification step in the characterization.
- Extensions and example: For m encoders, the CEO characterization extends beyond the two-encoder setting, and the binary symmetric-channel example shows rate gains depend on observation quality.When α = 0.01, a small rate increase yields a large relative improvement; when α = 0.25, a larger increase is needed for appreciable improvement.
- Stronger converse: The converse remains valid when block reproductions are arbitrary distributions rather than product distributions, and product distributions are nevertheless sufficient to achieve the full region.The minimum distortion is attained by estimating each source symbol separately.
4 Multiterminal Source Coding
The paper characterizes the multiterminal rate distortion region under logarithmic loss through Berger-Tung achievability and a matching converse, with applications to estimation, betting, and list decoding.
- Inner bound: The inner region is defined by auxiliary variables with the Berger-Tung factorization and conditional-entropy distortion constraints.The construction uses p(y1,y2)p(u1|y1,q)p(u2|y2,q)p(q), with D2 ≥ H(Y2|U1,U2,Q).
- Matching converse: Theorem 6 establishes that the inner region equals the achievable multiterminal rate distortion region.The proof first shows achievability and then proves the reverse inclusion using a tuned CEO argument.
- Matching converse: The converse couples the multiterminal problem to a CEO problem by introducing X=(YB,B), where B is independent Bernoulli and Y1 ↔ X ↔ Y2.The parameter t is tuned through continuity and timesharing to obtain a distribution satisfying both conditional-entropy constraints.
- Stronger converse: A strengthened converse remains valid when each reproduction is any probability measure on Y_i^n rather than a product distribution.An alternative proof uses the Csiszár sum identity, while the original proof uses CEO tuning and Lemma 7.
- Applications: The results imply applications to estimation, horse racing, and list decoding, including equivalence between 2-list decoding and logarithmic-loss multiterminal coding.For estimating (Y1,Y2), the region reduces to Slepian-Wolf constraints with each rate relaxed by D.
5 Relationship to the General Multiterminal Source Coding Problem
The paper relates logarithmic-loss coding to general distortion measures by deriving an outer bound over the same distributions as Berger-Tung and quantifying its gap for binary Hamming sources.
- General distortion measures: The general distortion problem is converted into logarithmic-loss coding through functions defined on reproduction sequences and an induced sequence distortion.The framework allows arbitrary reproduction alphabets and generic distortion measures.
- Binary Hamming distortion: For α-scaled Hamming distortion on binary sources, β_i(R1,R2,D1,D2)=log(1+2^-α) for every rate-distortion tuple.This constant behavior extends to distortion matrices whose columns are permutations of one another.
- Binary erasure distortion: For binary erasure distortion, β_i(R1,R2,D1,D2)=0 for every rate-distortion tuple.The result extends to larger alphabets by assigning penalty log |Y_i| to the erasure symbol.
- Outer bound: Theorem 9 gives rate and distortion inequalities over the Berger-Tung distribution family, with distortion penalties β_i(R1,R2,D1,D2).The rate constraints are mutual-information bounds, while each distortion is bounded by conditional entropy minus β_i.
- Outer bound: The outer bound is defined over the same probability distributions as Berger-Tung, although computing β_i can be difficult in general.The paper shows that β_i is readily determined for many popular distortion measures.
- Binary Hamming distortion: For binary Hamming sources, the Berger-Tung scheme yields a quantitative approximation to the general rate distortion region, with the stated worst-case gap below 0.161.The estimate can potentially improve when more is known about the source distribution.
6 Concluding Remarks
The paper identifies two distinct extension boundaries: CEO results extend to arbitrary encoders, while the two-encoder multiterminal result does not straightforwardly generalize beyond two encoders.
- The CEO results extend to an arbitrary number of encoders, with the extension proved in Appendix B.
- Generalizing the two-encoder multiterminal source-coding results to more than two encoders poses a significant challenge.The proof would require a higher-dimensional interpolation argument, and a simple fix would incorrectly imply tightness of the Berger–Tung inner bound.
A Cardinality Bounds on Auxiliary Random Variables
The cardinality analysis bounds auxiliary alphabets by the corresponding observation alphabets and uses timesharing and convexity arguments to control the resulting regions.
- The framework defines rate-distortion vectors through auxiliary variables satisfying subset rate inequalities and reconstruction mappings.The construction applies to arbitrary joint source-observation distributions and arbitrary distortion measures.
- Every extreme point of A⋆ admits auxiliary variables U1, …, Um with |Uj| ≤ |Yj| for each encoder.
- The CEO cardinality bounds follow by specializing the general framework with L = 1, V = X, and V̂1 = X̂.
- Timesharing between extreme points preserves the bounded auxiliary alphabets, while Caratheodory’s theorem bounds the number of points needed in convex combinations.
- For the two-encoder multiterminal problem, the same argument uses L = m = 2, V = (Y1, Y2), and V̂j = Ŷj.
B Extension of CEO Results to m Encoders
Appendix B extends the CEO characterization to m encoders by combining subset rate constraints with supermodular-polyhedron geometry and a coding construction for every extreme point.
- The appendix generalizes the two-encoder CEO theorems to m encoders, with the proofs described as extensions of the two-encoder arguments.
- The m-encoder CEO inner region consists of rate-distortion vectors satisfying subset inequalities involving I(Ui; Yi|X, Q) and H(X|UIc, Q) − D.
- The proof forms a polytope from the rate inequalities and reduces achievability to showing that each extreme point is dominated by a CEO-achievable rate vector.
- The relevant set functions are supermodular, allowing extreme points to be greedily computed from encoder orderings.
- For every extreme point, a time-sharing coding scheme achieves distortion no greater than D, proving the m-encoder extension.
- The auxiliary alphabets can satisfy |Uj| ≤ |Yj|, while the timesharing variable requires |Q| ≤ m + 2.
C Supermodular Functions
The appendix establishes supermodularity of the set functions underlying the CEO extension and invokes the associated greedy extreme-point characterization.
- The appendix reviews supermodularity and its role in the submodular optimization used to prove the CEO extension.
- A greedy algorithm enumerates every extreme point of a supermodular polyhedron by considering all linear orderings of its elements.
- For the CEO distribution and fixed D, f(I) is defined from conditional mutual information and the conditional entropy gap.
- Both f and f+ = max{f, 0} are supermodular functions.
- The proof derives supermodularity of f using conditional independence, the chain rule, and the fact that conditioning reduces entropy.
- The truncation f+ remains supermodular after considering the sign cases for f over intersections and unions of sets.
D Amplifying a Pointwise Convexity Constraint
Lemma 7 converts a pointwise convexity condition along a continuous path into the existence of a single parameter satisfying both target inequalities. Its proof uses compactness, fine partitioning, and a continuity argument, with Figure 5 illustrating the geometric conclusion.
- Lemma 7 setup: Lemma 7 assumes continuous f1 and f2 on a compact domain K and a function h satisfying the pointwise inequality in (40).The domain need not be connected, and h may be arbitrarily complicated.
- Coding application: In the coding converse, K is a closed subset of a finite-dimensional probability simplex and f1 and f2 are conditional entropies.This lemma is crucial for establishing the converse under logarithmic loss.
- Proof construction: The proof partitions [0,1] finely, defines piecewise-linear interpolants g1 and g2, and uses boundedness of f1 and f2 to control interpolation errors.The partition includes both endpoints and has sufficiently small interval width.
- Existence conclusion: Continuity and endpoint inequalities imply that some t∗ simultaneously satisfies the desired bounds on f1 and f2.The argument rules out simultaneous violation for every t and then invokes compactness through a convergent subsequence.
- Geometric interpretation: Figure 5 depicts the path ϕ(t)=(g1(t),g2(t)) entering the lower-left region because it avoids the shaded area while meeting the endpoint conditions.The figure presents the argument as a variation on the intermediate value theorem.
E Strengthening the Converse of Theorem 6
The strengthened converse shows that allowing non-product reproduction sequences cannot improve performance over product reproductions. The proof establishes sequence-achievability equivalence with the single-letter region using auxiliary variables, entropy bounds, and Berger–Tung achievability.
- Strengthened converse: Theorem 13 states that every sequence-achievable tuple belongs to the single-letter rate distortion region.The result follows from Theorem 6 and Lemmas 8 and 9.
- Strengthened converse: The strengthened converse permits non-product reproduction sequences without improving performance over decoder reproductions restricted to product distributions.This is the operational interpretation of Theorem 13.
- Converse bounds: Single-letter rate bounds follow by applying entropy identities, conditioning inequalities, Markov relations, and time sharing to the encoder outputs.The resulting constraints include separate bounds for R1 and R2 and a sum-rate bound.
- Achievability: Lemma 9 proves achievability for the resulting polytope by analyzing its extreme points and applying the Berger–Tung scheme.The proof extends achievability from the extreme points to all rate pairs in the polytope.
- Conclusion: Combining the converse and achievability arguments places the sequence-achievable tuple in the rate distortion region defined by the Berger–Tung scheme.The final inclusion is stated after establishing achievability for every point in the polytope.
F A Lemma for the Daily Double
Lemma 10 shows that the infimum of the conditional-entropy objective is attained by an auxiliary distribution whose sum-rate constraint holds with equality. The proof perturbs auxiliary variables while preserving feasibility and uses monotonicity to reach the boundary.
- Lemma statement: For rates satisfying R1 ≤ H(Y1), R2 ≤ H(Y2), and R1 + R2 ≤ H(Y1,Y2), the conditional-entropy infimum is attained.The optimizing distribution belongs to the compact set P(R1,R2).
- Conclusion: Therefore, an attaining distribution exists with R1 + R2 = I(Y1,Y2;U1∗,U2∗|Q∗).This equality is the key structural property established by the lemma.
- Proof cases: An optimizer with zero total conditional entropy already satisfies the sum-rate equality through the mutual-information identity.The proof then considers the remaining positive-entropy case.
- Perturbation argument: When the sum-rate constraint is initially slack, the proof perturbs an auxiliary variable toward the source while maintaining feasibility for sufficiently small perturbations.The perturbation strictly decreases the conditional-entropy objective, contradicting optimality unless a boundary constraint is reached.