A View of Information-Estimation Relations in Gaussian Networks

Abstract

Relations between estimation and information measures have received considerable attention from the information theory community. One of the most notable such relationships is the I-MMSE identity of Guo, Shamai and Verdú that connects the mutual information and the minimum mean square error (MMSE). This paper reviews several applications of the I-MMSE relationship to information theoretic problems arising in connection with multi-user channel coding. The goal of this paper is to review the different techniques used on such problems, as well as to emphasize the added-value obtained from the information-estimation point of view.

1. Introduction

The connections between information theory and estimation theory go back to the late 1950s in the work of Stam in which he uses the de Bruijn identity [1], attributed to his PhD advisor, which connects the differential entropy and the Fisher information of a random variable contaminated by additive white Gaussian noise. In 1968 Esposito [2] and then in 1971 Hatsell and Nolte [3] identified connections between the Laplacian and the gradient of the log-likelihood ratio and the conditional mean estimate. Information theoretic measure can indeed be put in terms of log-likelihood ratios, however, these works did not make this additional connecting step. In the early 1970s continuous-time signals observed in white Gaussian noise received specific attention in the work of Duncan [4] and Kadota et al. [5] who investigated connections between the mutual information and causal filtering. In particular, Duncan and Zakai (Duncan’s theorem was independently obtained by Zakai in the general setting of inputs that may depend causally on the noisy output in a 1969 unpublished Bell Labs Memorandum (see [6])) [4,7] showed that the input-output mutual information can be expressed as a time integral of the causal minimum mean square error (MMSE). It was only in 2005 that Guo, Shamai and Verdú revealed the I-MMSE relationship [8], which similarly to the de Bruijn identity, relates information theoretic quantities to estimation theoretic quantities over the additive white Gaussian noise channel. Moreover, the fact that the I-MMSE relationship connects the mutual information with the MMSE has made it considerably more applicable, specifically to information theoretic problems.

The I-MMSE type relationships have received considerable attention from the information theory community and a number of extensions have been found. In [9], in the context of multiple-input multiple-output (MIMO) Gaussian channels, it was shown that the gradient of the mutual information with respect to the channel matrix is equal to the channel matrix times the MMSE matrix. In [10] a version of the I-MMSE identity has been shown for Gaussian channels with feedback. An I-MMSE type relationship has been found for additive non-Gaussian channels in [11] and non-additive channels with a well-defined notion of the signal-to noise ratio (SNR) in [12,13,14,15]. A relationship between the MMSE and the relative entropy has been established in [16], and between the score function and Rényi divergence and f-divergence in [17]. The I-MMSE relationship has been extended to continuous time channels in [8] and generalized in [18] by using Malliavin calculus. For other continuous time generalizations the reader is referred to [19,20,21]. Finally, Venkat and Weissman [22] dispensed with the expectation and provided a point-wise identity that has given additional insight into this relationship. For a comprehensive summary of results on the interplay between estimation and information measures the interested reader is referred to [23].

In this survey we provide an overview of several applications of the I-MMSE relationship to multi-user information theoretic problems. We consider three types of applications:

• Capacity questions, including both converse proofs and bounds given additional constraints such as discrete inputs;
• The MMSE SNR-evolution, meaning the behavior of the MMSE as a function of SNR for asymptotically optimal code sequences (code sequences that approach capacity as $n\to \infty$); and
• Finite blocklength effects on the SNR-evolution of the MMSE and hence effects on the rate as well.

Our goal in this survey is both to show the strength of the I-MMSE relationship as a tool to tackle network information theory problems, and to overview the set of tools used in conjunction with the I-MMSE relationship such as the “single crossing point” property. As will be seen such tools lead to alternative and, in many cases, simpler proofs of information theoretic converses.

We are also interested in using estimation measures in order to upper or lower bound information measures. Such bounds lead to simple yet powerful techniques that are used to find “good” capacity approximations. At the heart of this technique is a generalization of the Ozarow-Wyner bound [24] based on minimum mean p-th error (MMPE). We hope that this overview will enable future application of these properties in additional multi-user information theoretic problems.

The outline of the paper is as follows:

• In Section 2 we review information and estimation theoretic tools that are necessary for the presentation of the main results.
• In Section 3 we go over point-to-point information theory and give the following results:
  • In Section 3.1, using the I-MMSE and a basic MMSE bound, a simple converse is shown for the Gaussian point-to-point channel;
  • In Section 3.2, a lower bound, termed the Ozarow-Wyner bound, on the mutual information achieved by a discrete input on an AWGN channel, is presented. The bound holds for vector discrete inputs and yields the sharpest known version of this bound; and
  • In Section 3.3, it is shown that the MMSE can be used to identify optimal point-to-point codes. In particular, it is shown that an optimal point-to-point code has a unique SNR-evolution of the MMSE.
• In Section 4 we focus on the wiretap channel and give the following results:
  • In Section 4.1, using estimation theoretic properties a simple converse is shown for the Gaussian wiretap channel that avoids the use of the entropy power inequality (EPI); and
  • In Section 4.2, some results on the SNR-evolution of the code sequences for the Gaussian wiretap channel are provided, showing that for the secrecy capacity achieving sequences of codes the SNR-evolution is unique.
• In Section 5 we study a communication problem in which the transmitter wishes to maximize its communication rate, while subjected to a constraint on the disturbance it inflicts on the secondary receiver. We refer to such scenarios as communication with a disturbance constraint and give the following results:
  • In Section 5.1 it is argued that an instance of a disturbance constraint problem, when the disturbance is measured by the MMSE, has an important connection to the capacity of a two-user Gaussian interference channel;
  • In Section 5.2 the capacity is characterized for the disturbance problem when the disturbance is measured by the MMSE;
  • In Section 5.3 the capacity is characterized for the disturbance problem when the disturbance is measured by the mutual information. The MMSE and the mutual information disturbance results are compared. It is argued that the MMSE disturbance constraint is a more natural measure in the case when the disturbance measure is chosen to model the unintended interference;
  • In Section 5.4 new bounds on the MMSE are derived and are used to show upper bounds on the disturbance constraint problem with the MMSE constraint when the block length is finite; and
  • In Section 5.5 a notion of mixed inputs is defined and is used to show lower bounds on the rates of the disturbance constraint problem when the block length is finite.
• In Section 6 we focus on the broadcast channel and give the following results:
  • In Section 6.1, the converse for a scalar Gaussian broadcast channel, which is based only on the estimation theoretic bounds and avoids the use of the EPI, is derived; and
  • In Section 6.2, similarly to the Gaussian wiretap channel, we examine the SNR-evolution of asymptotically optimal code sequences for the Gaussian broadcast channel, and show that any such sequence has a unique SNR-evolution of the MMSE.
• In Section 7 the SNR-evolution of the MMSE is derived for the K-user broadcast channel.
• In Section 8, building on the MMSE disturbance problem in Section 5.1, it is shown that for the two-user Gaussian interference channel a simple transmission strategy of treating interference as noise is approximately optimal.

Section 9 concludes the survey by pointing out interesting future directions.

1.1. Notation

Throughout the paper we adopt the following notational conventions:

• Random variables and vectors are denoted by upper case and bold upper case letters, respectively, where r.v. is short for either random variable or random vector, which should be clear from the context. The dimension of these random vectors is n throughout the survey. Matrices are denoted by bold upper case letters;
• If A is an r.v. we denote the support of its distribution by $\mathsf{supp}\left(A\right)$;
• The symbol $|·|$ may denote different things: $\left|\mathbf{A}\right|$ is the determinant of the matrix $\mathbf{A}$, $\left|\mathcal{A}\right|$ is the cardinality of the set $\mathcal{A}$, $\left|X\right|$ is the cardinality of $\mathsf{supp}\left(X\right)$, or $\left|x\right|$ is the absolute value of the real-valued x;
• The symbol $\parallel ·\parallel$ denotes the Euclidian norm;
• $\mathbb{E}[·]$ denotes the expectation;
• $\mathcal{N}({\mathbf{m}}_{\mathbf{X}},{\mathbf{K}}_{\mathbf{X}})$ denotes the density of a real-valued Gaussian r.v. $\mathbf{X}$ with mean vector ${\mathbf{m}}_{\mathbf{X}}$ and covariance matrix ${\mathbf{K}}_{\mathbf{X}}$;
• $X\sim \mathsf{PAM}\left(N,d_{\min \left(X\right)}\right)$ denotes the uniform probability mass function over a zero-mean pulse amplitude modulation (PAM) constellation with $\left|\mathsf{supp}\right(X\left)\right|=N$ points, minimum distance $d_{\min \left(X\right)}$, and therefore average energy $\mathbb{E}\left[X^2\right]=d_{\min \left(X\right)}^2\frac{N^2-1}{12}$;
• The identity matrix is denoted by $\mathbf{I}$;
• The reflection of the matrix $\mathbf{A}$ along its main diagonal, or the transpose operation, is denoted by ${\mathbf{A}}^{\mathsf{T}}$;
• The trace operation on the matrix $\mathbf{A}$ is denoted by $\mathrm{Tr}\left(\mathbf{A}\right)$;
• The order notation $\mathbf{A}⪰\mathbf{B}$ implies that $\mathbf{A}-\mathbf{B}$ is a positive semidefinite matrix;
• $\log (·)$ denotes the logarithm to the base $\mathrm{e}$;
• $[n_1:n_2]$ is the set of integers from $n_1$ to $n_2\ge n_1$;
• For $x\in \mathbb{R}$ we let $⌊x⌋$ denote the largest integer not greater than x;
• For $x\in \mathbb{R}$ we let ${\left[x\right]}^{+}:=\max (x,0)$ and ${\log }^{+}\left(x\right):={\left[\log \left(x\right)\right]}^{+}$;
• Let $f\left(x\right),g\left(x\right)$ be two real-valued functions. We use the Landau notation $f\left(x\right)=O\left(g\right(x\left)\right)$ to mean that for some$c>0$ there exists an $x_0$ such that $f\left(x\right)\le cg\left(x\right)$ for all $x\ge x_0$, and $f\left(x\right)=o\left(g\right(x\left)\right)$ to mean that for every$c>0$ there exists an $x_0$ such that $f\left(x\right)<cg\left(x\right)$ for all $x\ge x_0$; and
• We denote the upper incomplete gamma function and the gamma function by

  $$\begin{array}{cc}\hfill \Gamma \left(x;a\right)& :={\int }_a^{\infty }{t}^{x-1}{e}^{-t}dt,x\in \mathbb{R},a\in {\mathbb{R}}^{+},\hfill \end{array}$$

  (1a)

  $$\begin{array}{cc}\hfill \Gamma \left(x\right)& :=\Gamma \left(x;0\right).\hfill \end{array}$$

  (1b)

2. Estimation and Information Theoretic Tools

In this section, we overview relevant information and estimation theoretic tools. The specific focus is to show how estimation theoretic measures can be used to represent or bound information theoretic measures such as entropy and mutual information.

2.1. Estimation Theoretic Measures

Of central interest to us is the following estimation measure constructed from the $L_p$ norm.

Definition 1.

For the random vector $\mathbf{V}\in {\mathbb{R}}^n$ and $p>0$ let

$$\begin{array}{c}\hfill {\parallel \mathbf{V}\parallel }_p:={\left(\frac{1}{n}\mathbb{E}\left[{\parallel \mathbf{V}\parallel }^p\right]\right)}^{\frac{1}{p}}={\left(\frac{1}{n}\mathbb{E}\left[{\left(\mathrm{Tr}\left(\mathbf{V}{\mathbf{V}}^{\mathsf{T}}\right)\right)}^{\frac{p}{2}}\right]\right)}^{\frac{1}{p}}.\end{array}$$

(2a)

We define the minimum mean p-th error (MMPE) of estimating $\mathbf{X}$ from $\mathbf{Y}$ as

$$\begin{array}{c}\hfill \mathrm{mmpe}\left(\mathbf{X}\right|\mathbf{Y};p)=\underset{f}{\inf }{\parallel \mathbf{X}-f\left(\mathbf{Y}\right)\parallel }_p^p,\end{array}$$

(2b)

where the minimization is over all possible Borel measurable functions $f\left(\mathbf{Y}\right)$. Whenever the optimal MMPE estimator exists, we shall denote it by $f_p\left(\mathbf{X}\right|\mathbf{Y})$.

In particular, for $\mathbf{Z}\sim \mathcal{N}\left(\mathbf{0},\mathbf{I}\right)$ the norm in (2a) is given by

$$\begin{array}{c}\hfill {n\parallel \mathbf{Z}\parallel }_p^p=\mathbb{E}\left[{\left(\sum _{i=1}^n{Z}_i^2\right)}^{\frac{p}{2}}\right]=2^{\frac{p}{2}}\frac{\Gamma \left(\frac{n}{2}+\frac{p}{2}\right)}{\Gamma \left(\frac{n}{2}\right)},\mathrm{for}n\in \mathbb{N},p\ge 0,\end{array}$$

(3)

and for $\mathbf{V}$ uniform over the n dimensional ball of radius r the norm in (2a) is given by

$$\begin{array}{c}\hfill {n\parallel \mathbf{V}\parallel }_p^p=\frac{1}{\mathrm{Vol}\left(B\right(r\left)\right)}\frac{{\pi }^{\frac{n}{2}}}{\Gamma \left(\frac{n}{2}\right)}{\int }_0^r{\rho }^p{\rho }^{n-1}d\rho =\frac{n}{2p+2n}{r}^p,\mathrm{for}n\in \mathbb{N},p\ge 0.\end{array}$$

(4)

We shall denote

$$\begin{array}{c}\hfill \mathrm{mmpe}\left(\mathbf{X}\right|\mathbf{Y};p)=\mathrm{mmpe}(\mathbf{X},\mathsf{snr},p),\end{array}$$

(5)

if $\mathbf{Y}$ and $\mathbf{X}$ are related as

$$\begin{array}{c}\hfill \mathbf{Y}=\sqrt{\mathsf{snr}}\mathbf{X}+\mathbf{Z},\end{array}$$

(6)

where $\mathbf{Z},\mathbf{X},\mathbf{Y}\in {\mathbb{R}}^n$, $\mathbf{Z}\sim \mathcal{N}(\mathbf{0},\mathbf{I})$ is independent of $\mathbf{X}$, and $\mathsf{snr}\ge 0$ is the SNR. When it will be necessary to emphasize the SNR at the output $\mathbf{Y}$, we will denote it by ${\mathbf{Y}}_{\mathsf{snr}}$. Since the distribution of the noise is fixed $\mathrm{mmpe}\left(\mathbf{X}\right|\mathbf{Y};p)$ is completely determined by the distribution of $\mathbf{X}$ and $\mathsf{snr}$ and there is no ambiguity in using the notation $\mathrm{mmpe}(\mathbf{X},\mathsf{snr},p)$. Applications to the Gaussian noise channel will be the main focus of this paper.

In the special, case when $p=2$, we refer to the MMPE as the minimum mean square error (MMSE) and use the notation

$$\begin{array}{c}\hfill \mathrm{mmpe}(\mathbf{X},\mathsf{snr},2)=\mathrm{mmse}(\mathbf{X},\mathsf{snr}),\end{array}$$

(7)

in which case we also have that $f_2\left(\mathbf{X}\right|\mathbf{Y})=\mathbb{E}\left[\mathbf{X}\right|\mathbf{Y}]$.

Remark 1.

The notation $f_p\left(\mathbf{X}\right|\mathbf{Y})$, for the optimal estimator in (2) is inspired by the conditional expectation $\mathbb{E}\left[\mathbf{X}\right|\mathbf{Y}]$, and $f_p\left(\mathbf{X}\right|\mathbf{Y})$ should be thought of as an operator on $\mathbf{X}$ and a function of $\mathbf{Y}$. Indeed, for $p=2$, the MMPE reduces to the MMSE; that is, $\mathrm{mmpe}\left(\mathbf{X}\right|\mathbf{Y};2)=\mathrm{mmse}(\mathbf{X}\left|\mathbf{Y}\right)$ and $f_2\left(\mathbf{X}\right|\mathbf{Y})=\mathbb{E}\left[\mathbf{X}\right|\mathbf{Y}]$.

Finally, similarly to the conditional expectation, the notation $f_p\left(\mathbf{X}\right|\mathbf{Y}=\mathbf{y})$ should be understood as an evaluation for a realization of a random variable $\mathbf{Y}$, while $f_p\left(\mathbf{X}\right|\mathbf{Y})$ should be understood as a function of a random variable $\mathbf{Y}$ which itself is a random variable.

Lemma 1.

(Existence of the Optimal Estimator [25]) For any $\mathbf{X}$ and $\mathbf{Y}$ given by (6) an optimal estimator exists and the infimum in (2) can be attained.

In certain cases the optimal estimator might not be unique and the interested reader is referred to [25] for such examples. In general we do not have a closed form solution for the MMPE optimal estimator in (2). Interestingly, the optimal estimator for Gaussian inputs can be found and is linear for all $p\ge 1$

Proposition 1.

(MMPE of a Gaussian Input [25,26,27]) For ${\mathbf{X}}_G\sim \mathcal{N}(\mathbf{0},\mathbf{I})$ and $p\ge 1$

$$\begin{array}{c}\hfill \mathrm{mmpe}({\mathbf{X}}_G,\mathsf{snr},p)=\frac{{\parallel \mathbf{Z}\parallel }_p^p}{{(1+\mathsf{snr})}^{\frac{p}{2}}},\end{array}$$

(8a)

with the optimal estimator given by

$$\begin{array}{c}\hfill f_p\left({\mathbf{X}}_G\right|\mathbf{Y}=\mathbf{y})=\frac{\sqrt{\mathsf{snr}}\mathbf{y}}{1+\mathsf{snr}}.\end{array}$$

(8b)

