K-user Interference Channels: General Outer Bound and Sum-capacity for Certain Gaussian Channels

I Introduction

The goal of this paper is to derive an outer bound for the $K$-IFC that holds for any memoryless channel (not necessarily Gaussian) and for any $K\geq 2$.

The capacity region of the 2-IFC is known if the interference is strong , if the channel outputs are deterministic and invertible functions of the inputs , and if the channel has a special form of degradeness . The largest known inner bound is due to Han and Kobayashi (HK) and uses rate splitting and joint decoding. General outer bounds are due to Sato , and Carleial (see also Kramer [10, Th.5]).

For the Gaussian 2-IFC, the capacity region is fully known in strong interference only . The sum-capacity is however known in mixed interference , for the Z-channel , and in very weak interference . In mixed and weak interference, a simple rate splitting in the HK region is optimal to within one bit . The best outer bound may be obtained by intersecting the regions derived by Kramer in , by Etkin et al. in , and the region independently obtained in and later tighten by Etkin in .

Few results are available for more than two users and/or for non-Gaussian channels. Please refer to , and references therein, for a more detailed discussion of the past work that we shall only briefly list in the following for sake of space.

General inner bound regions are lacking. A straightforward generalization of the HK approach, whereby each user has a different message for every subset of non-intended receivers, has a super-exponential complexity in the number of users and might be suboptimal in general. In fact, coding schemes that deal directly with the effect of the aggregate interference, rather than with each interferer separately, as with interference alignment and with structured codes , are known to achieve a larger number of degrees of freedom than simple HK schemes for the Gaussian noise channel . To the best of the author’s knowledge, no outer bounds have been developed for the general (i.e., non-Gaussian) IFC with more than two users.

In Gaussian noise, channels with a special structure have been investigated such as: the “fully symmetric” channel , the “cyclic symmetric” channel, the three-user channel with “cyclic mixed strong-very strong” interference , and the “one-to-many” and the “many-to-one” channel . The Degrees of Freedom (DoF) of the Gaussian $K$-IFC has received more attention ; the lesson from the DoF analysis is that structured codes appear to outperform purely random codes and that the high-SNR analysis is very sensitive to the way the $K^{2}$ parameters of the $K$-IFC are let grow to infinity.

Of direct relevance for this work are the Gaussian 2-IFC outer bounds derived by Kramer in [10, Th.1] and by Etkin et al. in , which we seek to generalize to any memoryless channel with any number of users. The basic idea is to give side information to the receiver(s) in such a way that the resulting bound can be single-letterized, does not involve auxiliary random variables and can be computed for channels of interest, such as the Gaussian channel. An extension of [10, Th.1, first proof] to the $K$-user Gaussian channel, with any $K\geq 2$, appeared in ; the idea is to provide a group of receivers with sufficient side information so that they can decode a subset of the users as in a Multiple Access Channel (MAC) channel–as also discussed in ; the resulting optimization problem however does not appears to have a closed-form solution in general (a closed form result was given in for degraded channels only) and iterative algorithms for its numerical evaluation are discussed in . In this work, we will approach the problem from a different angle: we generalize [10, Th.1, second LMMSE-based proof] rather than [10, Th.1, first “general optimization problem”-based proof]. We will show that our bound can be evaluated in closed-form for certain Gaussian channels and it is sum-capacity for some classes of channels. Extensions of [18, Th.1] to the $K$-user Gaussian channel appeared in . In both works, the receivers are given a side information signal that generalizes that of [18, Th.1] whereby entropy terms are related by using the entropy power (EPI) and/or the extremal inequality (EI) rather than chosen so that they cancel one another. In this work we simply generalize the approach of [18, Th.1] to any memoryless channel as it is not obvious what EPI and/or EI are for a general channel.

I-B Contributions and Paper Organization

In Section II we derive an outer bound on the capacity region of the general memoryless IFC, i.e., not necessarily Gaussian, with an arbitrary number of source-destination pairs.

In Section III we specialize the bound derived in Section II to the Gaussian channel. In , we showed that there exist channel parameters for which our proposed bound is the tightest known for the sum-rate of the Gaussian 3-IFC. Here, we derive the sum-capacity of certain Z-like Gaussian $K$-IFCs. We also discuss how to generalize this sum-capacity result to non-Z Gaussian channels; in particular we offer two alternative proofs for the sum-capacity of the Gaussian degraded channel originally derived in .

Section IV concludes the paper. Some of the proofs are in the Appendix.

