PaperlayerView exact revision on arXiv

Source-linked AI summary

On the Dispersions of Three Network Information Theory Problems

Vincent Y. F. Tan, Oliver Kosut

arXiv:1201.3901v3cs.IT

TL;DR

The paper studies how quickly finite-blocklength rates converge to asymptotic limits in Slepian-Wolf coding and related multi-user problems. It develops dispersion-matrix analyses and unified proofs, showing that corner-point behavior requires bivariate Gaussian characterizations and off-diagonal dispersion terms.

  • Problem

    The paper asks how quickly achievable rates in distributed lossless source coding approach asymptotic Slepian-Wolf limits as blocklength grows.

  • Method

    The paper uses Gaussian approximations, multidimensional Berry-Esséen bounds, random binning, and a vector rate redundancy theorem to derive dispersion results and related inner bounds.

  • Results

    At Slepian-Wolf corner points, local and weighted sum-rate dispersions require a bivariate Gaussian and off-diagonal dispersion-matrix elements rather than scalar dispersions alone.

  • Takeaways & Limitations

    Dispersion matrices provide a network-level description of finite-blocklength rate behavior and extend the achievability analysis to multiple-access and asymmetric broadcast channels.

Abstract

from arXiv · show

We analyze the dispersions of distributed lossless source coding (the Slepian-Wolf problem), the multiple-access channel and the asymmetric broadcast channel. For the two-encoder Slepian-Wolf problem, we introduce a quantity known as the entropy dispersion matrix, which is analogous to the scalar dispersions that have gained interest recently. We prove a global dispersion result that can be expressed in terms of this entropy dispersion matrix and provides intuition on the approximate rate losses at a given blocklength and error probability. To gain better intuition about the rate at which the non-asymptotic rate region converges to the Slepian-Wolf boundary, we define and characterize two operational dispersions: the local dispersion and the weighted sum-rate dispersion. The former represents the rate of convergence to a point on the Slepian-Wolf boundary while the latter represents the fastest rate for which a weighted sum of the two rates converges to its asymptotic fundamental limit. Interestingly, when we approach either of the two corner points, the local dispersion is characterized not by a univariate Gaussian but a bivariate one as well as a subset of off-diagonal elements of the aforementioned entropy dispersion matrix. Finally, we demonstrate the versatility of our achievability proof technique by providing inner bounds for the multiple-access channel and the asymmetric broadcast channel in terms of dispersion matrices. All our proofs are unified a so-called vector rate redundancy theorem which is proved using the multidimensional Berry-Esseen theorem.

I. INTRODUCTION

The paper studies finite-blocklength dispersion for Slepian-Wolf coding, the multiple-access channel, and the asymmetric broadcast channel. It introduces matrix-valued and operational dispersions to describe convergence toward multi-user fundamental limits.

  • The paper analyzes second-order behavior for distributed lossless source coding, the multiple-access channel, and the asymmetric broadcast channel.
  • A. Summary of Main Results: The global Slepian-Wolf result uses a multidimensional Gaussian distribution with covariance matrix V to describe rate-region backoff from the asymptotic optimum.The set S(V, ϵ) is the multivariate-Gaussian analogue of a cumulative distribution function.
  • A. Summary of Main Results: Local and weighted sum-rate dispersions quantify how the finite-blocklength region approaches selected Slepian-Wolf boundary points and weighted asymptotic limits.At corner points, local dispersion requires a bivariate Gaussian and off-diagonal entries of V; at non-corner points, a diagonal entry suffices.
  • A. Summary of Main Results: The same achievability technique yields second-order inner bounds for the discrete memoryless multiple-access and asymmetric broadcast channels.These bounds are also expressed using dispersion matrices.
  • A. Summary of Main Results: For Slepian-Wolf coding, the finite-blocklength rate region is characterized up to an O(log n/n) correction, specifying the O(1/sqrt(n)) constants through a dispersion matrix.The characterization gives a tight second-order result because the inner and outer bounds differ by O(log n/n).

A. Definitions

