An Improved Lower Bound on Cardinality of Support of the Amplitude-Constrained AWGN Channel

1. Problem Statement

The paper investigates the Amplitude-Constrained Additive White Gaussian Noise (AWGN) channel, defined by the input-output relationship $Y = X + Z$, where:

• $X$ is the input random variable subject to a peak-power constraint $|X| \le A$ almost surely.
• $Z$ is a standard normal noise variable ($Z \sim \mathcal{N}(0,1)$) independent of $X$.
• The goal is to determine the channel capacity $C(A) = \max_{X: |X|\le A} I(X; Y)$ and the structure of the capacity-achieving input distribution $P_{X^*}$.

Key Context:

• It is a well-established result (Smith, 1971) that the capacity-achieving distribution $P_{X^*}$ is discrete, symmetric, and has finite support (a finite number of mass points).
• Previous work by Dytso et al. (2018) established that the cardinality of the support, denoted $K = |\text{supp}(P_{X^*})|$, is lower-bounded by $O(A)$ and upper-bounded by $O(A^2)$.
• The Conjecture: Dytso et al. conjectured that the support size scales linearly with the amplitude constraint ($K \sim O(A)$).
• The Gap: While numerical simulations suggested various scalings (e.g., $A^{4/3}$ or $A\sqrt{\log A}$), rigorous non-asymptotic lower bounds were lacking, leaving the linear scaling conjecture unrefuted.

2. Methodology

The authors employ a novel combination of information-theoretic stability, probability wrapping, and approximation theory to derive a tighter lower bound. The proof proceeds in two main logical steps:

A. Quantifying Output Distribution Stability

The authors first establish that the output distribution induced by the capacity-achieving input ($P_{Y^*}$) is extremely close to the output distribution induced by a uniform input ($P_{U+Z}$, where $U \sim \mathcal{U}[-A, A]$).

• Using the KKT conditions for capacity and bounds on mutual information, they prove that the relative entropy (Kullback-Leibler divergence) between these two output distributions is small:
  $$D(P_{U+Z} \| P_{Y^*}) \le O(1/A)$$
• This implies that for large $A$, the optimal output distribution is nearly uniform on $[-A, A]$.

B. The Wrapping Argument and Gaussian Mixture Approximation

To quantify how well a discrete input can approximate a uniform output, the authors introduce a wrapping operation:

• They map the real line to a circle (compact domain $[-\pi, \pi)$) using a modulo operation scaled by $A$.
• Under this mapping, the uniform output distribution becomes a uniform distribution on the circle.
• The problem is transformed into: How well can a finite Gaussian mixture (induced by the discrete input $X$) approximate the uniform distribution on the circle?

C. Best Approximation Theory

The authors leverage recent advances in the theory of best approximation by finite Gaussian mixtures:

• They utilize the trigonometric moment method and properties of the $\chi^2$-divergence.
• They prove that if the input has $K$ mass points, the $\chi^2$-divergence between the wrapped output and the wrapped uniform distribution is lower-bounded by an exponential term involving $K$ and $A$:
  $$\chi^2 \ge \frac{1}{2} \exp\left(-\frac{4\pi^2 K^2}{A^2}\right)$$
• By relating the $\chi^2$-divergence to the relative entropy (using the boundedness of the density), they establish a lower bound on the divergence that depends on $K$.

3. Key Contributions

1. Refutation of Linear Scaling: The paper definitively rules out the conjecture that the support size scales linearly with $A$ ($K \sim O(A)$).
2. New Lower Bound: The authors derive a new, rigorous non-asymptotic lower bound on the support cardinality $K$:
   $$K \ge \frac{A}{2\pi} \sqrt{\log_+\left( c A \right)}$$
   where $c \approx 0.0337$ and $\log_+(x) = \max(\log x, 0)$.
   • Asymptotically, this implies $K = \Omega(A\sqrt{\log A})$.
3. Methodological Innovation: The paper introduces a powerful technique combining wrapping operators with approximation theory on compact domains. This allows the authors to bypass the difficulties of analyzing the non-compact real line directly and utilize sharp bounds on Gaussian mixture approximations.
4. New Properties of Optimal Distributions: The authors derive several new properties of the capacity-achieving output density $f_{X^*+Z}$, including:
   • Bounds on the maximum density value ($\Theta(1/A)$).
   • Tail decay properties outside the interval $[-A, A]$.
   • Uniform bounds on the wrapped density.

4. Main Results

Theorem 1: For the amplitude-constrained AWGN channel with constraint $A$, the cardinality of the support of the capacity-achieving input distribution satisfies:
$$|\text{supp}(P_{X^*})| \ge \max \left\{ \frac{A \sqrt{\log_+(c A)}}{2\pi}, \sqrt{1 + \frac{2}{\pi e}A^2}, 2 \right\}$$

• Significance: For sufficiently large $A$ (specifically $A \gtrsim 3 \times 10^5$), the term $A\sqrt{\log A}$ dominates the previous linear bound $O(A)$.
• Implication: The support size must grow superlinearly with the amplitude constraint.

5. Significance and Future Directions

• Theoretical Impact: This work resolves a long-standing open problem regarding the scaling of the optimal input support. It shifts the theoretical understanding from linear scaling to a superlinear regime, aligning more closely with heuristic arguments (like Zhang's spacing analysis) and some numerical observations, though the exact exponent (e.g., $A\sqrt{\log A}$ vs. $A^{4/3}$) remains an open question.
• Numerical Stability: The paper highlights that previous numerical studies suggesting linear scaling were likely artifacts of numerical instability and algorithmic bias (e.g., in the Blahut-Arimoto algorithm) when dealing with the extreme sensitivity of the optimization problem for large $A$.
• Broader Applications: The methodology of mapping problems to compact domains via wrapping and using Gaussian mixture approximation bounds is proposed as a general tool. The authors suggest it could be applied to:
  • Vector Gaussian channels.
  • Fading channels.
  • The classical problem of estimating a bounded normal mean (least-favorable distributions).

In summary, this paper provides a rigorous mathematical breakthrough, proving that the complexity of the optimal input for the amplitude-constrained AWGN channel grows faster than linearly, specifically at a rate of at least $A\sqrt{\log A}$.