II Main Result

The capacity region of a general memoryless $K$-IFC is contained into:

The details of the proof may be found in the Appendix. The key idea is to provide the $k$-th receiver, $k\in[1:K]$, with the side information $S_{k}$ shown in Fig. 2. ∎

Th.1 holds for any memoryless IFC and for any number of users.

Since the capacity region of a $K$-user IFC does not depend on the joint transition probability $P_{Y_{1},\ldots,Y_{K}|X_{1},\ldots,X_{K}}$ (because the receivers cannot cooperate), but only on the marginal transition probabilities $P_{Y_{k}|X_{1},\ldots,X_{K}}$, $k\in[1:K]$, each bound in Th. 1 (one for each pair $(\mathcal{S},\pi)$) can be optimized with respect to the joint probability $P_{Y_{1},\ldots,Y_{K}|X_{1},\ldots,X_{K}}$ as long as the marginal probabilities are preserved.

The bound in (1a) reduces to [10, Th.1] for the Gaussian 2-IFC when $\mathcal{X}_{3}=\emptyset$ (see [10, eq.(34)] which inspired the side information structure given on the left side of Fig. 2).

The bound in (1b) reduces to [18, Th.1] for the Gaussian 2-IFC when $\mathcal{X}_{3}=\emptyset$ by setting $S_{1}=Y_{\backslash 2}$ and $S_{2}=Y_{\backslash 1}$. The bound in (1b) is tighter than [18, Th.1] because the correlation coefficient between the Gaussian noise of the channel output $Y_{k}$ and the Gaussian noise of the side information $Y_{\backslash\pi_{k}}$, $(k,\pi_{k})\in[1:K]^{2}$, can be optimized so as to get the tightest bound. It is however not tighter than the bound independently obtained in for the 2-user Gaussian channel.

From (1a) we get $N(K)=\sum_{k=1}^{K}{K\choose k}k!$ rate bounds. For $K=2$, the $N(2)=4$ bounds are as in [10, Th.1] (two single-rate bounds and two sum-rate bounds). For $K\geq 3$, the $N(K)-K^{2}$ bounds that involve at least three rates cannot be simply derived by silencing all but two users and then by applying [10, Th.1] to the resulting 2-IFC. The number of bounds grows exponentially with $K$: $N(3)=15,$ $N(4)=52,$ $N(5)=325,$ etc.

Similarly, from (1b) we get $N(K)$ bounds; those that involve at least three rates cannot be obtained by simply applying the 2-IFC sum-rate bound in [18, Th.1].

Th.1 can be easily evaluated. For example, the “Gaussian maximizes entropy” suffices to guarantee that a jointly Gaussian input is optimal for Gaussian channels.

Th.1 can be extended to other memoryless channels without receiver cooperation. For example, the 2-user cognitive channel was considered in , the 2-IFC with a cognitive relay in , and the 2-IFC with generalized feedback (a.k.a. source cooperation) in .

For the $K$-IFC with generalized feedback for example, Th.1 must be modified as follows: (a) replace each channel output $Y_{k}$ with the pair $(Y_{k},Y_{{\rm GF,}k})$, where $Y_{{\rm GF,}k}$ is the channel output observed at transmitter $k$, $k\in[1:K]$, (b) consider the union over all possible joint input distributions $P_{X_{1},\ldots,X_{K}}$ (because the generalized feedback enables source cooperation which results in correlated inputs); (c) choose the worst joint transition probability $P_{Y_{1},\ldots,Y_{K}|X_{1},\ldots,X_{K},Y_{{\rm GF,}1},\ldots,Y_{{\rm GF,}K}}$ that preserves the marginals $P_{Y_{k}|X_{1},\ldots,X_{K},Y_{{\rm GF,}1},\ldots,Y_{{\rm GF,}K}}$, $k\in[1:K]$.

Similar extensions are possible for other channels.

For the Gaussian 2-IFC, besides the bounds in and in that we generalized in Th.1, the following outer bounds are known: [10, Th.2] and . These bounds are tighter than [18, Th.1] for some weak interference parameters. It is left for future work to generalize these 2-user Gaussian channel bounds to non-Gaussian channels with more than two users. We note that the common feature of these bounds is to generalize the class of genie signals of [18, Th.1] by relating entropy terms rather than canceling them (see proof of Th.1); this is done by using the entropy power (EPI) and/or the extremal inequality (EI) ; the extension of the EPI and/or the EI to general (i.e., non-Gaussian) channels is not trivial.