The paper defines finite-blocklength Slepian-Wolf coding, its optimal rate region, and two operational dispersions describing convergence toward the asymptotic boundary.

  • Assumptions: The model assumes finite alphabets, i.i.d. source pairs with full support, dependent sources, and error probability 0 < ε < 1.
  • Definitions: An (n, ε)-achievable rate pair is supported by a length-n Slepian-Wolf code whose reconstruction error probability is at most ε.
  • Definitions: The optimal rate region collects all (n, ε)-achievable rate pairs, while weighted sum-rate achievability minimizes αR1 + βR2 over that region.
  • Operational dispersions: Local dispersion measures convergence to a boundary point from a specified angle, whereas weighted sum-rate dispersion measures convergence of a weighted rate sum.
  • Gaussian approximation: The Gaussian set S(V, ε) is defined through a possibly degenerate multivariate Gaussian and is used to specify finite-blocklength rate-region bounds.
  • Dispersion quantities: The entropy dispersion matrix V is the covariance matrix of the entropy-density vector and generalizes scalar dispersion to three rate coordinates.

B. Main Results and Interpretation

The main results characterize global, local, and weighted sum-rate dispersions for Slepian-Wolf coding using a dispersion matrix and Gaussian approximations.

  • Global dispersion: The global Slepian-Wolf dispersion theorem characterizes the finite-blocklength optimal rate region through a multivariate Gaussian set involving the dispersion matrix V.
  • Proof technique: The inner bound is universally attainable because the coding scheme does not require knowledge of the source statistics.
  • Local dispersion: Local dispersion has distinct characterizations for vertical, horizontal, sum-rate, and corner boundaries, depending on the approach angle and boundary point.
  • Weighted sum-rate dispersion: The weighted sum-rate dispersion theorem characterizes the fastest convergence of αR1 + βR2, with separate minimization constraints depending on whether α ≥ β or α < β.
  • Proof technique: The achievability proof combines random binning, minimum empirical entropy decoding, and multidimensional Berry-Esseen bounds through a reusable vector rate redundancy theorem.

1) Discussion of Theorem 1:

Theorem 1 models finite-blocklength Slepian-Wolf behavior through a multivariate Gaussian entropy vector with covariance matrix V. The resulting region agrees with simpler decoupled bounds except at corner points, where local and weighted-sum dispersions depend on joint Gaussian behavior and off-diagonal entries of V.

  • Theorem 1: The empirical entropy vector is asymptotically multivariate Gaussian with mean H and covariance V, yielding the second-order terms in the Slepian-Wolf region.The converse uses an information-spectrum theorem, while the result extends naturally to more than two senders.
  • Comparison with Polygonal Region: The decoupled side-information and single-user constraints form outer bounds, but Theorem 2 shows they differ from the full Slepian-Wolf region only at the two corner points.Away from the corners, the simplified and full regions coincide to the stated finite-blocklength order.
  • Corner points: At a corner, local dispersion requires a bivariate Gaussian and off-diagonal entries of V because marginal, sum-rate, and correlation contributions interact.The relevant terms include V_2,2, V_3,3, and the correlation coefficient ρ_2,3.
  • Corner points: Corner-point local dispersion depends on the error probability ε, unlike the corresponding local dispersions at non-corner boundary points.Figure 3 illustrates this dependence for a specified binary source and corner point.
  • Corner points: The local dispersion varies with approach angle: moderate angles move farther into the finite-blocklength region, while near-boundary approaches can make F diverge or require perturbations larger than O(1/√n).The half-angle is furthest from either boundary, but asymmetry means the smallest dispersion need not occur exactly there.
  • Corner points: The analysis characterizes constants for all O(1/√n) terms but does not resolve trajectories parallel to a boundary, which require moderate-deviations techniques.For such approaches, the relevant local-dispersion expression can become infinite.

4) Singular Entropy Dispersion Matrices:

For singular dispersion matrices, the discrete symmetric binary source reduces the general multivariate formulation to a scalar one. The same dispersion-matrix framework also supplies a global inner bound for the multiple-access channel, though a matching converse remains open.

  • Singular Entropy Dispersion Matrices: For a DSBS, V has rank one and is a scalar multiple of the all-ones matrix, so the three entropy dispersions collapse to the scalar V_ζ.The resulting finite-blocklength region recovers earlier scalar fixed-length results.
  • Singular Entropy Dispersion Matrices: When V is singular, the Gaussian distribution is supported on a lower-dimensional subspace, simplifying the set S(V, ε) and the corner-point formulas.For the DSBS, perfect correlations reduce the bivariate Ψ function to a univariate Q function.
  • Multiple-access channel: The MAC section constructs an inner bound on the finite-blocklength capacity region using coded time-sharing, MMI-like decoding, and a global information-dispersion matrix.The coding scheme achieves average error probability at most ε for sufficiently large n.
  • Multiple-access channel: The MAC result is only an inner bound because a tight global-dispersion converse would require new strong-converse techniques handling time-sharing or convexification.The authors do not pursue the analogous local and sum-rate analyses for the MAC and asymmetric broadcast channel.

B. Main Result and Interpretation

The paper gives dispersion-based inner bounds for the DM-MAC and DM-ABC, using matrix-valued second-order terms to describe finite-blocklength rate losses. For the DM-MAC, the achievability proof uses coded time-sharing and modified MMI decoding, while the DM-ABC uses superposition coding and variant MMI decoding.

  • DM-MAC: The DM-MAC inner bound approaches the usual capacity region at rate O(1/n), with a redundancy set approximating the finite-blocklength loss in three mutual-information quantities.The dispersion matrix couples the three inequalities, and the inner bound is universally attainable with time-sharing support bounded by |Q| ≤ 9.
  • DM-MAC: Coded time-sharing and modified MMI decoding establish the DM-MAC achievability result, with the transmitted-pair non-typicality event dominating the error probability near the boundary.Other competing-codeword error events are negligible relative to the target error probability when operating at high rates.
  • DM-MAC: The DM-MAC converse remains open because existing strong-converse techniques yield outer bounds too loose to match the O(1/n) dispersion term.The main obstacles are dependent Fano-distributions, the need to introduce time-sharing or convexification carefully, and the looseness of blowing-up and wringing arguments.
  • DM-ABC: The DM-ABC model has two messages, with decoder 1 recovering both and decoder 2 recovering only the second, under one joint average-error constraint.The encoder maps both messages to one channel input sequence, while the two decoders observe separate channel outputs.
  • DM-ABC: For the DM-ABC, the paper provides a global dispersion inner bound whose three coupled inequalities depend on an information dispersion matrix for pU,X.The construction uses superposition coding with a variant of MMI decoding and restricts the auxiliary support to |U| ≤ |X| + 6 while preserving I and V.

B. Main Result and Interpretation

The paper develops global and operational dispersion results for network information-theoretic problems, unifying their achievability proofs through a vector rate redundancy theorem. The resulting matrix-valued Gaussian approximations quantify finite-blocklength rate losses and reveal genuinely bivariate behavior at Slepian-Wolf corner points.

  • DM-ABC: The DM-ABC global dispersion inner bound extends the same matrix-based framework to a network with auxiliary random variables and admits local and sum-rate dispersion analyses.Its proof uses the same general strategy as the Slepian-Wolf and DM-MAC results.
  • DM-ABC: For the DM-ABC, constant-composition coding achieves a conditional information dispersion matrix no larger than the unconditional matrix in the positive-semidefinite order.This construction uses fixed-composition cloud centers and conditional satellite shells, so dispersion is not increased.
  • Unified framework: The paper’s central result is a vector rate redundancy theorem that unifies the global dispersion proofs for Slepian-Wolf coding, the DM-MAC, and the DM-ABC.The theorem is proved using multidimensional Berry-Esséen bounds and supports dispersion matrices rather than scalar dispersions.
  • Slepian-Wolf interpretation: At Slepian-Wolf corner points, local and weighted sum-rate dispersions require a bivariate Gaussian and off-diagonal entries of the entropy dispersion matrix.Scalar dispersion quantities do not suffice for these approaches to the boundary.
  • Proof framework: The vector rate redundancy proof applies Taylor expansion to a smooth function of the empirical type and then uses multidimensional Berry-Esséen approximation, including a reduction for singular covariance matrices.The argument controls the second-order residual and handles both positive-definite and singular dispersion matrices.

B. Proof of the Global Dispersion for the SW Problem (Theorem 1)