Note that unlike the Gaussian case in general the estimator will be a function of the order p. For $X=\pm 1$ equally likely (i.e., binary phase shift keying—BPSK) the optimal estimator is given by

$$\begin{array}{c}\hfill f_p\left(X\right|Y=y)=\tanh \left(\frac{y\sqrt{\mathsf{snr}}}{p-1}\right).\end{array}$$

(9)

Often the MMPE is difficult to compute, even for $p=2$ (MMSE), and one instead is interested in deriving upper bounds on the MMPE. One of the most useful upper bounds on the MMPE can be obtained by restricting the optimization in (2) to linear functions.

Proposition 2.

(Asymptotically Gaussian is the “hardest” to estimate [25]) For $\mathsf{snr}\ge 0$, $p\ge 1$, and a random variable $\mathbf{X}$ such that ${\parallel \mathbf{X}\parallel }_p^p\le {\sigma }^p{\parallel \mathbf{Z}\parallel }_p^p$, we have

$$\begin{array}{cc}\hfill \mathrm{mmpe}(\mathbf{X},\mathsf{snr},p)& \le {\kappa }_{p,{\sigma }^2\mathsf{snr}}·\frac{{\sigma }^p{\parallel \mathbf{Z}\parallel }_p^p}{{(1+\mathsf{snr}{\sigma }^2)}^{\frac{p}{2}}},\hfill \end{array}$$

(10a)

where

$$\begin{array}{cc}\mathit{for}p=2:\hfill & {\kappa }_{p,{\sigma }^2\mathsf{snr}}^{\frac{1}{p}}=1,\hfill \end{array}$$

(10b)

$$\begin{array}{cc}\mathit{for}p\ne 2:\hfill & 1\le {\kappa }_{p,{\sigma }^2\mathsf{snr}}^{\frac{1}{p}}=\frac{1+\sqrt{{\sigma }^2\mathsf{snr}}}{\sqrt{1+{\sigma }^2\mathsf{snr}}}\le 1+\frac{1}{\sqrt{1+{\sigma }^2\mathsf{snr}}}.\hfill \end{array}$$

(10c)

Moreover, a Gaussian $\mathbf{X}$ with per-dimension variance ${\sigma }^2$ (i.e., $\mathbf{X}\sim \mathcal{N}(\mathbf{0},{\sigma }^2\mathbf{I})$) asymptotically achieves the bound in (10a), since ${\lim }_{\mathsf{snr}\to \infty }{\kappa }_{p,{\sigma }^2\mathsf{snr}}=1$.

For the case of $p=2$, the bound in (10a) is achieved with a Gaussian input for all SNR’s. Moreover, this special case of the bound in (10a), namely

$$\begin{array}{c}\hfill \mathrm{mmse}(\mathbf{X},\mathsf{snr})\le \frac{{\sigma }^2}{1+{\sigma }^2\mathsf{snr}},\end{array}$$

(11)

for all ${\parallel \mathbf{X}\parallel }_2^2\le {\sigma }^2$, is referred to as the linear minimum mean square error (LMMSE) upper bound.

2.2. Mutual Information and the I-MMSE

For two random variables $(\mathbf{X},\mathbf{Y})$ distributed according to $P_{\mathbf{X}\mathbf{Y}}$ the mutual information is defined as

$$\begin{array}{c}\hfill I(\mathbf{X};\mathbf{Y})=\mathbb{E}\left[\log \frac{d{P}_{\mathbf{X}\mathbf{Y}}}{d(P_{\mathbf{X}}\times P_{\mathbf{Y}})}\right],\end{array}$$

(12)

where $\frac{d{P}_{\mathbf{X}\mathbf{Y}}}{d(P_{\mathbf{X}}\times P_{\mathbf{Y}})}$ is the Radon-Nikodym derivative. For the channel in (6) the mutual information between $\mathbf{X}$ and $\mathbf{Y}$ takes the following form:

$$\begin{array}{c}\hfill I(\mathbf{X};\mathbf{Y})=\mathbb{E}\left[\log \left(\frac{f_{\mathbf{Y}|\mathbf{X}}\left(\mathbf{Y}\right|\mathbf{X})}{f_{\mathbf{Y}}\left(\mathbf{Y}\right)}\right)\right],\end{array}$$

(13)

and it will be convenient to use the normalized mutual information

$$\begin{array}{c}\hfill I_n(\mathbf{X},\mathsf{snr})=\frac{1}{n}I(\mathbf{X};\mathbf{Y}).\end{array}$$

(14)

The basis for much of our analysis is the fundamental relationship between information theory and estimation theory, also known as the Guo, Shamai and Verdú I-MMSE relationship [8].

Theorem 1.

(I-MMSE [8]) For any $\mathbf{X}$ (independent of $\mathsf{snr}$) we have that

$$\begin{array}{cc}\hfill \frac{d}{d\mathsf{snr}}{I}_n(\mathbf{X},\mathsf{snr})& =\frac{1}{2}\mathrm{mmse}(\mathbf{X},\mathsf{snr}),\hfill \end{array}$$

(15a)

$$\begin{array}{cc}\hfill I_n(\mathbf{X},\mathsf{snr})& =\frac{1}{2}{\int }_0^{\mathsf{snr}}\mathrm{mmse}(\mathbf{X},t)dt.\hfill \end{array}$$

(15b)

In [28] the I-MMSE relationship has been partially extended to the limit as $n\to \infty$. This result was then extended in [29] under the assumption that the mutual information sequence converges.

Proposition 3.

(I-MMSE limiting expression [29]) Suppose that ${\parallel \mathbf{X}\parallel }_2^2\le {\sigma }^2<\infty$ and

$$\begin{array}{c}\hfill \underset{n\to \infty }{\lim }{I}_n(\mathbf{X},\mathsf{snr})=I_{\infty }(\mathbf{X},\mathsf{snr}),\end{array}$$

(16)

exists. (The limit here is taken with respect to a sequence of input distributions over ${\left\{{\mathbf{X}}_n\right\}}_{n\ge 1}$ which induces a sequence of input-output joint distributions. The second moment constraint $\parallel {\mathbf{X}}_n{\parallel }_2^2$ should be understood in a similar manner, as a constraint for every n in the sequence.) Then,

$$\begin{array}{c}\hfill \underset{n\to \infty }{\lim }\mathrm{mmse}(\mathbf{X},\mathsf{snr})={\mathrm{mmse}}_{\infty }(\mathbf{X},\mathsf{snr}),\end{array}$$

(17)

and the I-MMSE relationship holds for the following limiting expression:

$$\begin{array}{c}\hfill I_{\infty }(\mathbf{X},\mathsf{snr})=\frac{1}{2}{\int }_0^{\mathsf{snr}}{\mathrm{mmse}}_{\infty }(\mathbf{X},t)dt.\end{array}$$

(18)

Proof. 

The proof is given in Appendix A.  ☐

Properties of the MMSE, with the specific focus on the I-MMSE identity, as a function of the input distribution and the noise distribution have been thoroughly studied and the interested reader is referred to [17,30,31,32]. For the derivation of the I-MMSE and a comprehensive summary of various extension we refer the reader to [23].

For a continuous random vector $\mathbf{X}$ with the density $f_{\mathbf{X}}$ the differential entropy is defined as

$$\begin{array}{c}\hfill h\left(\mathbf{X}\right)=-\mathbb{E}\left[\log f_{\mathbf{X}}\left(\mathbf{X}\right)\right].\end{array}$$

(19)

Moreover, for a discrete random vector $\mathbf{X}$ the discrete entropy is defined as

$$\begin{array}{c}\hfill H\left(\mathbf{X}\right)=-\sum _{\mathbf{x}\in \mathsf{supp}\left(\mathbf{X}\right)}{p}_{\mathbf{x}}\log p_{\mathbf{x}},\mathrm{where}{p}_{\mathbf{x}}=\mathbb{P}[\mathbf{X}=\mathbf{x}].\end{array}$$

(20)

2.3. Single Crossing Point Property

Upper bounds on the MMSE are useful, thanks to the I-MMSE relationship, as tools to derive information theoretic converse results, and have been used in [23,30,33,34] to name a few. The key MMSE upper bound that will be used in conjunction with the I-MMSE to derive information theoretic converses is the single crossing point property (SCPP).

Proposition 4.

(SCPP [30,33]) Let ${\parallel \mathbf{X}\parallel }_2\le 1$. Then for any fixed ${\mathsf{snr}}_0$ there exists a unique $\alpha \in [0,1]$ such that

$$\begin{array}{c}\hfill \mathrm{mmse}(\mathbf{X},{\mathsf{snr}}_0)=\frac{\alpha }{1+\alpha {\mathsf{snr}}_0}.\end{array}$$

(21a)

Moreover, for every $\mathsf{snr}>{\mathsf{snr}}_0$

$$\begin{array}{c}\hfill \mathrm{mmse}(\mathbf{X},\mathsf{snr})\le \frac{\alpha }{1+\alpha \mathsf{snr}},\end{array}$$

(21b)

and for every $\mathsf{snr}\le {\mathsf{snr}}_0$

$$\begin{array}{c}\hfill \mathrm{mmse}(\mathbf{X},\mathsf{snr})\ge \frac{\alpha }{1+\alpha \mathsf{snr}}.\end{array}$$

(21c)

Even though the statement of Proposition 4 seems quite simple it turns out that it is sufficient to show a special case of the EPI [33]:

$$\begin{array}{c}\hfill {\mathrm{e}}^{\frac{2}{n}h(\mathbf{X}+\mathbf{Z})}\ge {\mathrm{e}}^{\frac{2}{n}h\left(\mathbf{X}\right)}+{\mathrm{e}}^{\frac{2}{n}h\left(\mathbf{Z}\right)},\end{array}$$

(22)

where $\mathbf{Z}\sim \mathcal{N}(\mathbf{0},{\mathbf{R}}_{\mathbf{Z}})$. Interestingly, the I-MMSE appears to be a very powerful tool in deriving EPI type inequalities; the interested reader is referred to [35,36,37,38].

In [25] it has been pointed out that the SCPP upper bound can also be shown for the MMPE as follows.

Proposition 5.

(Generalized SCPP upper bound [25]) Let ${\mathrm{mmpe}}^{\frac{2}{p}}(\mathbf{X},{\mathsf{snr}}_0,p)=\frac{{\beta \parallel \mathbf{Z}\parallel }_p^2}{1+\beta {\mathsf{snr}}_0}$ for some $\beta \ge 0$. Then,

$$\begin{array}{c}\hfill {\mathrm{mmpe}}^{\frac{2}{p}}(\mathbf{X},\mathsf{snr},p)\le c_p·\frac{{\beta \parallel \mathbf{Z}\parallel }_p^2}{1+\beta \mathsf{snr}},\mathrm{for}\mathsf{snr}\ge {\mathsf{snr}}_0,\end{array}$$

(23a)

where

$$\begin{array}{c}\hfill c_p=\left\{\begin{array}{cc}2\hfill & p\ne 2\hfill \\ 1\hfill & p=2\hfill \end{array}\right..\end{array}$$

(23b)

Proof. 

The proof of Propositions 4 and 5 uses a clever choice of a sub-optimal estimator. The interested reader is referred to Appendix B for the proof.  ☐

2.4. Complementary SCPP Bounds

Note that the SCPP allows us to upper bound the MMSE for all values of $\mathsf{snr}\ge {\mathsf{snr}}_0$, and as will be shown later this is a very powerful tool in showing information theoretic converses. Another interesting question is whether we can produce a complementary upper bound to that of the SCPP. That is, can we show an upper bounds on the MMSE for $\mathsf{snr}\le {\mathsf{snr}}_0$? As will be demonstrated in Section 5, such complementary SCPP bounds are useful in deriving information theoretic converses for problems of communication with a disturbance constraint.

The next result shows that this is indeed possible.

Proposition 6.

(Complementary SCPP bound [25]) For $0<\mathsf{snr}\le {\mathsf{snr}}_0$, $\mathbf{X}$ and $p\ge 0$, we have

$$\begin{array}{c}\mathrm{mmpe}(\mathbf{X},\mathsf{snr},p)\le {\kappa }_{n,t}{\mathrm{mmpe}}^{\frac{1-t}{1+t}}\left(\mathbf{X},{\mathsf{snr}}_0,\frac{1+t}{1-t}·p\right),\hfill \\ \mathit{where}{\kappa }_{n,t}:={\left(\frac{2^n}{n^2}\right)}^{\frac{t}{t+1}}{\left(\frac{1}{1-t}\right)}^{\frac{nt}{t+1}-\frac{1}{2}},t=\frac{{\mathsf{snr}}_0-\mathsf{snr}}{{\mathsf{snr}}_0}.\hfill \end{array}$$

An interesting property of the bound in Proposition 6 is that the right hand side of the inequality keeps the channel SNR fixed and only varies the order of the MMPE while the left hand side of the inequality keeps the order fixed and changes the SNR value.

2.5. Bounds on Differential Entropy

Another common application of estimation theoretic measures is to bound information measures. Next, we presented one such bound.

For any random vector $\mathbf{V}$ such that $\left|\mathrm{Cov}\right(\mathbf{V}\left)\right|<\infty ,h\left(\mathbf{V}\right)<\infty ,$ and any random vector $\mathbf{Y}$, the following inequality is considered to be a continuous analog of Fano’s inequality [39]:

$$\begin{array}{cc}\hfill h\left(\mathbf{V}\right|\mathbf{Y})& \le \frac{n}{2}{\log \left(2\pi \mathrm{e}\right|\mathrm{Cov}\left(\mathbf{V}\right|\mathbf{Y})|}^{\frac{1}{n}})\hfill \end{array}$$

(24)

$$\begin{array}{c}\le \frac{n}{2}\log \left(2\pi \mathrm{e}\mathrm{mmse}\left(\mathbf{V}\right|\mathbf{Y})\right),\hfill \end{array}$$

(25)

where the inequality in (25) is a consequence of the arithmetic-mean geometric-mean inequality, that is, for any $0⪯\mathbf{A}$ we have used ${\left|\mathbf{A}\right|}^{\frac{1}{n}}={\left({\prod }_{i=1}^n{\lambda }_i\right)}^{\frac{1}{n}}\le \frac{{\sum }_{i=1}^n{\lambda }_i}{n}=\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{n}$ where ${\lambda }_i$’s are the eigenvalues of $\mathbf{A}$.

The inequality in (25) can be generalized in the following way.

Theorem 2.

(Conditional Entropy Bound [25]) Let $\mathbf{V}\in {\mathbb{R}}^n$ be such that $h\left(\mathbf{V}\right)<\infty$ and ${\parallel \mathbf{V}\parallel }_p<\infty$. Then, for any $p\in (0,\infty )$ and for any $\mathbf{Y}\in {\mathbb{R}}^n$, we have

$$\begin{array}{c}\hfill h\left(\mathbf{V}\right|\mathbf{Y})\le \frac{n}{2}\log \left(k_{n,p}^2·n^{\frac{2}{p}}·{\mathrm{mmpe}}^{\frac{2}{p}}\left(\mathbf{V}\right|\mathbf{Y};p)\right),\end{array}$$

(26)

where $k_{n,p}=\frac{\sqrt{\pi }{\left(\frac{p\mathrm{e}}{n}\right)}^{\frac{1}{p}}{\Gamma }^{\frac{1}{n}}\left(\frac{n}{p}+1\right)}{{\Gamma }^{\frac{1}{n}}\left(\frac{n}{2}+1\right)}$.

While the MMPE is still a relatively new tool it has already found several applications:

• The MMPE can be used to bound the conditional entropy (see Theorem 2 in Section 2.5). These bounds are generally tighter than the MMSE based bound especially for highly non-Gaussian statistics;
• The MMPE can be used to develop bounds on the mutual information of discrete inputs via the generalized Ozarow-Wyner bound (see Theorem 4 in Section 3.2); The MMPE and the Ozarow-Wyner bound can be used to give tighter bounds on the gap to capacity achieved by PAM input constellations (see Figure 2);
• The MMPE can be used as a key tool in finding complementary bounds on the SCPP (see Theorem 10 in Section 5.4). Note that using the MMPE as a tool produces the correct phase transition behavior; and
• While not mentioned, another application is to use the MMPE to bound the derivatives of the MMSE; see [25] for further details.

3. Point-to-Point Channels

In this section, we review Shannon’s basic theorem for point-to-point communication and introduce relevant definitions used throughout the paper. The point-to-point channel is also a good starting point for introducing many of the techniques that will be used in this survey.

A classical point-to-point channel is shown in Figure 1. The transmitter wishes to reliably communicate a message W at a rate R bits per transmission to a receiver over a noisy channel. To that end, the transmitter encodes the message W into a signal $\mathbf{X}$ and transmits it over a channel in n time instances. Upon receiving a sequence $\mathbf{Y}$, a corrupted version of $\mathbf{X}$, the receiver decodes it to obtain the estimate $\widehat{W}$.

Definition 2.

A memoryless channel (MC), assuming no feedback, $(\mathcal{X},P_{Y|X},\mathcal{Y})$ (in short $P_{Y|X}$) consists of an input set $\mathcal{X}$, an output set $\mathcal{Y}$, and a collection of transition probabilities $P_{Y|X}$ on $\mathcal{Y}$ for every $x\in \mathcal{X}$. The transition of a length-n vector $\mathbf{X}$ through such a channel then has the following conditional distribution:

$$\begin{array}{c}\hfill P_{\mathbf{Y}|\mathbf{X}}\left(\mathbf{y}\right|\mathbf{x})=\prod _{i=1}^n{P}_{Y|X}\left(y_i\right|x_i).\end{array}$$

(27)

Definition 3.

A code of length n and rate R, denoted by $(2^{nR},n)$, of the channel $P_{Y|X}$ consist of the following:

• A message set$\{1,2,...,2^{nR}\}$. We assume that the message W is chosen uniformly over the message set.
• An encoding function$\mathbf{X}:\{1,2,...,2^{nR}\}\to {\mathcal{X}}^n$ that maps messages W to codewords $\mathbf{X}\left(W\right)$. The set of all codewords is called the codebook and is denoted by $\mathcal{C}$; and
• A decoding function$g:{\mathcal{Y}}^n\to \{1,2,...,2^{nR}\}$ that assigns an estimate $\widehat{W}$ to each received sequence.

The average probability of error for a $(2^{nR},n)$ code is defined as

$$\begin{array}{c}\hfill \mathbb{P}[\widehat{W}\ne W]=\frac{1}{2^{nR}}\sum _{w=1}^{2^{nR}}\mathbb{P}[\widehat{W}\ne w\mid W=w].\end{array}$$

Definition 4.

A rate R is said to be achievable over a point-to-point channel if there exists a sequence of codes, $(2^{nR},n)$, such that

$$\begin{array}{c}\hfill \underset{n\to \infty }{\lim }\mathbb{P}[\widehat{W}\ne W]=0.\end{array}$$

(28)

The capacity C of a point-to-point channel is the supremum over all achievable rates.

A crowning achievement of Shannon’s 1948 paper [40] is a simple characterization of the capacity of a point-to-point channel.

Theorem 3.

(Channel Coding Theorem [40]) The capacity of the channel $P_{Y|X}$ is given by

$$\begin{array}{c}\hfill C=\underset{P_X}{\max }I(X;Y).\end{array}$$

(29)

For a formal derivation of the capacity expression in (29) the reader is referred to classical texts such as [39,41,42].

3.1. A Gaussian Point-to-Point Channel

In this section we consider the practically relevant Gaussian point-to-point channel shown in Figure 1b and given by

$$\begin{array}{c}\hfill Y=\sqrt{\mathsf{snr}}X+Z,\end{array}$$

(30)

where Z is standard Gaussian noise and there is an additional input power constraint $\mathbb{E}\left[X^2\right]\le 1$. The capacity in this setting was solved in the original paper by Shannon and is given by

$$\begin{array}{c}\hfill C=\frac{1}{2}\log (1+\mathsf{snr}).\end{array}$$

(31)

To show the converse proof of the capacity (the upper bound on the capacity) in (31), Shannon used the maximum entropy principle. In contrast to Shannon’s proof, we show the converse can be derived by using the I-MMSE and the LMMSE upper bound in (11)

$$\begin{array}{cc}\hfill I(X;Y)& =\frac{1}{2}{\int }_0^{\mathsf{snr}}\mathrm{mmse}(X,\gamma )d\gamma \hfill \\ & \le \frac{1}{2}{\int }_0^{\mathsf{snr}}\frac{1}{1+\gamma }d\gamma \hfill \\ & =\frac{1}{2}\log (1+\mathsf{snr}).\hfill \end{array}$$

(32)

It is well know that the upper bound in (32) is achievable if and only if the input is $X\sim \mathcal{N}(0,1)$.

The main idea behind the upper bounding technique in (32) is to find an upper bound on the MMSE that holds for all SNR’s and integrate it to get an upper bound on the mutual information. This simple, yet powerful, idea will be used many times throughout this paper to show information theoretic converses for multi-user channels.

3.2. Generalized Ozarow-Wyner Bound

In practice, Gaussian inputs are seldom used and it is important to assess the performance of more practical discrete constellations (or inputs). Another reason is that discrete inputs often outperform Gaussian inputs in competitive multi-user scenarios, such as the interference channel, as will be demonstrated in Section 7. For other examples of discrete inputs being useful in multi-user settings, the interested readers is referred to [43,44,45,46].

However, computing an exact expression for the mutual information between the channel input and output when the inputs are discrete is often impractical or impossible. Therefore, the goal is to derive a good computable lower bound on the mutual information that is not too far away from the true value of the mutual information. As we will see shortly, estimation measures such as the MMSE and the MMPE will play an important role in establishing good lower bounds on the mutual information.

The idea of finding good capacity approximations can be traced back to Shannon. Shannon showed, in his unpublished work in 1948 [47], the asymptotic optimality of a PAM input for the point-to-point power-constrained Gaussian noise channel. Another such observation about approximate optimality of a PAM input was made by Ungerboeck in [48] who, through numerical methods, observed that the rate of a properly chosen PAM input is always a constant away from the AWGN capacity.

Shannon’s and Ungerboeck’s arguments were solidified by Ozarow and Wyner in [24] where firm lower bounds on the achievable rate with a PAM input were derived and used to show optimality of PAM to within 0.41 bits [24].

In [24] the following “Ozarow-Wyner lower bound” on the mutual information achieved by a discrete input $X_D$ transmitted over an AWGN channel was shown:

$$\begin{array}{c}{[H\left(X_D\right)-\mathsf{gap}]}^{+}\le I(X_D;Y)\le H\left(X_D\right),\hfill \end{array}$$

(33a)

$$\begin{array}{c}\mathsf{gap}\le \frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{6}\right)+\frac{1}{2}\log \left(1+\frac{\mathrm{lmmse}(X,\mathsf{snr})}{d_{\min }{\left(X_D\right)}^2}\right),\hfill \end{array}$$