III Gaussian channels

In this section we first introduce the Gaussian channel model (subsection III-A). We then show that Th.1 eq. (1a) gives the sum-capacity for certain Z-channels (subsection III-B). We conclude with Subsection III-C where we discuss how to extend the result of Subsection III-B to non-Z channels; in doing so we show that Th.1 eq. (1a) gives the sum-rate capacity of degraded channels, thereby providing an alternative proof for the result of ; we also offer an alternate proof for the sum-rate capacity of the degraded Gaussian $K$-IFC by generalizing an argument originally devised by Sato for the degraded Gaussian 2-IFC .

A SISO (single input single output) complex-valued Gaussian $K$-IFC in standard form has outputs:

In the following we adopted the Matlab-like convention that $\bm{H}_{\mathcal{R},\mathcal{C}}$ in the $|\mathcal{R}|\times|\mathcal{C}|$ matrix obtained from $\bm{H}$ by retaining the rows indexed by $\mathcal{R}$ and the columns indexed by $\mathcal{C}$.

III-B Sum-capacity of Z-like channels

Here we consider a class of Gaussian $K$-IFCs for which the channel matrix $\bm{H}$ is upper triangular. This class of channels can be thought of as the multi-user generalization of the 2-IFC Z-channel . The following theorem establishes the sum-capacity for a subset of Z-channels for which treating interference as noise is optimal:

Consider a $K\times K$ noise covariance matrix $\bm{\Sigma}_{K}$ defined recursively as follows: let $\bm{\Sigma}_{1}=$ and $\forall k=2,\ldots,K$ let

Consider a channel matrix $\bm{H}$ whose upper triangular part is defined recursively as follows: for $k=K,\ldots,2$

while the entries below the main diagonal of $\bm{H}$ are zero. For the channel defined by (2), the sum-rate capacity is given by (1a) and equals:

Since every mutual information term in (1a) contains all the inputs, the “Gaussian maximizes entropy” principle assures that iid $\mathcal{N}(0,1)$ inputs are optimal. Consider $\mathcal{S}=[1:K]$ with $\pi=(1,\ldots,K)$ in (1a) and rewrite the sum-rate as:

The channel matrix $\bm{H}$ defined by (2) is such that for each $k=K,\ldots,2$:

that is, conditioned on $(X_{1},\ldots,X_{k-1})$ the set of outputs $(Y_{1},\ldots,Y_{k-1})$ is a degraded version of $Y_{k}$ and thus:

By summing the rates in (6) over all $k\in[1:K]$ we obtain the sum-rate upper bound in (3). The upper bound in (3) can be achieved by simply treating interference as noise at each receiver (recall that for the Z-channel, the $k$-th receiver is interfered by $(X_{k+1},\ldots,X_{K})$ only). ∎

By considering all possible covariance matrices $\bm{\Sigma}_{K}$, Th.2 identifies a novel class of channels for which treating interference as noise is sum-rate optimal (besides those in [17, Th.4, Th.5, and Th.7] and [35, Th.3]) as shown in the following examples. The correspondence between channel matrices and noise covariance matrices given by (2) is interesting in itself and deserves further analysis.

Example 1. Th.2 assures that treating interference as noise is optimal for all channels that can be built as in (2) from a covariance matrix of the type:

The resulting channel has gains $h_{1,k}=v_{k}h_{k,k}$, $k=2,\ldots,K$ and zero for the remaining non-diagonal entries; this channel is to the so-called many-to-one channel . The condition $\sum_{k=2}^{K}|v_{k}|^{2}\leq 1$ identifies a subset of many-to-one channels for which treating interference as noise is optimal. The condition $\sum_{k=2}^{K}|v_{k}|^{2}\leq 1$ is equivalent to [17, Th.4], thus Th.2 generalizes [17, Th.4].

The relationship between the class of channels identified by Th.2 and that identified by [35, Th.3] (of which [17, Th.4 and Th.5] are special cases) is subject of current investigation. We note that [35, Th.3] is obtained from a generalization of [18, Th.1] while Th.2 from a generalization of [10, Th.1], it is thus possible that [35, Th.3] and Th.2 do not imply one another.

Example 2. Consider channels that can be obtained as in (2) from a rank-one covariance matrix of the type:

In the next subsection we relate the channels considered in Example 2 with the class of degraded channels studied in .

III-C Sum-capacity of non-Z channels