The achievability proof for the Slepian-Wolf global dispersion result uses universal random binning and empirical-entropy decoding. Error events are controlled through type counting and the vector rate redundancy theorem, yielding a deterministic code within the inner bound.

  • Achievability construction: The proof generates independent random bins for both sources and decodes the unique bin-compatible sequence pair whose empirical entropy vector lies in a rate-dependent typical set.The decoder is universal because it does not require knowledge of the true joint source distribution.
  • Error analysis: The ensemble error probability is decomposed into four events covering incorrect replacements of source 1, source 2, or both sources.The proof bounds these events separately after conditioning on the transmitted source sequences.
  • Gaussian approximation: The vector rate redundancy theorem is applied to the negative joint entropy function, with covariance equal to the entropy dispersion matrix.A Gaussian vector threshold is selected so that its probability is at least 1 − ǫ, while logarithmic slack controls the finite-blocklength remainder.
  • Conclusion: The averaged random-binning error probability is bounded by the target error level for sufficiently large n, so a deterministic code exists with the same guarantee.This converts the random-coding estimate into the stated Slepian-Wolf achievability result.

2) Converse:

The converse proof applies a nonasymptotic entropy constraint to every Slepian-Wolf code and approximates the resulting entropy-density vector with a multidimensional Gaussian. This yields an outer bound expressed through the same dispersion matrix used in the achievability analysis.

  • Converse inequality: Every length-n Slepian-Wolf code must satisfy an entropy-density constraint involving the two individual rates and their sum.The converse begins from a general strong-converse inequality and specializes it to the memoryless source setting.
  • Gaussian approximation: Memorylessness expresses the entropy-density vector as a sum of i.i.d. random vectors with covariance given by the entropy dispersion matrix.This representation enables a multidimensional Berry-Esséen approximation.
  • Technical conditions: The proof assumes positive-definite dispersion initially, handles the singular case as in the vector rate redundancy theorem, and uses a logarithmic slack parameter.The third-moment condition is uniformly bounded, allowing the Berry-Esséen bound to control the approximation error.
  • Conclusion: The resulting Gaussian probability constraint places the rate pair in the converse region, completing the dispersion-type outer bound.A smaller auxiliary error level produces a Gaussian threshold set contained in the target set, which yields the final inclusion.

3) Comments on the proof and Universal Decoding:

The DM-MAC proof uses empirical mutual-information decoding, a vector rate redundancy theorem, and atypicality bounds to establish achievability. A universal decoder avoids requiring channel statistics, while a non-universal alternative permits direct Berry–Esseen analysis.

  • Universal decoding: Universal decoding uses empirical mutual information without channel knowledge, whereas information-density decoding can be analyzed directly as a normalized sum of i.i.d. random vectors.The latter does not require the Taylor expansion used in the vector rate redundancy theorem.
  • Cardinality: The DM-MAC proof also restricts the time-sharing alphabet using three mutual informations and six dispersion-matrix entries.A support-lemma argument preserves the three mutual-information quantities, three diagonal variances, and three strict-upper-triangular covariances.
  • DM-MAC achievability: The proof generates conditionally independent codebooks, decodes message pairs using an empirical mutual-information vector, and bounds four error events.The decoding criterion accepts a unique pair whose empirical mutual-information vector exceeds the rate vector by a slack term.
  • Vector rate redundancy: The vector rate redundancy theorem converts Gaussian probability bounds for the information vector into finite-blocklength rate conditions.Its covariance matrix coincides with the information dispersion matrix after differentiating conditional mutual-information quantities.
  • Error analysis: A types-based atypicality lemma controls competing-codeword events by exploiting conditional independence and empirical mutual-information thresholds.The lemma is applied with the competing codeword as X and the remaining channel variables as Y, conditioned on the time-sharing sequence.
  • Achievability conclusion: The average error probability is at most ǫ, so a deterministic DM-MAC code with the desired rates exists.The argument combines the bounds on the individual error events after applying the redundancy and atypicality results.

2) Cardinality Bounds:

The multiple-access and asymmetric broadcast-channel proofs extend the vector rate redundancy approach to universal empirical-mutual-information decoding. Cardinality bounds preserve the relevant mutual informations and dispersion-matrix entries, while achievability follows from error-probability bounds.

  • Universal versus non-universal decoding: A non-universal MAC decoder based on information densities can be analyzed directly as a normalized sum of i.i.d. vectors, avoiding Taylor expansion.The universal decoder instead compares empirical mutual-information vectors and does not require channel-statistics knowledge.
  • Scope and limitation: For the AWGN-MAC, exact-power codebooks may yield smaller dispersion than the i.i.d. codebooks used in the proof.This identifies a setting-dependent limitation of the presented construction rather than a general impossibility result.
  • DM-ABC proof: The DM-ABC proof combines superposition coding with the vector rate redundancy theorem to derive its finite-blocklength inner bound.Cloud centers carry the common message, satellite codewords carry the private message, and the two decoders recover the required message sets.
  • DM-ABC error analysis: The DM-ABC bounds the union of two decoder error events jointly, enabling the vector rate redundancy theorem to operate on a length-3 empirical-mutual-information vector.This differs from the DM-MAC treatment, where the constituent events are bounded separately.
  • DM-ABC achievability: The remaining DM-ABC error events are controlled by the atypicality lemma using conditional independence of satellite codewords given cloud centers.The resulting average error probability is no greater than ǫ, implying existence of a deterministic code with the required performance.
  • Cardinality bounds: The DM-ABC auxiliary alphabet can be bounded by preserving the input distribution, two mutual informations, two variances, and three covariances.The support argument retains the relevant entries of the broadcast-channel dispersion matrix.

APPENDIX A PROOFS OF THE DISPERSIONS FOR SLEPIAN-WOLF

The appendix proves Slepian-Wolf dispersion results through a general Gaussian optimization lemma. Applying it to boundary points, corner points, and weighted sum rates yields the stated local and weighted dispersions.

  • General lemma: A general-purpose lemma bounds the finite-blocklength rate redundancy by optimizing a weighted linear functional over Gaussian probability constraints.The lemma handles nonnegative weights, linear boundary constraints, and asymptotically optimal redundancy vectors.
  • Lemma proof: The proof establishes matching lower and upper bounds on the optimized weighted redundancy, with exponentially decaying approximation terms.Continuity and differentiability of the Gaussian cumulative distribution function control the difference between the auxiliary optimizers.
  • Boundary points: At a non-corner Slepian-Wolf boundary point, the dispersion follows by specializing the lemma to a one-dimensional weighted constraint.The local dispersions at the two corresponding boundary regimes follow by the same argument.
  • Corner points: At a corner point, the relevant Gaussian constraint involves two components, producing a bivariate characterization of the local dispersion.The second corner follows symmetrically from the first corner analysis.
  • Weighted sum rate: For weighted sum-rate dispersion, the cases α ≥ β and β ≥ α are handled by selecting the corresponding Slepian-Wolf corner as an asymptotic optimum.The special cases β = 0, α = 0, and α = β admit alternative optima but yield the same dispersions as the general formulas.

APPENDIX B PROOF OF COROLLARY 8

The appendix proves the Berry–Esseen corollary used by the dispersion analysis through covariance whitening and finite third-moment bounds. The bounds apply uniformly to the Slepian-Wolf, MAC, and asymmetric broadcast settings.

  • Whitening argument: A Cholesky factor transforms the covariance matrix to identity coordinates, allowing the multidimensional Berry–Esseen bound to be applied to convex Borel sets.The transformed variables retain the Gaussian comparison structure while changing the third-moment constant.
  • Berry–Esseen corollary: The proof controls the approximation error by comparing threshold events through auxiliary events and combining the resulting probability bounds.The final inequality follows by combining the two event estimates.
  • Moment bounds: The third moments required by the Slepian-Wolf, MAC, and ABC analyses are uniformly bounded in terms of alphabet cardinalities.The proof uses finiteness of the underlying random-variable ranges and treats the three problems by analogous arguments.
  • MAC moment calculation: For the MAC, the third-moment bound decomposes the information-density vector into components and bounds their norms using convexity and finite-alphabet estimates.The argument controls representative terms such as E[|A1|^3] through mutual-information and alphabet-size quantities.
  • Atypicality bound: For the atypicality lemma, conditional mutual information is bounded by a conditional relative entropy, which then supports a probability tail bound.The Markov-chain structure makes the conditional-information identity available before applying the divergence comparison.
Loading 1201.3901v3…