(33b)

where $\mathrm{lmmse}\left(X\right|Y)$ is the LMMSE. The advantage of the bound in (33) compared to the existing bounds is its computational simplicity. The bound depends only on the entropy, the LMMSE, and the minimum distance, which are usually easy to compute.

The bound in (33) has also been proven to be useful for other problems such as two-user Gaussian interference channels [45,49], communication with a disturbance constraint [50], energy harvesting problems [51,52], and information-theoretic security [53].

The bound on the $\mathsf{gap}$ in (33) has been sharpened in [45] to

$$\begin{array}{c}\hfill \mathsf{gap}\le \frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{6}\right)+\frac{1}{2}\log \left(1+\frac{\mathrm{mmse}(X,\mathsf{snr})}{d_{\min }{\left(X_D\right)}^2}\right),\end{array}$$

(34)

since $\mathrm{lmmse}(X,\mathsf{snr})\ge \mathrm{mmse}(X,\mathsf{snr})$.

Finally, the following generalization of the bound in (34) to discrete vector input, which is the sharpest known bound on the $\mathsf{gap}$ term, was derived in [25].

Theorem 4.

(Generalized Ozarow-Wyner Bound [25]) Let ${\mathbf{X}}_D$ be a discrete random vector with finite entropy, and let ${\mathcal{K}}_p$ be a set of continuous random vectors, independent of ${\mathbf{X}}_D$, such that for every $\mathbf{V}\in {\mathcal{K}}_p$, $h\left(\mathbf{V}\right),$${\parallel \mathbf{V}\parallel }_p<\infty$, and

$$\begin{array}{c}\hfill H\left({\mathbf{X}}_D\right|{\mathbf{X}}_D+\mathbf{V})=0,\forall \mathbf{V}\in {\mathcal{K}}_p.\end{array}$$

(35a)

Then for any $p>0$

$$\begin{array}{c}\hfill {[H\left({\mathbf{X}}_D\right)-{\mathsf{gap}}_p]}^{+}\le I({\mathbf{X}}_D;\mathbf{Y})\le H\left({\mathbf{X}}_D\right),\end{array}$$

(35b)

where

$$\begin{array}{cc}\hfill n^{-1}{\mathsf{gap}}_p& \le \underset{\mathbf{V}\in {\mathcal{K}}_p}{\inf }\left(G_{1,p}(\mathbf{V},{\mathbf{X}}_D)+G_{2,p}\left(\mathbf{V}\right)\right),\hfill \end{array}$$

$$\begin{array}{cc}\hfill G_{1,p}(\mathbf{V},{\mathbf{X}}_D)& =\log \left(\frac{\parallel \mathbf{V}+{\mathbf{X}}_D-f_p\left({\mathbf{X}}_D\right|\mathbf{Y}){\parallel }_p}{{\parallel \mathbf{V}\parallel }_p}\right)\le \left\{\begin{array}{c}\log \left(1+\frac{{\mathrm{mmpe}}^{\frac{1}{p}}({\mathbf{X}}_D,\mathsf{snr},p)}{{\parallel \mathbf{V}\parallel }_p}\right),p\ne 2\hfill \\ \frac{1}{2}\log \left(1+\frac{\mathrm{mmse}({\mathbf{X}}_D,\mathsf{snr})}{{\parallel \mathbf{V}\parallel }_2^2}\right),p=2\hfill \end{array}\right.,\hfill \end{array}$$

(35c)

$$\begin{array}{cc}\hfill G_{2,p}\left(\mathbf{V}\right)& =\log \left(\frac{k_{n,p}·n^{\frac{1}{p}}·{\parallel \mathbf{V}\parallel }_p}{{\mathrm{e}}^{\frac{1}{n}{h}_{\mathrm{e}}\left(\mathbf{V}\right)}}\right).\hfill \end{array}$$

(35d)

Remark 2.

The condition in (35a) can be enforced by, for example, selecting the support of $\mathbf{V}$ to satisfy a non-overlap condition given by

$$\begin{array}{c}\hfill \mathsf{supp}(\mathbf{V}+{\mathbf{x}}_i)\cap \mathsf{supp}(\mathbf{V}+{\mathbf{x}}_j)=\varnothing ,\forall {\mathbf{x}}_i,{\mathbf{x}}_j\in \mathsf{supp}\left({\mathbf{X}}_D\right),i\ne j,\end{array}$$

(36)

as was done in [54].

It is interesting to note that the lower bound in (35b) resembles the bound for lattice codes in [55], where $\mathbf{V}$ can be thought of as a dither, $G_{2,p}$ corresponds to the log of the normalized p-moment of a compact region in ${\mathbb{R}}^n$, $G_{1,p}$ corresponds to the log of the normalized MMSE term, and $H\left({\mathbf{X}}_D\right)$ corresponds to the capacity C.

In order to show the advantage of Theorem 4 over the original Ozarow-Wyner bound (case of $n=1$ and with LMMSE instead of MMPE), we consider $X_D$ uniformly distributed with the number of points equal to $N=\lfloor \sqrt{1+\mathsf{snr}}\rfloor$, that is, we choose the number of points such that $H\left(X_D\right)\approx \frac{1}{2}\log (1+\mathsf{snr})$. Figure 2 shows:

• The solid cyan line is the “shaping loss” $\frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{6}\right)$ for a one-dimensional infinite lattice and is the limiting gap if the number of points N grows faster than $\sqrt{\mathsf{snr}}$;
• The solid magenta line is the gap in the original Ozarow-Wyner bound in (33); and
• The dashed purple, dashed-dotted blue and dotted green lines are the new gap given by Theorem 4 for values of $p=2,4,6$, respectively, and where we choose $V\sim \mathcal{U}\left[-\frac{d_{\min \left(X_D\right)}}{2},\frac{d_{\min \left(X_D\right)}}{2}\right]$.

We note that the version of the Ozarow-Wyner bound in Theorem 4 provides the sharpest bound for the gap term. An open question, for $n=1$, is what value of p provide the smallest gap and whether it coincides with the ultimate “shaping loss”.

For the AWGN channel there exist a number of other bounds that use discrete inputs as well (see [46,56,57,58] and references therein). The advantage of using Ozarow-Wyner type bounds, however, lies in their simplicity as they only depend on the number of signal constellation points and the minimum distance of the constellation.

The Ozarow-Wyner bound will play a key role in Section 5 and Section 8 where we examine achievable schemes for a point-to-point channel with a disturbance constraint and for a two-user Gaussian interference channel.

For recent applications of the bound in Theorem 4 to non-Gaussian and MIMO channels the reader is referred to [59,60,61].

3.3. SNR Evolution of Optimal Codes

The I-MMSE can also be used in the analysis of the MMSE SNR-evolution of asymptotically optimal code sequences (code sequences that approach capacity in the limit of blocklength). In particular, using the I-MMSE relationship one can exactly identify the MMSE SNR-evolution of asymptotically optimal code sequences for the Gaussian point-to-point channel.

Theorem 5.

(SNR evolution of the MMSE [62,63]) Any code sequence for the Gaussian point-to-point channel attains capacity if and only if