The condition expressed by (2) is only sufficient for the achievability of (3). In general, the expression in (3) is an upper bound to the sum-capacity of channels for which the upper triangular part of $\bm{H}$ can be expressed as in (2) and the entries below the main diagonal have any arbitrary value. For such channels, the entries below the main diagonal might need to satisfy some extra constraints (besides (2)) in order for (3) to be achievable. The following discusses an example of such extra constraints.

The expression in (3) suggests the following achievable strategy for non-Z channels: the $k$-th receiver first decodes users $1,\ldots,k-1$, then strip them from its received signal, and finally decodes its intended message by treating the signal of users $k+1,\ldots,K$ as noise; with this “successive decoding strategy” the rate-tuplet $(r_{1},\ldots,r_{K})$ in (6) is achievable if:

The sum-rate in (3) is achievable for a channel $\bm{H}$ such that the upper triangular part of $\bm{H}$ can be expressed as in (2) and such that the entries below the main diagonal satisfy:

for $(r_{1},\ldots,r_{K})$ defined in (6).

The proof follows from the previous discussion. The achievable region in Th.3 is the intersection of $K$ MAC regions where only the constraints that involve the intended rate have been retained. ∎

Degraded channels, that is, channels for which $\bm{H}$ has rank one, satisfy the assumptions of Th.3.

Consider a $K$-IFC with unit rank channel matrix $\bm{H}=\bm{a}\bm{b}^{H}$, for some $K$-length column vectors $\bm{a}$ and $\bm{b}$ (notice that these channels have upper triangular part as in Example 2 with $b_{k}^{*}=h_{k,k}/a_{k}$). Without loss of generality, assume that the entries of the vector $\bm{a}$ satisfy $|a_{1}|\leq|a_{2}|...\leq|a_{K}|$. With this ordering the channel outputs from a Markov chain:

For this channel, clearly the $k$-th decoder can decode all users with index $i<k$ without imposing any rate penalty to these users; thus sum-rate in (3) is achievable. ∎

Corollary 4 offers a simple proof for the sum-capacity result of ; this implies that Th.3 generalizes the result of .

Another proof for the converse part of Corollary 4 can be obtained by generalizing the bound for the degraded Gaussian 2-IFC proposed by Sato in . We have:

The capacity of the Gaussian $K$-IFC with channel matrix $\bm{H}=\bm{a}\bm{b}^{H}$, such that $|a_{1}|\leq|a_{2}|...\leq|a_{K}|$, is outer bounded by:

for all $\beta_{k}\geq 0$, $k\in[1:K]$, such that $\sum_{k=1}^{K}\beta_{k}=1$.

By using the outer bound in Th.5 we have the following very simple proof for the converse part of Corollary 4: by letting $\beta_{u}\|\bm{b}\|^{2}=|b_{k}|^{2}$ in (8) we immediately obtain the upper bound in (3), which is equivalent to (7) with $b_{k}^{*}=h_{k,k}/a_{k}$.

IV Conclusions

In this work we developed a framework to derive an outer bound for the general memoryless interference channel with an arbitrary number of source-destination pairs. For the Gaussian channel, we showed that the proposed bound gives the sum-capacity for certain channels, including some Z-channels and degraded channels.

Proof of (1a). Consider a non-empty subset $\mathcal{S}$ of $[1:K]$ and let $\mathcal{S}^{c}$ be its complement in $[1:K]$. Consider without loss of generality the permutation $\pi=(1,2,\ldots,|S|)$ (the others are obtained by relabeling the users). We use the following conventions: for a set $\mathcal{S}$, $W(\mathcal{S})=\{W_{i}:i\in\mathcal{S}\}$. We have:

where the different (in)equalities follow from: (a) Fano’s inequality, (b) non-negativity of mutual information (i.e., add side information at the receivers as in Fig. 2), (c) independence of messages (and thus of codewords), (d) chain rule for mutual information, (e) swap order of summation, (f) chain rule for mutual information, (g) “conditioning reduces entropy”, memoryless property of the channel, and by introducing a “time sharing” random variable $Q$ uniformly distributed on $[1:n]$ and independent of everything else.

Proof of (1b). Consider a non-empty subset $\mathcal{S}$ of $[1:K]$,

A good candidate for the side information is as in Fig. 2 inspired by

where we defined $Y_{\backslash k}\sim Y_{k}|_{X_{k}}$.

Acknowledgment

This work was partially funded by NSF under award number 0643954. The contents of this article are solely the responsibility of the authors and do not necessarily represent the official views of the NSF.

References