Comparison of channels: criteria for domination by a symmetric channel

Anuran Makur, Yury Polyanskiy

Abstract

This research establishes a mathematical framework for comparing the "noisiness" of communication channels. By developing rigorous criteria to determine when a general channel is dominated by a $q$-ary symmetric channel, the authors enable the derivation of complex functional inequalities, such as Logarithmic Sobolev Inequalities (LSI), for otherwise intractable systems. The work bridges information theory and functional analysis through the use of $\chi^2$-divergence and matrix analysis.

Introduction

In information theory, comparing two channels to determine which preserves information better is a fundamental challenge. This is typically addressed through preorders like "less noisy" or "degraded" relations. While these concepts are essential for network information theory (such as broadcast channels), they are notoriously difficult to apply in practice because they require optimization over Kullback-Leibler (KL) divergence across all possible input distributions.

This paper, authored by Anuran Makur and Yury Polyanskiy, addresses this gap by extending the logic of channel comparison to $q$-ary symmetric channels—a common and mathematically significant class of noise models. The authors identify simpler, entry-wise matrix criteria that guarantee channel domination, bypassing the need for complex global optimizations.

Methodology

The authors utilize several advanced mathematical tools to simplify the comparison of channel noisiness:

  • $\chi^2$-Divergence Characterization: A pivotal theoretical contribution is proving that the "less noisy" preorder can be perfectly characterized using $\chi^2$-divergence instead of KL divergence. This significantly simplifies analysis as $\chi^2$ is often more mathematically tractable and linear in nature compared to the logarithmic structure of KL divergence.
  • Matrix Minimum-Entry Analysis: The researchers develop a sufficient condition for degradation based solely on the minimum entry ($\nu$) of the channel's stochastic matrix. This allows for quick checks of channel properties without knowing the full transition matrix.
  • Group Theory and Fourier Analysis: For additive noise channels—where noise is added via a group operation—properties of finite Abelian groups and Fourier analysis are used to sharpen the criteria for domination.
A composite channel model where one input is processed by a Binary Symmetric Channel (BSC) before a logical NOR operation.

Key Insights and Ideas

The discovery that $\chi^2$-divergence serves as a complete proxy for KL divergence in the "less noisy" context is a major breakthrough. It suggests that local approximations of divergence can capture the global behavior of channel noisiness.

Furthermore, the "minimum entry" criterion implies that the entire structure of a channel isn't always necessary for comparison; if the "least likely" outcome of a channel is still "likely enough" (exceeding a threshold $\nu$), the channel is mathematically guaranteed to be noisier than a specific symmetric counterpart. This allows complex, non-symmetric channels to "inherit" stability properties, such as LSI constants, from simpler symmetric models. These constants are vital for understanding how quickly information dissipates or how fast Markov chains converge to equilibrium.

Main Results

  1. Theorem 1 (Equivalence): Formally proves that channel $W$ is less noisy than $V$ if and only if the $\chi^2$-divergence at $W$'s output is consistently greater than or equal to that of $V$'s output for any two input distributions.
  2. Theorem 2 (The $\nu$-Criterion): Provides a tight formula for a crossover probability $\delta$ such that a $q$-ary symmetric channel $W_\delta$ is guaranteed to degrade a general channel $V$ based on its minimum entry $\nu$.
  3. Theorem 3 (Additive Noise): Characterizes the "domination regions" for additive noise channels as closed, convex sets that remain invariant under specific permutations.
  4. Theorem 4 & 5 (The LSI Bridge): Establishes that if a symmetric channel dominates channel $V$, then the Dirichlet form of $V$ dominates that of the symmetric channel. This provides a direct path to calculating LSI constants for complex channels using known values from simpler ones.

Conclusion and Future Work

While the minimum-entry criterion is proven to be "tight" for general channels, it can be conservative for specific subclasses. The authors demonstrate that these bounds can be significantly improved for additive noise channels.

Future research may focus on extending these criteria to continuous alphabets, such as Gaussian channels, or exploring non-Abelian group structures. Additionally, while the paper provides a minimax characterization for the maximum domination factor, computing this value exactly for high-dimensional channels remains a significant computational challenge.

Summary updated

Abstract

This paper studies the basic question of whether a given channel $V$ can be dominated (in the precise sense of being more noisy) by a $q$-ary symmetric channel. The concept of "less noisy" relation between channels originated in network information theory (broadcast channels) and is defined in terms of mutual information or Kullback-Leibler divergence. We provide an equivalent characterization in terms of $χ^2$-divergence. Furthermore, we develop a simple criterion for domination by a $q$-ary symmetric channel in terms of the minimum entry of the stochastic matrix defining the channel $V$. The criterion is strengthened for the special case of additive noise channels over finite Abelian groups. Finally, it is shown that domination by a symmetric channel implies (via comparison of Dirichlet forms) a logarithmic Sobolev inequality for the original channel.
BibTeX
@article{makur2016comparison,
  author = {Anuran Makur and Yury Polyanskiy},
  title = {{Comparison of channels: criteria for domination by a symmetric channel}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  doi = {10.1109/tit.2018.2839743},
}
Figure