$$\begin{array}{c}\hfill {\mathrm{mmse}}_{\infty }(\mathbf{X},\gamma )=\left\{\begin{array}{cc}\frac{1}{1+\gamma }\hfill & \gamma \le \mathsf{snr},\hfill \\ 0\hfill & \gamma \ge \mathsf{snr}.\hfill \end{array}\right.\end{array}$$

(37)

Figure 3 depicts the SNR evolution of the MMSE as described in Theorem 5. The discontinuity of the MMSE at $\mathsf{snr}$ is ofter referred to as the phase transition. From Theorem 5 it is clear that the optimal point-to-point code must have the same MMSE profile as the Gaussian distribution for all SNR’s before $\mathsf{snr}$ and experience a phase transition at $\mathsf{snr}$. Intuitively, the phase transition happens because an optimal point-to-point code designed to operate at $\mathsf{snr}$ can be reliably decoded at $\mathsf{snr}$ and SNR’s larger than $\mathsf{snr}$, and both the decoding and estimation errors can be driven to zero. It is also important to point out that the area under (37) is twice the capacity.

4. Applications to the Wiretap Channel

In this section, by focusing on the wiretap channel, it is shown how estimation theoretic techniques can be applied to multi-user information theory. The wiretap channel, introduced by Wyner in [64], is a point-to-point channel with an additional eavesdropper (see Figure 4a). The input is denoted by $\mathbf{X}$, the output of the legitimate user is denoted by $\mathbf{Y}$, and the output of an eavesdropper is denoted by ${\mathbf{Y}}_{\mathrm{e}}$. The transmitter of $\mathbf{X}$, commonly referred to as Alice, wants to reliably communicate a message W to the legitimate receiver $\mathbf{Y}$, commonly referred to as Bob, while keeping the message W secure to some extent from the eavesdropper ${\mathbf{Y}}_{\mathrm{e}}$, commonly referred to as Eve.

Definition 5.

A rate-equivocation pair $(R,d)$ is said to be achievable over a wiretap channel if there exists a sequence of $(2^{nR},n)$ codes such that

$$\begin{array}{cc}\underset{n\to \infty }{\lim }\mathbb{P}[\widehat{W}\ne W]=0,\hfill & \hfill reliabilityconstraint,\end{array}$$

(38a)

$$\begin{array}{cc}\underset{n\to \infty }{\lim }\frac{1}{n}I(W;{\mathbf{Y}}_{\mathrm{e}})\le R-d,\hfill & \hfill informationleakageorsecrecyconstraint.\end{array}$$

(38b)

The rate-equivocation region${\mathcal{R}}_s$ is defined as the closure of all achievable rate-equivocation pairs, and the secrecy capacity is defined as

$$\begin{array}{c}\hfill C_s=\underset{R}{\sup }\{R:(R,R)\in {\mathcal{R}}_s\}.\end{array}$$

(39)

The secrecy capacity of a general wiretap channel was shown by Csiszár and Körner [65] and is given by

$$\begin{array}{c}\hfill C_s=\underset{P_{UX}}{\max }\left\{I(U;Y)-I(U;Y_{\mathrm{e}})\right\}\end{array}$$

(40)

where U is an auxiliary random variable that satisfies the Markov relationship $U\leftrightarrow X\leftrightarrow (Y,Y_{\mathrm{e}})$.

In the case of a degraded wiretap channel (i.e., a wiretap channel obeying the Markov relationship $X\leftrightarrow Y\leftrightarrow Y_{\mathrm{e}}$) the expression in (40) reduces to

$$\begin{array}{c}\hfill C_s=\underset{P_X}{\max }\left\{I(X;Y)-I(X;Y_{\mathrm{e}})\right\}.\end{array}$$

(41)

In fact, the expression in (41) for the degraded channel predates the expression in (40) and was shown in the original work of Wyner [64].

4.1. Converse of the Gaussian Wiretap Channel

In this section, we consider the practically relevant scalar Gaussian wiretap channel given by

$$\begin{array}{cc}\hfill Y& =\sqrt{\mathsf{snr}}{X}_1+Z_1,\hfill \end{array}$$

(42a)

$$\begin{array}{cc}\hfill Y_{\mathrm{e}}& =\sqrt{{\mathsf{snr}}_0}{X}_2+Z_2,\hfill \end{array}$$

(42b)

where $\mathsf{snr}\ge {\mathsf{snr}}_0$, with an additional input power constraint $\mathbb{E}\left[X^2\right]\le 1$. This setting was considered in [66], and the secrecy capacity was shown to be

$$\begin{array}{c}\hfill C_s=\frac{1}{2}\log \left(\frac{1+\mathsf{snr}}{1+{\mathsf{snr}}_0}\right).\end{array}$$

(43)

In contrast to the proof in [66], where the key technical tool used to maximize the expression in (41) was the EPI, by using the I-MMSE relationship the capacity in (43) can be shown via the following simple three line argument [30]:

$$\begin{array}{cc}\hfill I(X;Y)-I(X;Y_{\mathrm{e}})& =\frac{1}{2}{\int }_{{\mathsf{snr}}_0}^{\mathsf{snr}}\mathrm{mmse}(X,t)dt\hfill \end{array}$$

(44a)

$$\begin{array}{cc}& \le \frac{1}{2}{\int }_{{\mathsf{snr}}_0}^{\mathsf{snr}}\frac{1}{1+t}dt\hfill \end{array}$$

(44b)

$$\begin{array}{cc}& =\frac{1}{2}\log \left(\frac{1+\mathsf{snr}}{1+{\mathsf{snr}}_0}\right),\hfill \end{array}$$

(44c)

where the inequality follows by using the LMMSE upper bound in (11). It is also interesting to point out that the technique in (44) can be easily mimicked to derive the entire rate-equivocation region; for details see [23].

4.2. SNR Evolution of Optimal Wiretap Codes

In the previous section, we saw that the I-MMSE relationship is a very powerful mathematical tool and can be used to provide a simple derivation of the secrecy capacity of the scalar Gaussian wiretap channel. In fact, as shown in [28,34], the I-MMSE relationship can also be used to obtain practical insights. Specifically, it was shown to be useful in identifying key properties of optimal wiretap codes.

Theorem 6.

(SNR evolution of the MMSE [28]) Any code sequence for the Gaussian wiretap channel attains a rate equivocation pair $(R,C_s)$, meaning it attains the maximum level of equivocation, if and only if

$$\begin{array}{c}\hfill {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma \mid W)=0,\gamma \ge {\mathsf{snr}}_0,\end{array}$$

(45)

and

$$\begin{array}{c}\hfill {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )=\left\{\begin{array}{cc}\frac{1}{1+\gamma },\hfill & \gamma \le \mathsf{snr},\hfill \\ 0,\hfill & \gamma >\mathsf{snr},\hfill \end{array}\right.\end{array}$$

(46)

regardless of the rate of the code, meaning for any $R\ge C_s$.

Note that, as shown in Theorem 5, (46) is the SNR-evolution of any point-to-point capacity achieving code sequence, C, to $\mathbf{Y}$ as shown in [62,63]; however, only a one-to-one mapping over this codebook sequence leads to the maximum point-to-point rate. The idea is that the maximum level of equivocation determines the SNR-evolution of $\mathrm{mmse}(\mathbf{X};\gamma )$ regardless of the rate.

The additional condition given in (45) is required in order to fully define the sub-group of code sequences that are $(R,C_s)$ codes for the Gaussian wiretap channel. Still, these conditions do not fully specify the rate of the code sequence, as the group contains codes of different rates R as long as $R\ge d_{\max }$. Note that the rate of the code is determined solely by the SNR-evolution of $\mathrm{mmse}\left(\mathbf{X};\gamma |W\right)$ in the region of $\gamma \in [0,{\mathsf{snr}}_0)$ and is given by

$$\begin{array}{c}R=\frac{1}{2}{\int }_0^{\mathsf{snr}}\left[{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )-{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W)\right]d\gamma .\hfill \end{array}$$

(47)

The immediate question that arises is: Can we find MMSE properties that will distinguish code sequences of different rates? The answer is affirmative in the two extreme cases: (i) When $R=C_s$, meaning a completely secure code; (ii) When $R=C$, meaning maximum point-to-point capacity. In the latter case, one-to-one mapping is required, and the conditional MMSE is simply zero for all SNR. Figure 5 considers the former case of perfect secrecy as well as an arbitrary intermediate case in which the rate is between the secrecy capacity and the point-to-point capacity.

According to the above result, constructing a completely secure code sequence requires splitting the possible codewords into sub-codes that are asymptotically optimal for the eavesdropper. This approach is exactly the one in Wyner’s original work [64], and also emphasized by Massey in [67], wherein the achievability proof the construction of the code sequence is such that the bins of each secure message are asymptotically optimal code sequences to the eavesdropper (saturating the eavesdropper). The above claim extends this observation by claiming that any mapping of messages to codewords (alternatively, any binning of the codewords) that attains complete secrecy must saturate the eavesdropper, thus supporting the known achievability scheme of Wyner. Moreover, it is important to emphasize that the maximum level of equivocation can be attained with no loss in rate, meaning the reliable receiver can continue communicating at capacity.

Another important point to note is that these results supports the necessity of a stochastic encoder for any code sequence for the Gaussian wiretap channel, achieving the maximum level of equivocation and with $R<C$ (as shown in [68] for a completely secure code for the discrete memoryless wiretap channel), since one can show that the conditions guarantee $H\left(\mathbf{X}|W\right)>0$ for any such code sequence.

5. Communication with a Disturbance Constraint

Consider a scenario in which a message, encoded as $\mathbf{X}$, must be decoded at the primary receiver $\mathbf{Y}$ while it is also seen at the unintended/secondary receiver ${\mathbf{Y}}_0$ for which it is interference, as shown in Figure 6a. The transmitter wishes to maximize its communication rate, while subject to a constraint on the disturbance it inflicts on the secondary receiver, and where the disturbance is measured by some function $F(\mathbf{X},{\mathbf{Y}}_0)$. It is common to refer to such a scenario as communication with a disturbance constraint. The choice of $F(\mathbf{X},{\mathbf{Y}}_0)$ depends on the application one has in mind. For example, a common application is to limit the interference that the primary user inflicts on the secondary. In this case, two possible choices of $F(\mathbf{X},{\mathbf{Y}}_0)$ are the mutual information $I(\mathbf{X};{\mathbf{Y}}_0)$ and the MMSE $\mathrm{mmse}\left(\mathbf{X}\right|{\mathbf{Y}}_0)$, considered in [69,70], respectively. In what follows we review these two possible measures of disturbance, so as to explain the advantages of the MMSE as a measure of disturbance that best models the interference.

5.1. Max-I Problem

Consider a Gaussian noise channel and take the disturbance to be measured in terms of the MMSE (i.e., $F(\mathbf{X},{\mathbf{Y}}_0)=\mathrm{mmse}(\mathbf{X},{\mathsf{snr}}_0)$), as shown on Figure 6b. Intuitively, the MMSE disturbance constraint quantifies the remaining interference after partial interference cancellation or soft-decoding have been performed [47,70]. Formally, the following problem was considered in [50]:

Definition 6.

(Max-I problem.) For some $\beta \in [0,1]$

$$\begin{array}{c}{\mathcal{C}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta ):=\underset{\mathbf{X}}{\sup }{I}_n(\mathbf{X},\mathsf{snr}),\hfill \end{array}$$

(48a)

$$\begin{array}{c}{\mathrm{s}.\mathrm{t}.\parallel \mathbf{X}\parallel }_2^2\le 1,powerconstraint\hfill \end{array}$$

(48b)

$$\begin{array}{c}and\mathrm{mmse}(\mathbf{X},{\mathsf{snr}}_0)\le \frac{\beta }{1+\beta {\mathsf{snr}}_0},MMSEconstraint.\hfill \end{array}$$

(48c)

The subscript n in ${\mathcal{C}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ emphasizes that we consider length n inputs $\mathbf{X}\in {\mathbb{R}}^n$ . Clearly ${\mathcal{C}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ is a non-decreasing function of n. The scenario depicted in Figure 6b is captured when $n\to \infty$ in the Max-I problem, in which case the objective function has a meaning of reliable achievable rate.

The scenario modeled by the Max-I problem is motivated by the two-user Gaussian interference channel (G-IC), whose capacity is known only for some special cases. The following strategies are commonly used to manage interference in the G-IC:

• Interference is treated as Gaussian noise: in this approach the interference is not explicitly decoded. Treating interference as noise with Gaussian codebooks has been shown to be sum-capacity optimal in the so called very-weak interference regime [71,72,73].
• Partial interference cancellation: by using the Han-Kobayashi (HK) achievable scheme [74], part of the interfering message is jointly decoded with part of the desired signal. Then the decoded part of the interference is subtracted from the received signal, and the remaining part of the desired signal is decoded while the remaining part of the interference is treated as Gaussian noise. With Gaussian codebooks, this approach has been shown to be capacity achieving in the strong interference regime [75] and optimal within 1/2 bit per channel per user otherwise [76].
• Soft-decoding/estimation: the unintended receiver employs soft-decoding of part of the interference. This is enabled by using non-Gaussian inputs and designing the decoders that treat interference as noise by taking into account the correct (non-Gaussian) distribution of the interference. Such scenarios were considered in [44,46,49], and shown to be optimal to within either a constant or a $O\left(\log \log \right(\mathsf{snr}\left)\right)$ gap for all regimes in [45].

Even though the Max-I problem is somewhat simplified, compared to that of determining the capacity of the G-IC, as it ignores the existence of the second transmission, it can serve as an important building block towards characterizing the capacity of the G-IC [47,70], especially in light of the known (but currently uncomputable) limiting expression for the capacity region [77]:

$$\begin{array}{c}{\mathcal{C}}_{\infty }^{\mathrm{IC}}=\underset{n\to \infty }{\lim }\mathsf{co}\bigcup _{P_{{\mathbf{X}}_1{\mathbf{X}}_2}=P_{{\mathbf{X}}_1}{P}_{{\mathbf{X}}_2}}\left\{\begin{array}{c}0\le R_1\le I_n({\mathbf{X}}_1;{\mathbf{Y}}_1)\hfill \\ 0\le R_2\le I_n({\mathbf{X}}_2;{\mathbf{Y}}_2)\hfill \end{array}\right\},\hfill \end{array}$$

(49)

where $\mathsf{co}$ denotes the convex closure operation. Moreover, observe that for any finite n we have that the capacity region can be inner bounded by

$$\begin{array}{c}\hfill {\mathcal{C}}_n^{\mathrm{IC}}\subset {\mathcal{C}}_{\infty }^{\mathrm{IC}},\end{array}$$

(50)

where

$$\begin{array}{c}\hfill {\mathcal{C}}_n^{\mathrm{IC}}=\mathsf{co}\bigcup _{P_{{\mathbf{X}}_1{\mathbf{X}}_2}=P_{{\mathbf{X}}_1}{P}_{{\mathbf{X}}_2}}\left\{\begin{array}{c}0\le R_1\le I_n({\mathbf{X}}_1;{\mathbf{Y}}_1)\hfill \\ 0\le R_2\le I_n({\mathbf{X}}_2;{\mathbf{Y}}_2)\hfill \end{array}\right\}.\end{array}$$

(51)

The inner bound ${\mathcal{C}}_n^{\mathrm{IC}}$ will be referred to as the treating interference as noise (TIN) inner bound. Finding the input distributions $P_{{\mathbf{X}}_1}{P}_{{\mathbf{X}}_2}$ that exhaust the achievable region in ${\mathcal{C}}_n^{\mathrm{IC}}$ is an important open problem. In Section 8, for a special case of $n=1$, we will demonstrate that ${\mathcal{C}}_1^{\mathrm{IC}}$ is within a constant or $O\left(\log \log \right(\mathsf{snr}\left)\right)$ from the capacity ${\mathcal{C}}_{\infty }^{\mathrm{IC}}$. Therefore, the Max-I problem, denoted by ${\mathcal{C}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ in (48), can serve as an important step in characterizing the structure of optimal input distributions for ${\mathcal{C}}_n^{\mathrm{IC}}$. We also note that in [47,70] it was conjectured that the optimal input for ${\mathcal{C}}_1(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ is discrete. For other recent works on optimizing the TIN region in (51), we refer the reader to [43,46,49,78,79] and the references therein.

The importance of studying models of communication systems with disturbance constraints has been recognized previously. For example, in [69] Bandemer et al. studied the following problem related to the Max-I problem in (48).

Definition 7.

(Bandemer et al. problem [69]) For some $R\ge 0$

$$\begin{array}{cc}\hfill {\mathcal{I}}_n({\mathsf{snr}}_0,\mathsf{snr},R)& :=\underset{\mathbf{X}}{\max }{I}_n(\mathbf{X},{\mathsf{snr}}_0),\hfill \end{array}$$

(52a)

$$\begin{array}{cc}& {\mathrm{s}.\mathrm{t}.\parallel \mathbf{X}\parallel }_2^2\le 1,\mathit{power}\mathit{constraint},\hfill \end{array}$$

(52b)

$$\begin{array}{cc}& \mathit{and}{I}_n(\mathbf{X},{\mathsf{snr}}_0)\le R,\mathit{disturbance}\mathit{constraint}.\hfill \end{array}$$

(52c)

In [69] it was shown that the optimal solution for ${\mathcal{I}}_n(\mathsf{snr},{\mathsf{snr}}_0,R)$, for any n, is attained by $\mathbf{X}\sim \mathcal{N}\left(\mathbf{0},\alpha \mathbf{I}\right)$ where $\alpha =\min \left(1,\frac{{\mathrm{e}}^{2R}-1}{{\mathsf{snr}}_0}\right)$; here $\alpha$ is such that the most stringent constraint between (52b) and (52c) is satisfied with equality. In other words, the optimal input is independent and identically distributed (i.i.d.) Gaussian with power reduced such that the disturbance constraint in (52c) is not violated.

Theorem 7

([69]). The rate-disturbance region of the problem in (52) is given by

$$\begin{array}{c}\hfill {\mathcal{I}}_n({\mathsf{snr}}_0,\mathsf{snr},R)\le \frac{1}{2}\log \left(1+\alpha \mathsf{snr}\right),\end{array}$$

(53)

with equality if and only if $\mathbf{X}\sim \mathcal{N}\left(\mathbf{0},\alpha \mathbf{I}\right)$ where $\alpha =\min \left(1,\frac{{\mathrm{e}}^{2R}-1}{{\mathsf{snr}}_0}\right)$.

Measuring the disturbance with the mutual information as in (52), in contrast to the MMSE as in (48), suggests that it is always optimal to use Gaussian codebooks with reduced power without any rate splitting. Moreover, while the mutual information constraint in (52) limits the amount of information transmitted to the unintended receiver, it may not be the best choice for measuring the interference, since any information that can be reliably decoded by the unintended receiver is not really interference. For this reason, it has been argued in [47,70] that the Max-I problem in (48) with the MMSE disturbance constraint is a more suitable building block to study the G-IC, since the MMSE constraint accounts for the interference, and captures the key role of rate splitting.

We also refer the reader to [80] where, in the context of discrete memoryless channels, the disturbance constraint was modeled by controlling the type (i.e., empirical distribution) of the interference at the secondary user. Moreover, the authors of [80] were able to characterize the tradeoff between the rate and the type of the induced interference by exactly characterizing the capacity region of the problem at hand.

We first consider a case of the Max-I problem when $n\to \infty$.

5.2. Characterization of ${\mathcal{C}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ as $n\to \infty$

For the practically relevant case of $n\to \infty$, which has an operational meaning, ${\mathcal{C}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ has been characterized in [70] and is given by the following theorem.

Theorem 8

([70]). For any $\mathsf{snr},{\mathsf{snr}}_0\ge 0$ and $\beta \in [0,1]$

$$\begin{array}{c}{\mathcal{C}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )=\underset{n\to \infty }{\lim }{\mathcal{C}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta ),\hfill \\ =\left\{\begin{array}{cc}\frac{1}{2}\log (1+\mathsf{snr}),& \mathsf{snr}\le {\mathsf{snr}}_0,\\ \frac{1}{2}\log (1+\beta \mathsf{snr})+\frac{1}{2}\log \left(1+\frac{{\mathsf{snr}}_0(1-\beta )}{1+\beta {\mathsf{snr}}_0}\right),& \mathsf{snr}\ge {\mathsf{snr}}_0,\end{array}\right.\hfill \\ =\frac{1}{2}{\log }^{+}\left(\frac{1+\beta \mathsf{snr}}{1+\beta {\mathsf{snr}}_0}\right)+\frac{1}{2}\log \left(1+\min (\mathsf{snr},{\mathsf{snr}}_0)\right),\hfill \end{array}$$

(54)

which is achieved by using superposition coding with Gaussian codebooks.

The proof of the achievability part of Theorem 8 is by using superposition coding and is outside of the scope of this work. The interested reader is referred to [63,70,81] for a detailed treatment of MMSE properties of superposition codes.

Next, we show a converse proof of Theorem 8. In addition, to the already familiar use of the LMMSE bound technique, as in the wiretap channel in Section 4.1, we also show an application of the SCPP bound. The proof for the case of $\mathsf{snr}\le {\mathsf{snr}}_0$ follows by ignoring the MMSE constraint at ${\mathsf{snr}}_0$ and using the LMMSE upper bound

$$\begin{array}{cc}\hfill I_n(\mathbf{X},\mathsf{snr})& =\frac{1}{2}{\int }_0^{\mathsf{snr}}\mathrm{mmse}(\mathbf{X},t)dt\hfill \\ & \le \frac{1}{2}{\int }_0^{\mathsf{snr}}\frac{1}{1+t}dt\hfill \\ & =\frac{1}{2}\log (1+\mathsf{snr})dt.\hfill \end{array}$$

Next, we focus on the case of $\mathsf{snr}\ge {\mathsf{snr}}_0$

$$\begin{array}{cc}\hfill I_n(\mathbf{X},\mathsf{snr})& =\frac{1}{2}{\int }_0^{\mathsf{snr}}\mathrm{mmse}(\mathbf{X},t)dt\hfill \\ & =\frac{1}{2}{\int }_0^{{\mathsf{snr}}_0}\mathrm{mmse}(\mathbf{X},t)dt+\frac{1}{2}{\int }_{{\mathsf{snr}}_0}^{\mathsf{snr}}\mathrm{mmse}(\mathbf{X},t)dt\hfill \\ & \le \frac{1}{2}{\int }_0^{{\mathsf{snr}}_0}\frac{1}{1+t}dt+\frac{1}{2}{\int }_{{\mathsf{snr}}_0}^{\mathsf{snr}}\frac{\beta }{1+\beta t}dt\hfill \\ & =\frac{1}{2}\log (1+\beta \mathsf{snr})+\frac{1}{2}\log \left(1+\frac{{\mathsf{snr}}_0(1-\beta )}{1+\beta {\mathsf{snr}}_0}\right),\hfill \end{array}$$

where the last inequality follows by upper bounding the integral over $[0,{\mathsf{snr}}_0]$ by the LMMSE bound in (11) and by upper bounding the integral over $[{\mathsf{snr}}_0,\mathsf{snr}]$ using the SCPP bound in (21).

Figure 7 shows a plot of ${\mathcal{C}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ in (54) normalized by the capacity of the point-to-point channel $\frac{1}{2}\log (1+\mathsf{snr})$. The region $\mathsf{snr}\le {\mathsf{snr}}_0$ (flat part of the curve) is where the MMSE constraint is inactive since the channel with ${\mathsf{snr}}_0$ can decode the interference and guarantee zero MMSE. The regime $\mathsf{snr}\ge {\mathsf{snr}}_0$ (curvy part of the curve) is where the receiver with ${\mathsf{snr}}_0$ can no-longer decode the interference and the MMSE constraint becomes active, which in practice is the more interesting regime because the secondary receiver experiences “weak interference” that cannot be fully decoded (recall that in this regime superposition coding appears to be the best achievable strategy for the two-user Gaussian interference channel, but it is unknown whether it achieves capacity [76]).

5.3. Proof of the Disturbance Constraint Problem with a Mutual Information Constraint

In this section we show that the mutual information disturbance constraint problem in (52) can also be solved via an estimation theoretic approach.

An Alternative Proof of the Converse Part of Theorem 7.

Observe that, similarly to the Max-I problem, the interesting case of the ${\mathcal{I}}_n({\mathsf{snr}}_0,\mathsf{snr},R)$ is the “weak interference” regime (i.e., $\mathsf{snr}\ge {\mathsf{snr}}_0$). This, follows since for the “strong interference” regime (i.e., $\mathsf{snr}\le {\mathsf{snr}}_0$) the result follows trivially by the data processing inequality

$$\begin{array}{c}\hfill I_n(\mathbf{X},\mathsf{snr})\le I_n(\mathbf{X},{\mathsf{snr}}_0)\le R,\end{array}$$

(55)

and maximizing (55) under the power constraint. To show Theorem 7, for the case of $\mathsf{snr}\ge {\mathsf{snr}}_0$, observe that

$$\begin{array}{c}\hfill 0\le I_n(\mathbf{X},{\mathsf{snr}}_0)\le \frac{1}{2}\log \left(1+{\mathsf{snr}}_0\right),\end{array}$$

(56)

where the inequality on the right is due to the power constraint on $\mathbf{X}$. Therefore, there exists some $\alpha \in [0,1]$ such that

$$\begin{array}{c}\hfill I_n(\mathbf{X},{\mathsf{snr}}_0)=\frac{1}{2}\log \left(1+\alpha {\mathsf{snr}}_0\right).\end{array}$$

(57)

Using the I-MMSE, (57) can be written as

$$\begin{array}{c}\hfill \frac{1}{2}{\int }_0^{{\mathsf{snr}}_0}\mathrm{mmse}(\mathbf{X},t)dt=\frac{1}{2}{\int }_0^{{\mathsf{snr}}_0}\frac{\alpha }{1+\alpha t}dt.\end{array}$$

(58)

From (58) and SCPP property we conclude that $\mathrm{mmse}(\mathbf{X},t)$ and $\frac{\alpha }{1+\alpha t}$ are either equal for all t, or cross each other once in the region $[0,{\mathsf{snr}}_0)$. In both cases, by the SCPP, we have

$$\begin{array}{c}\hfill \mathrm{mmse}(\mathbf{X},t)\le \frac{\alpha }{1+\alpha t},\forall t\in [{\mathsf{snr}}_0,\infty ).\end{array}$$

(59)

We are now in the position to bound the main term of the disturbance constrained problem. By using the I-MMSE relationship the mutual information can be bounded as follows:

$$\begin{array}{cc}\hfill I_n(\mathbf{X},\mathsf{snr})& =\frac{1}{2}{\int }_0^{{\mathsf{snr}}_0}\mathrm{mmse}(\mathbf{X},t)dt+\frac{1}{2}{\int }_{{\mathsf{snr}}_0}^{\mathsf{snr}}\mathrm{mmse}(\mathbf{X},t)dt\hfill \\ & =\frac{1}{2}\log \left(1+\alpha {\mathsf{snr}}_0\right)+\frac{1}{2}{\int }_{{\mathsf{snr}}_0}^{\mathsf{snr}}\mathrm{mmse}(\mathbf{X},t)dt\hfill \end{array}$$

$$\begin{array}{cc}& \le \frac{1}{2}\log \left(1+\alpha {\mathsf{snr}}_0\right)+\frac{1}{2}{\int }_{{\mathsf{snr}}_0}^{\mathsf{snr}}\frac{\alpha }{1+\alpha t}dt\hfill \end{array}$$

(60)

$$\begin{array}{cc}& =\frac{1}{2}\log \left(1+\alpha \mathsf{snr}\right),\hfill \end{array}$$

(61)

where the bound in (60) follows by the inequality in (59). The proof of the converse is concluded by establishing that the maximum value of $\alpha$ in (61) is given by $\alpha =\min \left(1,\frac{{\mathrm{e}}^{2R}-1}{{\mathsf{snr}}_0}\right)$ which is a consequence of the bound $I_n(\mathbf{X},{\mathsf{snr}}_0)\le R$.

This concludes the proof of the converse.  ☐

The achievability proof of Theorem 7 follows by using an i.i.d. Gaussian input with power $\alpha$. This concludes the proof of Theorem 7.

In contrast to the proof in [69] which appeals to the EPI, the proof outlined here only uses the SCPP and the I-MMSE. Note, that unlike the proof of the converse of the Max-I problem, which also requires the LMMSE bound, the only ingredient in the proof of the converse for ${\mathcal{I}}_n({\mathsf{snr}}_0,\mathsf{snr},R)$ is a clever use of the SCPP bound. In Section 6, we will make use of this technique and show a converse proof for the scalar Gaussian broadcast channel.

Another observation is that the achievability proof of the ${\mathcal{I}}_n({\mathsf{snr}}_0,\mathsf{snr},R)$ holds for an arbitrary finite n while the achievability proof of the Max-I problem holds only as $n\to \infty$. In the next section, we demonstrate techniques for how to extend the achievability of the Max-I problem to the case of finite n. These techniques will ultimately be used to show an approximate optimality of the TIN inner bound for the two-user G-IC in Section 8.

5.4. Max-MMSE Problem

The Max-I problem in (48) is closely related to the following optimization problem.

Definition 8.

(Max-MMSE problem [50,82]) For some $\beta \in [0,1]$

$$\begin{array}{c}{\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta ):=\underset{\mathbf{X}}{\sup }\mathrm{mmse}(\mathbf{X},\mathsf{snr}),\hfill \end{array}$$

(62a)

$$\begin{array}{c}{\mathrm{s}.\mathrm{t}.\parallel \mathbf{X}\parallel }_2^2\le 1,\mathit{power}\mathit{constraint},\hfill \end{array}$$

(62b)

$$\begin{array}{c}\mathit{and}\mathrm{mmse}(\mathbf{X},{\mathsf{snr}}_0)\le \frac{\beta }{1+\beta {\mathsf{snr}}_0},\mathit{MMSE}\mathit{constraint}.\hfill \end{array}$$

(62c)

The authors of [63,70] proved that

$$\begin{array}{c}\hfill {\mathrm{M}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )=\underset{n\to \infty }{\lim }{\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )=\left\{\begin{array}{cc}\frac{1}{1+\mathsf{snr}},& \mathsf{snr}<{\mathsf{snr}}_0,\\ \frac{\beta }{1+\beta \mathsf{snr}},& \mathsf{snr}\ge {\mathsf{snr}}_0,\end{array}\right.,\end{array}$$

(63)

achieved by superposition coding with Gaussian codebooks. Clearly there is a discontinuity in (63) at $\mathsf{snr}={\mathsf{snr}}_0$ for $\beta <1$. This fact is a well known property of the MMSE, and it is referred to as a phase transition [63].

The LMMSE bound provides the converse solution for ${\mathrm{M}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ in (63) in the regime $\mathsf{snr}\le {\mathsf{snr}}_0$. An interesting observation is that in this regime the knowledge of the MMSE at ${\mathsf{snr}}_0$ is not used. The SCPP bound provides the converse in the regime $\mathsf{snr}\le {\mathsf{snr}}_0$ and, unlike the LMMSE bound, does use the knowledge of the value of MMSE at ${\mathsf{snr}}_0$.

The solution of the Max-MMSE problem provides an upper bound on the Max-I problem (for every n including in the limit as $n\to \infty$), through the I-MMSE relationship

$$\begin{array}{cc}\hfill {\mathcal{C}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )=\frac{1}{2}{\int }_0^{\mathsf{snr}}\mathrm{mmse}(\mathbf{X},t)dt& \le \frac{1}{2}{\int }_0^{\mathsf{snr}}{\mathrm{M}}_n(t,{\mathsf{snr}}_0,\beta )dt.\hfill \end{array}$$

(64)

The reason is that in the Max-MMSE problem one maximizes the integrand in the I-MMSE relationship for every $\gamma$, and the maximizing input may have a different distribution for each $\gamma$. The surprising result is that in the limit as $n\to \infty$ we have equality, meaning that in the limit there exists an input that attains the maximum Max-MMSE solution for every $\gamma$. In other words, the integration of ${\mathrm{M}}_{\infty }(\gamma ,{\mathsf{snr}}_0,\beta )$ over $\gamma \in [0,\mathsf{snr}]$ results in ${\mathcal{C}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )$. In view of the relationship in (64) we focus on the ${\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ problem.

Note that SCPP gives a solution to the Max-MMSE problem in (62) for $\mathsf{snr}\ge {\mathsf{snr}}_0$ and any $n\ge 1$ as follows:

$$\begin{array}{c}\hfill {\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )=\frac{\beta }{1+\beta \mathsf{snr}},\mathrm{for}\mathsf{snr}\ge {\mathsf{snr}}_0,\end{array}$$

(65)

achieved by $\mathbf{X}\sim \mathcal{N}(0,\beta \mathbf{I})$.

However, for $\mathsf{snr}\le {\mathsf{snr}}_0$, where the LMMSE bound (11) is used without taking the constraint into account, it is no longer tight for every $n\ge 1$. Therefore, the emphasis in the treatment of the Max-MMSE problem is on the regime $\mathsf{snr}\le {\mathsf{snr}}_0$. In other words, the phase transition phenomenon can only be observed as $n\to \infty$, and for any finite n the LMMSE bound on the MMSE at $\mathsf{snr}\le {\mathsf{snr}}_0$ must be sharpened, as the MMSE constraint at ${\mathsf{snr}}_0$ must restrict the input in such a way that would effect the MMSE performance at $\mathsf{snr}\le {\mathsf{snr}}_0$. We refer to the upper bounds in the regime $\mathsf{snr}\le {\mathsf{snr}}_0$ as complementary SCPP bounds. Also, for any finite n, $\mathrm{mmse}(\mathbf{X},\mathsf{snr})$ is a continuous function of $\mathsf{snr}$ [30]. Putting these two facts together we have that, for any finite n, the objective function ${\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ must be continuous in $\mathsf{snr}$ and converge to a function with a jump-discontinuity at ${\mathsf{snr}}_0$ as $n\to \infty$. Therefore, ${\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ must be of the following form:

$$\begin{array}{c}{\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )=\left\{\begin{array}{cc}\frac{1}{1+\mathsf{snr}},\hfill & \mathsf{snr}\le {\mathsf{snr}}_L,\hfill \\ T_n(\mathsf{snr},{\mathsf{snr}}_0,\beta ),\hfill & {\mathsf{snr}}_L\le \mathsf{snr}\le {\mathsf{snr}}_0,\hfill \\ \frac{\beta }{1+\beta \mathsf{snr}},\hfill & {\mathsf{snr}}_0\le \mathsf{snr},\hfill \end{array}\right.\hfill \end{array}$$

(66)

for some ${\mathsf{snr}}_L$. The goal is to characterize ${\mathsf{snr}}_L$ in (66) and the continuous function $T_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ such that

$$\begin{array}{cc}\hfill T_n({\mathsf{snr}}_L,{\mathsf{snr}}_0,\beta )& =\frac{1}{1+{\mathsf{snr}}_L},\hfill \end{array}$$

(67a)

$$\begin{array}{cc}\hfill T_n({\mathsf{snr}}_0,{\mathsf{snr}}_0,\beta )& =\frac{\beta }{1+\beta {\mathsf{snr}}_0},\hfill \end{array}$$

(67b)

and give scaling bounds on the width of the phase transition region defined as

$$\begin{array}{c}\hfill W_n:={\mathsf{snr}}_0-{\mathsf{snr}}_L.\end{array}$$

(68)

In other words, the objective is to understand the behavior of the MMSE phase transitions for arbitrary finite n by obtaining complementary upper bounds on the SCPP. We first focus on upper bounds on ${\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$.

Theorem 9.

(D-Bound [50]) For any $\mathbf{X}$ and $0<\mathsf{snr}\le {\mathsf{snr}}_0$, we have

$$\begin{array}{c}\mathrm{mmse}(\mathbf{X},\mathsf{snr})\le \mathrm{mmse}(\mathbf{X},{\mathsf{snr}}_0)+k_n\left(\frac{1}{\mathsf{snr}}-\frac{1}{{\mathsf{snr}}_0}\right),\hfill \end{array}$$

(69a)

$$\begin{array}{c}{k}_n\le n+2,\hfill \end{array}$$

(69b)

The proof of Theorem 9 can be found in [50] and relies on developing bounds on the derivative of the MMSE with respect to the SNR.

Theorem 10.

(M-Bound [25]) For $0<\mathsf{snr}\le {\mathsf{snr}}_0$,

$$\begin{array}{c}\mathrm{mmse}(\mathbf{X},\mathsf{snr})\le \underset{r>\frac{2}{\gamma }}{\min }\kappa (r,\gamma ,n){\left(\mathrm{mmse}(\mathbf{X},{\mathsf{snr}}_0)\right)}^{\frac{\gamma r-2}{r-2}},\hfill \end{array}$$

(70a)

where $\gamma :=\frac{\mathsf{snr}}{2{\mathsf{snr}}_0-\mathsf{snr}}\in (0,1],$ and

$$\begin{array}{c}\kappa (r,\gamma ,n):=\frac{\sqrt{2}}{n^{1-\gamma }}{\left(\frac{1+\gamma }{\gamma }\right)}^{\frac{n(1-\gamma )-1}{2}}{M}_r^{\frac{2(1-\gamma )}{r-2}},\hfill \end{array}$$

(70b)

$$\begin{array}{c}{M}_r:={∥\mathbf{X}-\mathbb{E}\left[\mathbf{X}|{\mathbf{Y}}_{{\mathsf{snr}}_0}\right]∥}_r^r\le 2^r\min \left(\frac{{\parallel \mathbf{Z}\parallel }_r^r}{{\mathsf{snr}}_0^{\frac{r}{2}}},{\parallel \mathbf{X}\parallel }_r^r\right).\hfill \end{array}$$

(70c)

The bounds in (69a) and in (70a) are shown in Figure 8. The key observation is that the bounds in (69a) and in (70a) are sharper versions of the LMMSE bound that take into account the value of the MMSE at ${\mathsf{snr}}_0$. It is interesting to observe how the bounds converge with n going to ∞.

The bound in (70a) is asymptotically tighter than the one in (69a). It can be shown that the phase transition region shrinks as $O\left(\frac{1}{\sqrt{n}}\right)$ for (70a), and as $O\left(\frac{1}{n}\right)$ for the bound in (69a). It is not possible in general to assert that (70a) is tighter than (69a). In fact, for small values of n, the bound in (69a) can offer advantages, as seen for the case $n=1$ shown in Figure 8b. Another advantage of the bound in (69a) is its analytical simplicity.

With the bounds in (69a) and in (70a) at our disposal we can repeat the converse proof outline in (61).

5.5. Mixed Inputs

Another question that arises, in the context of finite n, is how to mimic the achievability of superposition codes? Specifically, how to select an input that will maximize ${\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ when $\mathsf{snr}\le {\mathsf{snr}}_0$.

We propose to use the following input, which in [45] was termed a mixed input:

$$\begin{array}{cc}\hfill {\mathbf{X}}_{\mathrm{mix}}& :=\sqrt{1-\delta }{\mathbf{X}}_D+\sqrt{\delta }{\mathbf{X}}_G,\delta \in [0,1]:\hfill \end{array}$$

(71)

$$\begin{array}{cc}\hfill {\mathbf{X}}_G& \sim \mathcal{N}(0,\mathbf{I}),\parallel {\mathbf{X}}_D{\parallel }_2^2\le 1,\frac{1}{n}H\left({\mathbf{X}}_D\right)<\infty ,\hfill \end{array}$$

(72)

where ${\mathbf{X}}_G$ and ${\mathbf{X}}_D$ are independent. The parameter $\delta$ and the distribution of ${\mathbf{X}}_D$ are to be optimized over.

The behavior of the input in (71) exibits many properties of superposition codes and we will see that the discrete part ${\mathbf{X}}_D$ will behave as the common message and the Gaussian part ${\mathbf{X}}_G$ will behave as the private message.

The input ${\mathbf{X}}_{\mathrm{mix}}$ exhibits a decomposition property via which the MMSE and the mutual information can be written as the sum of the MMSE and the mutual information of the ${\mathbf{X}}_D$ and ${\mathbf{X}}_G$ components, albeit at different SNR values.

Proposition 7

([50]). For ${\mathbf{X}}_{\mathrm{mix}}$ defined in (71) we have that

$$\begin{array}{cc}\hfill I_n({\mathbf{X}}_{\mathrm{mix}},\mathsf{snr})& =I_n\left({\mathbf{X}}_D,\frac{\mathsf{snr}(1-\delta )}{1+\delta \mathsf{snr}}\right)+I_n({\mathbf{X}}_G,\mathsf{snr}\delta ),\hfill \end{array}$$

(73a)

$$\begin{array}{cc}\hfill \mathrm{mmse}({\mathbf{X}}_{\mathrm{mix}},\mathsf{snr})& =\frac{1-\delta }{{(1+\mathsf{snr}\delta )}^2}\mathrm{mmse}\left({\mathbf{X}}_D,\frac{\mathsf{snr}(1-\delta )}{1+\delta \mathsf{snr}}\right)+\delta \mathrm{mmse}({\mathbf{X}}_G,\mathsf{snr}\delta ).\hfill \end{array}$$

(73b)

Observe that Proposition 7 implies that, in order for mixed inputs (with $\delta <1$) to comply with the MMSE constraint in (48c) and (62c), the MMSE of ${\mathbf{X}}_D$ must satisfy

$$\begin{array}{c}\hfill \mathrm{mmse}\left({\mathbf{X}}_D,\frac{{\mathsf{snr}}_0(1-\delta )}{1+\delta {\mathsf{snr}}_0}\right)\le \frac{(\beta -\delta )(1+\delta {\mathsf{snr}}_0)}{(1-\delta )(1+\beta {\mathsf{snr}}_0)}.\end{array}$$

(74)

Proposition 7 is particularly useful because it allows us to design the Gaussian and discrete components of the mixed input independently.

Next, we evaluate the performance of ${\mathbf{X}}_{\mathrm{mix}}$ in ${\mathrm{M}}_n(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ for the important special case of $n=1$. Figure 9 shows upper and lower bounds on ${\mathrm{M}}_1(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ where we show the following:

• The ${\mathrm{M}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ upper bound in (63) (solid red line);
• The upper D-bound (69a) (dashed cyan line) and upper M-bound (dashed red line) (70a);
• The Gaussian-only input (solid green line), with $X\sim \mathcal{N}(0,\beta )$, where the power has been reduced to meet the MMSE constraint;
• The mixed input (blue dashed line), with the input in (71). We used Proposition 7 where we optimized over $X_D$ for $\delta =\beta \frac{{\mathsf{snr}}_0}{1+{\mathsf{snr}}_0}$. The choice of $\delta$ is motivated by the scaling property of the MMSE, that is, $\delta \mathrm{mmse}(X_G,\mathsf{snr}\delta )=\mathrm{mmse}(\sqrt{\delta }{X}_G,\mathsf{snr})$, and the constraint on the discrete component in (74). That is, we chose $\delta$ such that the power of $X_G$ is approximately $\beta$ while the MMSE constraint on $X_D$ in (74) is not equal to zero. The input $X_D$ used in Figure 9 was found by a local search algorithm on the space of distributions with $N=3$, and resulted in $X_D=[-1.8412,-1.7386,0.5594]$ with $P_X=[0.1111,0.1274,0.7615]$, which we do not claim to be optimal;
• The discrete-only input (Discrete 1 brown dashed-dotted line), with
  $X_D=[-1.8412,-1.7386,0.5594]$ with $P_X=[0.1111,0.1274,0.7615]$, that is, the same discrete part of the above mentioned mixed input. This is done for completeness, and to compare the performance of the MMSE of the discrete component of the mixed input with and without the Gaussian component; and
• The discrete-only input (Discrete 2 dotted magenta line), with
  $X_D=[-1.4689,-1.1634,0.7838]$ with $P_X=[0.1282,0.2542,0.6176]$, which was found by using a local search algorithm on the space of discrete-only distributions with $N=3$ points.

The choice of $N=3$ is motivated by the fact that it requires roughly $N=\lfloor \sqrt{1+{\mathsf{snr}}_0}\rfloor$ points for the PAM input to approximately achieve capacity of the point-to-point channel with SNR value ${\mathsf{snr}}_0$.

On the one hand, Figure 9 shows that, for $\mathsf{snr}\ge {\mathsf{snr}}_0$, a Gaussian-only input with power reduced to $\beta$ maximizes ${\mathrm{M}}_1(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ in agreement with the SCPP bound (green line). On the other hand, for $\mathsf{snr}\le {\mathsf{snr}}_0$, we see that discrete-only inputs (brown dashed-dotted line and magenta dotted line) achieve higher MMSE than a Gaussian-only input with reduced power. Interestingly, unlike Gaussian-only inputs, discrete-only inputs do not have to reduce power in order to meet the MMSE constraint. The reason discrete-only inputs can use full power, as per the power constraint only, is because their MMSE decreases fast enough (exponentially in SNR) to comply with the MMSE constraint. However, for $\mathsf{snr}\ge {\mathsf{snr}}_0$, the behavior of the MMSE of discrete-only inputs, as opposed to mixed inputs, prevents it from being optimal; this is due to their exponential tail behavior. The mixed input (blue dashed line) gets the best of both (Gaussian-only and discrete-only) worlds: it has the behavior of Gaussian-only inputs for $\mathsf{snr}\ge {\mathsf{snr}}_0$ (without any reduction in power) and the behavior of discrete-only inputs for $\mathsf{snr}\le {\mathsf{snr}}_0$. This behavior of mixed inputs turns out to be important for the Max-I problem, where we need to choose an input that has the largest area under the MMSE curve.

Finally, Figure 9 shows the achievable MMSE with another discrete-only input (Discrete 2, dotted magenta line) that achieves higher MMSE than the mixed input for $\mathsf{snr}\le {\mathsf{snr}}_0$ but lower than the mixed input for $\mathsf{snr}\ge {\mathsf{snr}}_0$. This is again due to the tail behavior of the MMSE of discrete inputs. The reason this second discrete input is not used as a component of the mixed inputs is because this choice would violate the MMSE constraint on $X_D$ in (74). Note that the difference between Discrete 1 and 2 is that, Discrete 1 was found as an optimal discrete component of a mixed input (i.e., $\delta =\beta \frac{{\mathsf{snr}}_0}{1+{\mathsf{snr}}_0}$), while Discrete 2 was found as an optimal discrete input without a Gaussian component (i.e., $\delta =0$).

We conclude this section by demonstrating that an inner bound on ${\mathcal{C}}_1(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ with the mixed input in (71) is to within an additive gap of the outer bound.

Theorem 11

([50]). A lower bound on ${\mathcal{C}}_1(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ with the mixed input in (71), with $X_D\sim \mathsf{PAM}$ and with input parameters as specified in

Table 1. Parameters of the mixed input in (71) used in the proof of Proposition 11.

Regime	Input Parameters
Weak Interference ($\mathsf{snr}\ge {\mathsf{snr}}_0$)	$N=⌊\sqrt{1+c_1\frac{(1-\delta ){\mathsf{snr}}_0}{1+\delta {\mathsf{snr}}_0}}⌋,$$c_1=\frac{3}{2\log \left(\frac{12(1-\delta )(1+\beta {\mathsf{snr}}_0)}{(1+{\mathsf{snr}}_0\delta )(\beta -\delta )}\right)}$, $\delta =\beta \frac{{\mathsf{snr}}_0}{1+{\mathsf{snr}}_0}$
Strong Interference ($\mathsf{snr}\le {\mathsf{snr}}_0$)	$N=⌊\sqrt{1+c_2\mathsf{snr}}⌋$, $c_2=\frac{3}{2\log \left(\frac{12(1+\beta {\mathsf{snr}}_0)}{\beta }\right)}$, $\delta =0$

, is to within $O\left(\log \log \left(\frac{1}{\mathrm{mmse}(X,{\mathsf{snr}}_0)}\right)\right)$.

We refer the reader to [50] for the details of the proof and extension of Theorem 11 to arbitrary n.

Please note that the gap result in Proposition 11 is constant in $\mathsf{snr}$ (i.e., independent of $\mathsf{snr}$) but not in ${\mathsf{snr}}_0$. Figure 10 compares the inner bounds on ${\mathcal{C}}_1(\mathsf{snr},{\mathsf{snr}}_0,\beta )$, normalized by the point-to-point capacity $\frac{1}{2}\log (1+\mathsf{snr})$, with mixed inputs (dashed magenta line) in Proposition 11 to:

• The ${\mathcal{C}}_{\infty }(\mathsf{snr},{\mathsf{snr}}_0,\beta )$ upper bound in (54) (solid red line);
• The upper bound from integration of the bound in (69a) (dashed blue line);
• The upper bound from integration of the bound in (70a) (dashed red line); and
• The inner bound with $X\sim \mathcal{N}(0,\beta )$, where the reduction in power is necessary to satisfy the MMSE constraint $\mathrm{mmse}(X,{\mathsf{snr}}_0)\le \frac{\beta }{1+\beta {\mathsf{snr}}_0}$ (dotted green line).

Figure 10 shows that Gaussian inputs are sub-optimal and that mixed inputs achieve large degrees of freedom compared to Gaussian inputs. Interestingly, in the regime $\mathsf{snr}\le {\mathsf{snr}}_0$, it is approximately optimal to set $\delta =0$, that is, only the discrete part of the mixed input is used. This in particular supports the conjecture in [70] that discrete inputs may be optimal for $n=1$ and $\mathsf{snr}\le {\mathsf{snr}}_0$. For the case $\mathsf{snr}\ge {\mathsf{snr}}_0$ our results partially refute the conjecture by excluding the possibility of discrete inputs with finitely many points from being optimal.

The key intuition developed in this section about the mixed input and its close resemblance to superposition coding will be used in Section 8 to show approximate optimality of TIN for the two-user G-IC.

6. Applications to the Broadcast Channel

The broadcast channel (BC), introduced by Cover in [83], is depicted in Figure 11a. In the BC the goal of the transmitter is to reliably transmit the message $W_1$ to receiver 1 and the message $W_2$ to receiver 2. The transmitter encodes the pair of messages $(W_1,W_2)$ into a transmitted codeword $\mathbf{X}$ of length n. Receiver 1 receives the sequence ${\mathbf{Y}}_1$ of length n and receiver 2 receives the sequence ${\mathbf{Y}}_2$ of length n. They both try to decode their respective messages from their received sequence. An achievable rate pair is defined as follows:

Definition 9.

A rate pair $(R_1,R_2)$ is said to be achievable for each n, for a message $W_1$ of cardinality $2^{n{R}_1}$ and a message $W_2$ of cardinality $2^{n{R}_2}$, if there exists an encoding function

$$\begin{array}{cc}\hfill f_n(W_1,W_2)& =\mathbf{X},\hfill \end{array}$$

and decoding functions

$$\begin{array}{cc}\hfill {\widehat{W}}_1& =g_{1,n}\left({\mathbf{Y}}_1\right),\hfill \\ \hfill {\widehat{W}}_2& =g_{2,n}\left({\mathbf{Y}}_2\right),\hfill \end{array}$$

such that

$$\begin{array}{c}\hfill \underset{n\to \infty }{\lim }\mathbb{P}[(W_1,W_2)\ne ({\widehat{W}}_1,{\widehat{W}}_2)]=0,\end{array}$$

assuming that $W_1$ and $W_2$ are uniformly distributed over the respective message sets.

The capacity is defined as the closure over all achievable rate pairs. Note that one can easily add to the above definition a common message.

The capacity of a general broadcast channel is still an open problem. However, the capacity is known for some important special cases [42] such as the degraded broadcast channel which is of interest in this work.

As told by Cover in [84] 1973–1974 was a year of “intense activity” where Bergmans, Gallager and others tried to provide a converse proof showing that the natural achievable region (shown in 1973 by Bergmans) is indeed the capacity region. Correspondences were exchanged between Gallager, Bergmans and Wyner until finally one day both Gallager and Bergmans sent a converse proof to Wyner. Gallager’s proof tackled the degraded (i.e., $X\leftrightarrow Y_1\leftrightarrow Y_2$) discrete memoryless BC yielding the following [85]:

$$\begin{array}{c}\hfill {\mathcal{C}}_{BC}=\bigcup _{P_{UX}}\left\{\begin{array}{c}{R}_1\le I(X;Y_1|U)\hfill \\ R_2\le I(U;Y_2)\hfill \end{array}\right.,\end{array}$$

(75)

where U is an auxiliary random variable with $U\leftrightarrow X\leftrightarrow (Y_1,Y_2)$. It did not consider a constraint on the input.

Bergman’s proof directly examined the scalar Gaussian channel under a power constraint $\mathbb{E}\left[X^2\right]\le 1$ and input-output relationship given by

$$\begin{array}{cc}\hfill Y_1& =\sqrt{{\mathsf{snr}}_1}X+Z_1,\hfill \end{array}$$

(76)

$$\begin{array}{cc}\hfill Y_2& =\sqrt{{\mathsf{snr}}_2}X+Z_2,\hfill \end{array}$$

(77)

where ${\mathsf{snr}}_1\ge {\mathsf{snr}}_2$ (i.e., the degraded case) and applied the EPI (its first use since Shannon’s paper in 1948) [86]:

$$\begin{array}{c}\hfill {\mathcal{C}}_{BC}=\bigcup _{\alpha \in [0,1]}\left\{\begin{array}{c}{R}_1\le \frac{1}{2}\log \left(1+\alpha {\mathsf{snr}}_1\right)\hfill \\ R_2\le \frac{1}{2}\log \left(\frac{1+{\mathsf{snr}}_2}{1+\alpha {\mathsf{snr}}_2}\right)\hfill \end{array}\right..\end{array}$$

(78)

6.1. Converse for the Gaussian Broadcast Channel

In [30] Guo et al. have shown that a converse proof of the scalar (degraded) Gaussian channel can also be derived using the SCPP bound instead of the EPI, when applied on the extension of Gallager’s single-letter expression which takes into account also a power constraint.

The power constraint $\mathbb{E}\left[X^2\right]\le 1$, implies that there exists some $\alpha \in [0,1]$ such that

$$\begin{array}{c}\hfill I(X;Y_2|U)=\frac{1}{2}\log (1+\alpha {\mathsf{snr}}_2)=\frac{1}{2}{\int }_0^{{\mathsf{snr}}_2}\frac{\alpha }{1+\alpha t}dt.\end{array}$$

(79)

By the chain rule of mutual information

$$\begin{array}{cc}\hfill I(U;Y_2)& =I(U,X;Y_2)-I(X;Y_2|U)\hfill \\ & =I(X;Y_2)-I(X;Y_2|U),\hfill \end{array}$$

(80)

where in the last step we have used the Markov chain relationship $U\leftrightarrow X\leftrightarrow (Y_1,Y_2)$. Using (79) and (80) the bound on $R_2$ is given by

$$\begin{array}{cc}\hfill R_2& \le I(U;Y_2)\hfill \\ & =\frac{1}{2}{\int }_0^{{\mathsf{snr}}_2}\mathrm{mmse}(X,t)dt+{\int }_0^{{\mathsf{snr}}_2}\frac{\alpha }{1+\alpha t}dt\hfill \end{array}$$

$$\begin{array}{cc}& \le \frac{1}{2}{\int }_0^{{\mathsf{snr}}_2}\frac{1}{1+t}dt+{\int }_0^{{\mathsf{snr}}_2}\frac{\alpha }{1+\alpha t}dt\hfill \end{array}$$

(81)

$$\begin{array}{cc}& =\frac{1}{2}\log \left(\frac{1+{\mathsf{snr}}_2}{1+\alpha {\mathsf{snr}}_2}\right),\hfill \end{array}$$

(82)

where in (81) we have used the LMMSE bound. The inequality in (82) establishes the desired bound on $R_2$. To bound the $R_1$ term observe that by using I-MMSE and (79)

$$\begin{array}{c}\hfill I(X;Y_2|U)=\frac{1}{2}{\int }_0^{{\mathsf{snr}}_2}\mathrm{mmse}(X,t|U)dt=\frac{1}{2}{\int }_0^{{\mathsf{snr}}_2}\frac{\alpha }{1+\alpha t}dt,\end{array}$$

(83)

the expression in (83) implies that there exists some $0\le {\mathsf{snr}}_0\le {\mathsf{snr}}_2$ such that

$$\begin{array}{c}\hfill \mathrm{mmse}(X,{\mathsf{snr}}_0|U)=\frac{\alpha }{1+\alpha {\mathsf{snr}}_0}.\end{array}$$

(84)

The equality in (84) together with the SCPP bound implies the following inequality:

$$\begin{array}{c}\hfill \mathrm{mmse}(X,t|U)\le \frac{\alpha }{1+\alpha t},\end{array}$$

(85)

for all $t\ge {\mathsf{snr}}_2\ge {\mathsf{snr}}_0$. Therefore,

$$\begin{array}{cc}\hfill R_1& \le I(X;Y_1|U)\hfill \\ & =\frac{1}{2}{\int }_0^{{\mathsf{snr}}_2}\mathrm{mmse}(X,t|U)dt+\frac{1}{2}{\int }_{{\mathsf{snr}}_2}^{{\mathsf{snr}}_1}\mathrm{mmse}(X,t|U)dt\hfill \end{array}$$

(86)

$$\begin{array}{cc}& =\frac{1}{2}\log (1+\alpha {\mathsf{snr}}_2)+\frac{1}{2}{\int }_{{\mathsf{snr}}_2}^{{\mathsf{snr}}_1}\mathrm{mmse}(X,t|U)dt\hfill \end{array}$$

(87)

$$\begin{array}{cc}& \le \frac{1}{2}\log (1+\alpha {\mathsf{snr}}_2)+\frac{1}{2}{\int }_{{\mathsf{snr}}_2}^{{\mathsf{snr}}_1}\frac{\alpha }{1+\alpha t}dt\hfill \\ & =\frac{1}{2}\log \left(\frac{1+{\mathsf{snr}}_2}{1+\alpha {\mathsf{snr}}_2}\right),\hfill \end{array}$$

where the expression in (86) follows from (79) and the bound in (87) follows by using the bound in (85). This concludes the proof.

6.2. SNR Evolution of Optimal BC Codes

Similarly to the analysis presented in Section 4.2 the I-MMSE relationship can be used also to obtain practical insights and key properties of optimal code sequences for the scalar Gaussian BC. These were shown in [28,87].

The first result we present explains the implications of reliable decoding in terms of the MMSE behavior.

Theorem 12

([28]). Consider a code sequence, transmitting a message pair $(W_1,W_2)$, at rates $(R_1,R_2)$ (not necessarily on the boundary of the capacity region), over the Gaussian BC. $W_2$ can be reliably decoded from ${\mathbf{Y}}_2$ if and only if

$$\begin{array}{c}\hfill {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_2)={\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma ),\forall \gamma \ge {\mathsf{snr}}_2.\end{array}$$

(88)

The above theorem formally states a very obvious observation which is that once $W_2$ can be decoded, it provides no improvement to the estimation of the transmitted codeword, beyond the estimation from the output. This insight is strengthened as it is also a sufficient condition for reliable decoding of the message $W_2$.

The main observation is an extension of the result given in [63], where it was shown that a typical code from the hierarchical code ensemble (which achieves capacity) designed for a given Gaussian BC has a specific SNR-evolution of the MMSE function. This result was extended and shown to hold for any code sequence on the boundary of the capacity region.

Theorem 13

([28]). An achievable code sequence for the Gaussian BC has rates on the boundary of the capacity region, meaning

$$\begin{array}{c}\hfill (R_1,R_2)=\left(\frac{1}{2}\log \left(1+\alpha {\mathsf{snr}}_1\right),\frac{1}{2}\log \left(\frac{1+{\mathsf{snr}}_2}{1+\alpha {\mathsf{snr}}_2}\right)\right),\end{array}$$

(89)

for some $\alpha \in [0,1]$, if and only if it has a deterministic mapping from $(W_1,W_2)$ to the transmitted codeword and

$$\begin{array}{cc}\hfill {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )& =\left\{\begin{array}{cc}\frac{1}{1+\gamma },\hfill & \mathsf{snr}\in [0,{\mathsf{snr}}_2)\hfill \\ \frac{\alpha }{1+\alpha \gamma },\hfill & \gamma \in [{\mathsf{snr}}_2,{\mathsf{snr}}_1)\hfill \\ 0,\hfill & \gamma \ge {\mathsf{snr}}_1\hfill \end{array}\right.,\hfill \end{array}$$

(90)

$$\begin{array}{cc}\hfill {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_2)& =\left\{\begin{array}{cc}\frac{\alpha }{1+\alpha \gamma },\hfill & \mathsf{snr}\in [0,{\mathsf{snr}}_1)\hfill \\ 0,\hfill & \mathsf{snr}\ge {\mathsf{snr}}_1\hfill \end{array}\right..\hfill \end{array}$$

(91)

Note that the above SNR-evolution holds for any capacity achieving code sequence for the Gaussian BC. This includes also codes designed for decoding schemes such as “dirty paper coding”, in which case the decoding at ${\mathbf{Y}}_1$ does not require the reliable decoding of the known “interference” (the part of the codeword that carries the information of $W_2$), but simply encodes the desired messages against that “interference”. In that sense the result is surprising since one does not expect such a scheme to have the same SNR-evolution as a superposition coding scheme, where the decoding is in layers: first the “interference” and only after its removal, the reliable decoding of the desired message.

Figure 12 depicts the result of Theorem 13 for capacity achieving code sequences.

7. Multi-Receiver SNR-Evolution

In this section we extend the results regarding the SNR-evolution of the Gaussian wiretap channel and the SNR-evolution of the Gaussian broadcast channel, given in Section 4.2 and Section 6.2, respectively, to the multi-receiver setting. Moreover, we enhance the graphical interpretation of the SNR-evolution to relate to the basic relevant quantities of rate and equivocation.

More specifically, we now consider a multi-receiver additive Gaussian noise setting in which

$$\begin{array}{c}\hfill {\mathbf{Y}}_i=\sqrt{{\mathsf{snr}}_i}\mathbf{X}+{\mathbf{Z}}_i,\end{array}$$

(92)

where we assume that ${\mathsf{snr}}_1\le {\mathsf{snr}}_2\le \cdots \le {\mathsf{snr}}_K$ for some $K\ge 2$. Since both rate and equivocation are measured according to the conditional densities at the receivers we may further assume that $\mathbf{Z}={\mathbf{Z}}_i$ for all i. Moreover, $\mathbf{X}$ is the transmitted message encoded at the transmitter, assuming a set of some L messages $(W_1,W_2,\dots ,W_L)$. Each receiver may have a different set of requirements regarding these messages. Such requirements can include:

• Reliably decoding some subset of these messages;
• Begin ignorant to some extent regarding some subset of these messages, meaning having at least some level of equivocation regarding the messages within this subset;
• A receiver may be an “unintended” receiver with respect to some subset of messages, in which case we might wish also to limit the “disturbance” these message have at this specific receiver. We may do so by limiting the MMSE of these messages; and
• Some combination of the above requirements.

There might be, of course, additional requirements, but so far the application of the I-MMSE approach as done in [34,70,87,88], was able to analyze these types of requirements. We will now give the main results from which one can consider other specific cases as discussed at the end of this section.

We first consider only reliable communication, meaning a set of messages intended for receivers at different SNRs, in other words, a K-user Gaussian BC.

Theorem 14

([88]). Given a set of messages $(W_1,W_2,\dots ,W_K)$, such that $W_i$ is reliably decoded at ${\mathsf{snr}}_i$ and ${\mathsf{snr}}_1\le {\mathsf{snr}}_2\le \cdots \le {\mathsf{snr}}_K$, we have that

$$\begin{array}{c}\hfill R_i=\frac{1}{2}{\int }_0^{{\mathsf{snr}}_i}{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_{i-1})-{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_i)d\gamma .\end{array}$$

(93)

In the case of $R_1$ the first MMSE is simply ${\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )$ (meaning $W_0=\varnothing$).

Note that due to the basic ordering of the MMSE quantity, meaning that for all $\gamma \ge 0$

$$\begin{array}{c}{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )\ge {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1)\ge {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,W_2)\ge {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,W_2,W_3)\ge \dots ,\hfill \end{array}$$

we have that the integrand is always non-negative. Thus, the above result slices the region defined by ${\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )$ into distinctive stripes defined by the conditional MMSE functions. Each such stripe corresponds to twice the respective rate. The order of the stripes from top to bottom is by the message first decoded to the one last decoded (see Figure 13); further, taking into account Theorem 12, which gives a necessary and sufficient condition for reliable communication in terms of MMSE functions, we know that for $\mathsf{snr}\ge {\mathsf{snr}}_i$ the MMSE conditioned on any message reliably decoded at ${\mathsf{snr}}_i$ equals ${\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )$; thus, we may extend the integration in the above result to any $\mathsf{snr}\ge {\mathsf{snr}}_i$ (or even integrate to infinity).

We now consider in addition to reliable communication also the equivocation measure.

Theorem 15

([88]). Assume a set of independent messages $(W_1,W_2,\dots ,W_i)$ such that $(W_1,W_2,\dots ,W_{i-1})$ are reliably decoded at $\mathbf{Y}\left({\mathsf{snr}}_{i-1}\right)$, however $W_i$ is reliably decoded only at some ${\mathsf{snr}}_i>{\mathsf{snr}}_{i-1}$. The equivocation of $W_i$ at $\mathbf{Y}\left({\mathsf{snr}}_{i-1}\right)$ equals

$$\begin{array}{c}\hfill H\left(W_i\right|\mathbf{Y}\left({\mathsf{snr}}_{i-1}\right))=\frac{1}{2}{\int }_{{\mathsf{snr}}_{i-1}}^{{\mathsf{snr}}_i}{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_{i-1})-{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,W_2,\dots ,W_i)d\gamma ,\end{array}$$

(94)

which can also be written as

$$\begin{array}{c}\hfill H\left(W_i\right|\mathbf{Y}\left({\mathsf{snr}}_{i-1}\right))=\frac{1}{2}{\int }_{{\mathsf{snr}}_{i-1}}^{{\mathsf{snr}}_i}{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )-{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_i)d\gamma .\end{array}$$

(95)

The above result together with Theorem 14 provides a novel graphical interpretation. Theorem 14 divides the area below ${\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma )$ into stripes, each corresponding to a rate. Theorem 15 further divides these stripes horizontally. The stripe corresponding to the rate of message $W_i$ is an area between ${\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,W_2,\dots ,W_{i-1})$ and ${\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,W_2,\dots ,W_i)$ from $[0,{\mathsf{snr}}_i]$. For any point $\mathsf{snr}>{\mathsf{snr}}_i$ this area is then split into the region between $[0,\mathsf{snr}]$ which corresponds to the information that can be obtained regarding the message by $\mathbf{Y}\left(\mathsf{snr}\right)$ and the region $[\mathsf{snr},{\mathsf{snr}}_i]$ which corresponds to the equivocation (see Figure 14 for an example).

Let us now assume complete secrecy, meaning

$$\begin{array}{cc}\hfill H\left(W_i\right|\mathbf{Y}\left({\mathsf{snr}}_{i-1}\right))& =H\left(W_i\right).\hfill \end{array}$$

(96)

Using Theorems 14 and 15 we have that

$$\begin{array}{c}{\int }_0^{{\mathsf{snr}}_i}{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_{i-1})-{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_i)d\gamma =\hfill \\ {\int }_{{\mathsf{snr}}_{i-1}}^{{\mathsf{snr}}_i}{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_{i-1})-{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_i)d\gamma ,\hfill \end{array}$$

(97)

assuming we have reliable decoding of messages $(W_1,W_2,\dots ,W_{i-1})$ at ${\mathsf{snr}}_{i-1}$. This reduces to

$$\begin{array}{c}\hfill {\int }_0^{{\mathsf{snr}}_{i-1}}{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_{i-1})-{\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,\dots ,W_i)d\gamma =0,\end{array}$$

(98)

which due to the non-negativity of the integrand results in

$$\begin{array}{c}\hfill {\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,W_2,\dots ,W_{i-1})={\mathrm{mmse}}_{\infty }(\mathbf{X};\gamma |W_1,W_2,\dots ,W_i),\end{array}$$

(99)

for all $\gamma \in [0,{\mathsf{snr}}_{i-1})$. This is exactly the condition for complete secrecy given in [34]. The important observation here is that to obtain complete secrecy we require that the stripe of the secure message is reduced to the section $[{\mathsf{snr}}_{i-1},{\mathsf{snr}}_i]$, where the eavesdropper is at ${\mathsf{snr}}_{i-1}$ and the legitimate receiver is at ${\mathsf{snr}}_i$. This reduction in the stripe of the secure message can be interpreted as having been used for the transmission of the camouflaging information required for complying with the secrecy constraint.

The above approach can be further extended and can provide a graphical interpretation for more elaborate settings with additional requirements at the receiver. An immediate such example would be adding “disturbance” constraints in terms of MMSEs. Another extension which has been also considered in [88] is the problem of “secrecy outside the bounded range” [89]. For this setting complete secrecy rate can be enhanced by using the inherent randomness in the message which results from the fact that it contains an additional “unintended” message which is not necessarily reliably decoded. For more details on this problem and its graphical interpretation the reader is referred to [88,89].

8. Interference Channels

A two user interference channel (IC), introduced by Ahlswede in [77], depicted in Figure 15, is a system consisting of two transmitters and two receivers. The goal of a transmitter $i\in [1:2]$ is to reliably transmit the message $W_i$ to receiver i. Transmitter i encodes a message $W_i$ into a transmitted codeword ${\mathbf{X}}_i$ of length n. Receiver i receives the sequence ${\mathbf{Y}}_i$ of length n and tries to decode the message $W_i$ from the observed sequence ${\mathbf{Y}}_i$. An achievable rate pair for the IC is defined as follows:

Definition 10.

A rate pair $(R_1,R_2)$ is said to be achievable, if for a message $W_1$ of cardinality $2^{n{R}_1}$ and a message $W_2$ of cardinality $2^{n{R}_2}$ there exists a sequence of encoding functions

$$\begin{array}{cc}\hfill f_{n,1}\left(W_1\right)& ={\mathbf{X}}_1,\hfill \\ \hfill f_{n,2}\left(W_2\right)& ={\mathbf{X}}_2,\hfill \end{array}$$

and decoding functions

$$\begin{array}{cc}\hfill {\widehat{W}}_1& =g_{1,n}\left({\mathbf{Y}}_1\right),\hfill \\ \hfill {\widehat{W}}_2& =g_{2,n}\left({\mathbf{Y}}_2\right),\hfill \end{array}$$

such that

$$\begin{array}{c}\hfill \underset{n\to \infty }{\lim }\mathbb{P}[(W_1,W_2)\ne ({\widehat{W}}_1,{\widehat{W}}_2)]=0,\end{array}$$

(100)

assuming that $W_1$ and $W_2$ are uniformly distributed over their respective message sets.

The capacity region is defined as the closure over all achievable rate pairs. In [77] Ahlswede demonstrated a multi-letter capacity expression given in (49). Unfortunately, the capacity expression in (49) is considered “uncomputable” in the sense that we do not know how to explicitly characterize the input distributions that attain its convex closure. Moreover, it is not clear whether there exists an equivalent single-letter form for (49) in general.

Because of “uncomputability” the capacity expression in (49) has received little attention, except for the following: in [79] the limiting expression was used to show that limiting to jointly Gaussian distributions is suboptimal; in [72] the limiting expression was used to derive the sum-capacity in the very weak interference regime; and in [90] it was shown that in the high-power regime the limiting expression normalized by the point-to-point capacity (i.e., the degrees of freedom (DoF)) can be single letterized.

Instead, the field has focussed on finding alternative ways to characterize single-letter inner and outer bounds. The best known inner bound is the HK achievable scheme [74], which is:

• capacity achieving in the strong interference regime [75,91,92];
• capacity achieving for a class of injective deterministic channels [93,94];
• approximately capacity achieving for a class of injective semi-deterministic channels [95]; and
• approximately capacity achieving (within $1/2$ bit) for a class of Gaussian noise channels (which is a special case of the injective semi-deterministic channel) [76].

It is important to point out that in [96] the HK scheme was shown to be strictly sub-optimal for a class of DMC’s. Moreover, the result in [96] suggests that multi-letter achievable strategies might be needed to achieve capacity of the IC.

8.1. Gaussian Interference Channel

In this section we consider the practically relevant scalar G-IC channel, depicted in Figure 15b, with input-output relationship

$$\begin{array}{cc}\hfill Y_1& =h_{11}{X}_1+h_{12}{X}_2+Z_1,\hfill \end{array}$$

(101a)

$$\begin{array}{cc}\hfill Y_2& =h_{21}{X}_1+h_{22}{X}_2+Z_2,\hfill \end{array}$$

(101b)

where $Z_i$ is i.i.d. zero-mean unit-variance Gaussian noise. For the G-IC in (101), the maximization in (49) is further restricted to inputs satisfying the power constraint $\mathbb{E}\left[X_i^2\right]\le 1$, $i\in [1:2]$.

For simplicity we will focus primarily on the symmetric G-IC defined by

$$\begin{array}{c}|h_{11}{|}^2={\left|h_{22}\right|}^2=\mathsf{snr}\ge 0,\hfill \end{array}$$

(102a)

$$\begin{array}{c}|h_{12}{|}^2={\left|h_{21}\right|}^2=\mathsf{inr}\ge 0,\hfill \end{array}$$

(102b)

and we will discuss how the results for the symmetric G-IC extend to the general asymmetric setting.

In general, little is known about the optimizing input distribution in (49) for the G-IC and only some special cases have been solved. In [71,72,73] it was shown that i.i.d. Gaussian inputs maximize the sum-capacity in (49) for $\sqrt{\frac{\mathsf{inr}}{\mathsf{snr}}}(1+\mathsf{inr})\le \frac{1}{2}$ in the symmetric case. In contrast, the authors of [79] showed that in general multivariate Gaussian inputs do not exhaust regions of the form in (49). The difficulty arises from the competitive nature of the problem [43]: for example, say $X_2$ is i.i.d. Gaussian; taking $X_1$ to be Gaussian increases $I(X_1;Y_1)$ but simultaneously decreases $I(X_2;Y_2)$, as Gaussians are known to be the “best inputs” for Gaussian point-to-point power-constrained channels, but are also the “worst noise” (or interference, if it is treated as noise) for a Gaussian input.

So, instead of pursuing exact results, the community has recently focussed on giving performance guarantees on approximations of the capacity region [97]. In [76] the authors showed that the HK scheme with Gaussian inputs and without time-sharing is optimal to within 1/2 bit, irrespective of the channel parameters.

8.2. Generalized Degrees of Freedom

The constant gap result of [76] provides an exact characterization of the generalized degrees of freedom (gDoF) region defined as

$$\begin{array}{cc}\hfill \mathcal{D}\left(\alpha \right)& :=\left\{(d_1,d_2):d_i:=\underset{\mathsf{snr}\to \infty }{\lim }\frac{R_i(\mathsf{snr},\mathsf{inr}={\mathsf{snr}}^{\alpha })}{\frac{1}{2}\log (1+\mathsf{snr})},i\in [1:2],(R_1,R_2)\mathrm{is}\mathrm{achievable}\right\},\hfill \end{array}$$

(103)

and where $\mathcal{D}\left(\alpha \right)$ was shown to be

$$\begin{array}{c}\hfill \mathcal{D}\left(\alpha \right)=\left\{(d_1,d_2):\begin{array}{cc}{d}_1\hfill & \le 1\hfill \\ d_2\hfill & \le 1\hfill \\ d_1+d_2\hfill & \le {[1-\alpha ]}^{+}+\max (\alpha ,1)\hfill \\ d_1+d_2\hfill & \le \max (1-\alpha ,\alpha )+\max (1-\alpha ,\alpha )\hfill \\ 2d_1+d_2\hfill & \le {[1-\alpha ]}^{+}+\max (1,\alpha )+\max (1-\alpha ,\alpha )\hfill \\ d_1+2d_2\hfill & \le {[1-\alpha ]}^{+}+\max (1,\alpha )+\max (1-\alpha ,\alpha )\hfill \end{array}\right\}.\end{array}$$

(104a)

The region in (104) is achieved by the HK scheme without time sharing; for the details see [42,76].

The $\alpha$ parameter is the strength of the interference in dB. The gDoF is an important metric that sheds light on the optimal coding strategies in the high SNR regime. The gDoF metric deemphasizes the role of noise in the network and only focuses on the role of signal interactions. Often these strategies can be translated to the medium and low SNR regions. The gDoF is especially useful in analyzing interference alignment strategies [98,99] where proper design of the signaling scheme can ensure very high rates. The notion of gDoF has received considerable attention in information theoretic literature and the interested reader is referred to [100] and reference therein.

For our purposes, we will only look at the sum-gDoF of the interference channel given by

$$\begin{array}{c}\hfill d_{\mathrm{\Sigma }}\left(\alpha \right)=\underset{(d_1,d_2)\in \mathcal{D}\left(\alpha \right)}{\max }{d}_1+d_2=2\min \left(1,\max \left(\frac{\alpha }{2},1-\frac{\alpha }{2}\right),\max (\alpha ,1-\alpha )\right).\end{array}$$

(105)

The sum-gDoF in (105) as a function of the parameter $\alpha$ is plotted in Figure 16. The curve in Figure 16 is often called the W-curve.

Depending on the parameters $(\mathsf{snr},\mathsf{inr}={\mathsf{snr}}^{\alpha })$ we identify the following operational regimes: very strong interference, $\alpha \ge 2$; strong interference, $1\le \alpha <2$; weak interference type I, $2/3\le \alpha <1$; weak interference type II, $1/2\le \alpha <2/3$; very weak interference, $0\le \alpha <1/2$.

8.3. Treating Interference as Noise

An inner bound on the capacity region in (49) can be obtained by considering i.i.d. inputs in (49) thus giving

$$\begin{array}{cc}\hfill {\mathcal{R}}_{\mathrm{in}}^{\mathrm{TIN}+\mathrm{TS}}& =\mathsf{co}\left(\bigcup _{P_{X_1{X}_2}=P_{X_1}{P}_{X_2}}\left\{\begin{array}{c}0\le R_1\le I(X_1;Y_1)\hfill \\ 0\le R_2\le I(X_2;Y_2)\hfill \end{array}\right\}\right),\hfill \end{array}$$

(106)

where the superscript “TIN+TS” reminds the reader that the region is achieved by treating interference and noise and with time sharing (TS), where TS is enabled by the convex hull operation [42]. By further removing the convex hull operation in (106) we arrive at

$$\begin{array}{cc}\hfill {\mathcal{R}}_{\mathrm{in}}^{\mathrm{TINnoTS}}& =\bigcup _{P_{X_1{X}_2}=P_{X_1}{P}_{X_2}}\left\{\begin{array}{c}0\le R_1\le I(X_1;Y_1)\hfill \\ 0\le R_2\le I(X_2;Y_2)\hfill \end{array}\right\}.\hfill \end{array}$$

(107)

The region in (107) does not allow the users to time-share.

Obviously

$$\begin{array}{c}\hfill {\mathcal{R}}_{\mathrm{in}}^{\mathrm{TINnoTS}}\subseteq {\mathcal{R}}_{\mathrm{in}}^{\mathrm{TIN}+\mathrm{TS}}\subseteq \mathcal{C}.\end{array}$$

The question of interest in this section is how ${\mathcal{R}}_{\mathrm{in}}^{\mathrm{TINnoTS}}$ fares compared to $\mathcal{C}$. Note that there are many advantages in using TINnoTS in practice. For example, TINnoTS does not require codeword synchronization, as for example for joint decoding or interference cancellation, and does not require much coordination between users, thereby reducing communications overhead. Therefore, an interesting question that arises is: What are the limits of the TIN region?

By evaluating the TIN region with Gaussian inputs we get an achievable sum-gDoF of

$$\begin{array}{c}\hfill d_{\mathrm{\Sigma }}^{\mathrm{TIN}-\mathrm{G}}\left(\alpha \right)=2\max (0,1-\alpha ),\end{array}$$

(108)

shown by a red curve in Figure 16. Clearly, using Gaussian inputs in the TIN region is gDoF optimal in the very weak interference regime and is otherwise strictly suboptimal. Because Gaussian inputs are often mutual information maximizers, one might think that the expression in (108) is the best that we can hope for. However, this intuition can be very misleading, and despite the simplicity of TIN, in [45] TINnoTS was shown to achieve capacity $\mathcal{C}$ within a gap which also implies that TIN is gDoF optimal. The key observation is to use non-Gaussian inputs, specifically the mixed inputs presented in Section 5.5.

Theorem 16

([45]). For the G-IC, as defined in (102), the TINnoTS achievable region in (107) is optimal to within a constant gap, or a gap of order $O\left(\log \log \right(\min (\mathsf{snr},\mathsf{inr})\left)\right)$, and it is therefore gDoF optimal.

Next, we demonstrated the main ideas behind Theorem 16. The key to this analysis is to use mixed inputs, presented in Section 5.5, and given by

$$\begin{array}{cc}\hfill X_i& =\sqrt{1-{\delta }_i}{X}_{iD}+\sqrt{{\delta }_i}{X}_{iG},i\in [1:2]:\hfill \end{array}$$

(109a)

$$\begin{array}{c}{X}_{iD}\sim \mathsf{PAM}\left(N_i,\sqrt{\frac{12}{N_i^2-1}}\right),\hfill \end{array}$$

(109b)

$$\begin{array}{c}{X}_{iG}\sim \mathcal{N}(0,1),\hfill \end{array}$$

(109c)

where the random variables $X_{ij}$ are independent for $i\in [1:2]$ and $j\in \{D,G\}$. Inputs in (109) have four parameters, namely the number of points $N_i\in \mathbb{N}$ and the power split ${\delta }_i\in [0,1]$, for $i\in [1:2]$, which must be chosen carefully in order to match a given outer bound.

By evaluating the TIN region in (107) with mixed inputs in (109) we arrive at the following achievable region.

Proposition 8.

(TIN with Mixed Inputs [45]) For the G-IC the TINnoTS region in (107) contains the region ${\mathcal{R}}_{\mathrm{in}}$ defined as

$$\begin{array}{c}{\mathcal{R}}_{\mathrm{in}}:=\hfill \\ \bigcup \left\{\begin{array}{c}0\le R_1\le I\left(S_1,S_1+Z_1\right)+\frac{1}{2}\log \left(1+\frac{|h_{11}{|}^2{\delta }_1}{1+|h_{12}{|}^2{\delta }_2}\right)-\min \left(\log \left(N_2\right),\frac{1}{2}\log \left(1+\frac{|h_{12}{|}^2(1-{\delta }_2)}{1+|h_{12}{|}^2{\delta }_2}\right)\right)\hfill \\ 0\le R_2\le I\left(S_2;S_2+Z_2\right)+\frac{1}{2}\log \left(1+\frac{|h_{22}{|}^2{\delta }_2}{1+|h_{21}{|}^2{\delta }_1}\right)-\min \left(\log \left(N_1\right),\frac{1}{2}\log \left(1+\frac{|h_{21}{|}^2(1-{\delta }_1)}{1+|h_{21}{|}^2{\delta }_1}\right)\right)\hfill \end{array}\right\},\hfill \end{array}$$

(110)

where the union is over all possible parameters $[N_1,N_2,{\delta }_1,{\delta }_2]\in {\mathbb{N}}^2\times {[0,1]}^2$ for the mixed inputs in (109) and where the equivalent discrete constellations seen at the receivers are

$$\begin{array}{c}{S}_1:=\frac{\sqrt{1-{\delta }_1}{h}_{11}{X}_{1D}+\sqrt{1-{\delta }_2}{h}_{12}{X}_{2D}}{\sqrt{1+|h_{11}{|}^2{\delta }_1+{\left|h_{12}\right|}^2{\delta }_2}},\hfill \end{array}$$

(111a)

$$\begin{array}{c}{S}_2:=\frac{\sqrt{1-{\delta }_1}{h}_{21}{X}_{1D}+\sqrt{1-{\delta }_2}{h}_{22}{X}_{2D}}{\sqrt{1+|h_{21}{|}^2{\delta }_1+{\left|h_{22}\right|}^2{\delta }_2}}.\hfill \end{array}$$

(111b)

Next, we select the parameters $[N_1,N_2,{\delta }_1,{\delta }_2]$ to optimize the region in (110). For simplicity, we focus only on the very strong interference regime ($\alpha \ge 2$). The gDoF optimality of TIN in the very strong interference regime is perhaps the most surprising. The capacity in this regime has been shown by Carleial in [91] who demonstrated that capacity can be achieved with a successive cancellation decoding strategy where the interference is decoded before the desired signal. Unlike the Carleial scheme TIN only use a point-to-point decoder for non-Gaussian noise and can be classified as a soft-interference-decoding strategy discussed in Section 5.1.

In the very strong interference ($\alpha \ge 2$) regime the sum-gDoF is given by

$$\begin{array}{c}\hfill d_{\mathrm{\Sigma }}\left(\alpha \right)=2.\end{array}$$

(112)

To show that TIN can achieve the gDoF (112), let the parameters in (110) be given by $N=N_1=N_2=\lfloor \sqrt{1+\mathsf{snr}}\rfloor$ and ${\delta }_1={\delta }_2=0$. It is not difficult to see that with this choice of inputs the rate in (110) is given by

$$\begin{array}{cc}\hfill R_i& =I\left(S_i,S_i+Z_i\right)-\min \left(\log \left(N\right),\frac{1}{2}\log \left(1+\mathsf{inr}\right)\right)\hfill \\ & \ge I\left(S_i,S_i+Z_i\right)-\log \left(N\right).\hfill \end{array}$$

Therefore, the key now is to lower bound $I\left(S_i,S_i+Z_i\right)$. This is done by using the Ozarow-Wyner bound in (35b).

Lemma 2.

Let $N=N_1=N_2=\lfloor \sqrt{1+\mathsf{snr}}\rfloor$ and ${\delta }_1={\delta }_2=0$. Then,

$$\begin{array}{cc}\hfill I\left(S_i,S_i+Z_i\right)& \ge 2\log \left(N\right)-\frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{3}\right).\hfill \end{array}$$

(113)

Proof. 

Using the Ozarow-Wyner bound in (35b)

$$\begin{array}{cc}\hfill I\left(S_i,S_i+Z_i\right)& \ge H\left(S_i\right)-\frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{6}\right)-\frac{1}{2}\log \left(1+\frac{12\mathrm{mmse}(S_i,1)}{d_{\min }{\left(S_i\right)}^2}\right)\hfill \\ & \stackrel{a)}{\ge }H\left(S_i\right)-\frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{6}\right)-\frac{1}{2}\log \left(1+\frac{12\mathrm{mmse}(S_i,1)}{\mathsf{snr}{d}_{\min }{\left(X_i\right)}^2}\right)\hfill \\ & \stackrel{b)}{\ge }H\left(S_i\right)-\frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{6}\right)-\frac{1}{2}\log \left(1+\frac{12(\mathsf{snr}+\mathsf{inr})}{(1+\mathsf{snr}+\mathsf{inr})\mathsf{snr}{d}_{\min }{\left(X_i\right)}^2}\right)\hfill \\ & \stackrel{c)}{\ge }H\left(S_i\right)-\frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{6}\right)-\frac{1}{2}\log \left(1+\frac{(\mathsf{snr}+\mathsf{inr})}{(1+\mathsf{snr}+\mathsf{inr})}\right)\hfill \\ & \stackrel{d)}{\ge }H\left(S_i\right)-\frac{1}{2}\log \left(\frac{\pi \mathrm{e}}{3}\right),\hfill \end{array}$$

where the (in)-equalities follow from: (a) using the bound $d_{\min }\left(S_i\right)\ge \min (\sqrt{\mathsf{snr}}{d}_{\min }\left(X_1\right),$ $\sqrt{\mathsf{inr}}{d}_{\min }\left(X_2\right))$; (b) using the LMMSE bound in (11); (c) using the bound $d_{\min }{\left(X_i\right)}^2=\frac{12}{N_i^2-1}\ge \frac{12}{\mathsf{snr}}$; and (d) using the bound $\frac{(\mathsf{snr}+\mathsf{inr})}{(1+\mathsf{snr}+\mathsf{inr})}\le 1$.

The proof is concluded by observing that in the very strong interference regime with the choice $N=N_1=N_2=\lfloor \sqrt{1+\mathsf{snr}}\rfloor$, the entropy of a sum-set is given by

$$\begin{array}{c}\hfill H\left(S_i\right)=H\left(X_1\right)+H\left(X_2\right)=2\log \left(N\right).\end{array}$$

☐

Therefore, the sum-gDoF of TIN is given by

$$\begin{array}{cc}\hfill \underset{\mathsf{snr}\to \infty }{\lim }\frac{R_1+R_2}{\frac{1}{2}\log (1+\mathsf{snr})}& \ge \underset{\mathsf{snr}\to \infty }{\lim }\frac{2\log \left(N\right)-\log \left(\frac{\pi \mathrm{e}}{3}\right)}{\frac{1}{2}\log (1+\mathsf{snr})}\hfill \\ & =\underset{\mathsf{snr}\to \infty }{\lim }\frac{2\log \left(\lfloor \sqrt{1+\mathsf{snr}}\rfloor \right)-\log \left(\frac{\pi \mathrm{e}}{3}\right)}{\frac{1}{2}\log (1+\mathsf{snr})}=2.\hfill \end{array}$$

This concludes the proof of the achievability for the very strong interference regime.

Using the same ideas as in the proof for the very strong interference regime one can extend the optimality of TIN to other regimes.

9. Concluding Remarks and Future Directions

This section concludes this work by summarizing some interesting future directions.

One of the intriguing extensions of the I-MMSE relationship is the gradient formula, obtained by Palomar and Verdú [9]:

$$\begin{array}{c}\hfill {\nabla }_{\mathbf{H}}I(\mathbf{X};\mathbf{H}\mathbf{X}+\mathbf{Z})=\mathbf{H}\mathbb{E}\left[(\mathbf{X}-\mathbb{E}[\mathbf{X}\mid \mathbf{H}\mathbf{X}+\mathbf{Z}]){(\mathbf{X}-\mathbb{E}[\mathbf{X}\mid \mathbf{H}\mathbf{X}+\mathbf{Z}])}^{\mathsf{T}}\right].\end{array}$$

(114)

The expression in (114) has been used to study MIMO wiretap channels [101], extensions of Costa’s EPI [102], and the design of optimal precoders for MIMO Gaussian channels [103].

However, much work is needed to attain the same level of maturity for the gradient expression in (114) as for the original I-MMSE results [8]. For example, it is not clear what is the correct extension (or if it exists) of a matrix version of the SCPP in Proposition 4. A matrix version of the SCPP could facilitate a new proof of the converse of the MIMO BC by following the steps of Section 6.1. The reader is referred to [33] where the SCPP type bounds have been extended to several classes of MIMO Gaussian channels.

Estimation theoretic principles have been instrumental in finding a general formula for the DoF for a static scalar K-user Gaussian interference channel [90], based on notions of the information dimension [104] and the MMSE dimension [32]. While the DoF is an important measure of the network performance it would be interesting to see if the approach of [90] could be used to analyze the more robust gDoF measure. Undoubtedly, such an extension will rely on the interplay between estimation and information measures.

"Information bottleneck" type problems [105] are defined as

$$\begin{array}{c}\underset{Y}{\min }I(X;Y,Z)\hfill \end{array}$$

(115a)

$$\begin{array}{c}\mathrm{s}.\mathrm{t}.I(X;Y)=C,\hfill \end{array}$$

(115b)

where $X\sim \mathcal{N}(0,1)$, $Z=\sqrt{\mathsf{snr}}X+N$ with $N\sim \mathcal{N}(0,1)$ independent of X and Y. A very elegant solution to (115) can be found by using the I-MMSE, the SCPP, and the argument used in the proof of the converse for the Gaussian BC in Section 6.1. It would be interesting to explore whether other variants of the bottleneck problem can be solved via estimation theoretic tools. For example, it would be interesting to consider

$$\begin{array}{c}\underset{X,Z}{\max }I(X;Z)\hfill \end{array}$$

(116a)

$$\begin{array}{c}\mathrm{s}.\mathrm{t}.I(Y;Z)\le C,\hfill \end{array}$$

(116b)

where $X\leftrightarrow Y\leftrightarrow Z$ and $Y=\sqrt{\mathsf{snr}}X+N$ where $N\sim \mathcal{N}(0,1)$ and independent of X.

The extremal entropy inequality of [106], inspired by the channel enhancement method [107], was instrumental in showing several information theoretic converses in problems such as the MIMO wiretap channel [108], two-user Gaussian interference channel [71,72,73], and cognitive interference channel [109] to name a few. In view of the successful applications of the I-MMSE relationship to prove EPI type inequalities (e.g., [35,36,38,102]), it would be interesting to see if the extremal inequality presented in [106] can be shown via estimation theoretic arguments. Existence of such a method can reveal a way of deriving a large class of extremal inequalities potentially useful for information theoretic converses.

The extension of the I-MMSE results to cases that allow $\mathsf{snr}$ dependency of the input signal have been derived and shown to be useful in [10]. An interesting future direction is to consider the MMPE while allowing $\mathsf{snr}$ dependency of the input signal; such a generalization has the potential of being useful when studying feedback systems as did the generalization of the MMSE in [10].

Another interesting direction is to study sum-rates of arbitrary networks with the use of the Ozarow-Wyner bound in Theorem 4. Note that, the Ozarow-Wyner bound holds for an arbitrary transition probability and the rate of an arbitrary network with n independent inputs and outputs can be lower bounded as

$$\begin{array}{c}\hfill \sum _i{R}_i=I(X_1,...,X_n;Y_1,...,Y_n)\ge \sum _{i}H\left(X_i\right)-\mathsf{gap},\end{array}$$

(117)

where the $\mathsf{gap}$ term is explicitly given in Theorem 4 and is a function of the network transition probability.