# Incremental Relaying for the Gaussian Interference Channel with a Degraded
Broadcasting Relay ††thanks:  Manuscript received November 7, 2011; revised
August 9, 2012 and Nov 24, 2012; accepted Dec 7, 2012. Date of current version
December 12, 2012. This work was supported by the Natural Science and
Engineering Research Council (NSERC) of Canada. The material in this paper has
been presented in part at Allerton Conf. Commun., Control and Computing, Sept.
2011. ††thanks: The authors are with The Edward S. Rogers Sr. Department of
Electrical and Computer Engineering, University of Toronto, Toronto, ON M5S
3G4 Canada (email<EMAIL_ADDRESS>weiyu@comm.utoronto.ca).

Lei Zhou, Student Member, IEEE and Wei Yu, Senior Member, IEEE

###### Abstract

This paper studies incremental relay strategies for a two-user Gaussian relay-
interference channel with an in-band-reception and out-of-band-transmission
relay, where the link between the relay and the two receivers is modelled as a
degraded broadcast channel. It is shown that generalized hash-and-forward
(GHF) can achieve the capacity region of this channel to within a constant
number of bits in a certain weak-relay regime, where the transmitter-to-relay
link gains are not unboundedly stronger than the interference links between
the transmitters and the receivers. The GHF relaying strategy is ideally
suited for the broadcasting relay because it can be implemented in an
incremental fashion, i.e., the relay message to one receiver is a degraded
version of the message to the other receiver. A generalized-degree-of-freedom
(GDoF) analysis in the high signal-to-noise ratio (SNR) regime reveals that in
the symmetric channel setting, each common relay bit can improve the sum rate
roughly by either one bit or two bits asymptotically depending on the
operating regime, and the rate gain can be interpreted as coming solely from
the improvement of the common messages rate, or alternatively in the very weak
interference regime as solely coming from the rate improvement of the private
messages. Further, this paper studies an asymmetric case in which the relay
has only a single single link to one of the destinations. It is shown that
with only one relay-destination link, the approximate capacity region can be
established for a larger regime of channel parameters. Further, from a GDoF
point of view, the sum-capacity gain due to the relay can now be thought as
coming from either signal relaying only, or interference forwarding only.

###### Index Terms:

Approximate capacity, generalized hash-and-forward (GHF), generalized degrees
of freedom, Han-Kobayashi strategy, interference channel, relay channel.

##  I Introduction

Interference is a key limiting factor in modern communication systems. In a
wireless cellular network, the performance of cell-edge users is severely
limited by intercell interference. This paper considers the use of relays in
cellular networks. The uses of relays to combat channel shadowing and to
extend coverage for wireless systems have been widely studied in the
literature. The main goal of this paper is to demonstrate the benefit of
relaying for interference mitigation in the interference-limited regime.

Consider a two-cell wireless network with two base-stations each serving their
respective receivers while interfering with each other, as shown in Fig. 1.
The deployment of a cell-edge relay, which observes a linear combination of
the two transmit signals from the base-stations and is capable of
independently communicating with the receivers over a pair of relay links, can
significantly help the receivers mitigate intercell interference. This model
is often referred to as an in-band-reception and out-of-band-transmission
relay-interference channel, as the relay-to-receiver transmission can be
thought of as taking place on a different frequency band.

A particular feature of the channel model considered in this paper is that the
relay-to-receivers link is modeled as a Gaussian broadcast channel. This is
motivated by the fact that the relay’s transmission to the remote receivers
often takes place in a wireless medium. Consequently, the same relay message
can be heard by both receivers and can potentially help both receivers at the
same time. Further, it is convenient (and without loss of generality as shown
later for the achievability scheme and the converse proved in this paper) to
model the relay-to-receiver links as digital links with capacities
$\mathsf{C}_{1}$ and $\mathsf{C}_{2}$ respectively, but where one relay
message is required to be a degraded version of the other relay message, as in
a Gaussian broadcast channel. The goal of this paper is to devise an
incremental relaying strategy and to quantify its benefit for this particular
relay-interference channel.

###  I-A Related Work

The classic two-user interference channel consists of two transmitter-receiver
pairs communicating in the presence of interference from each other. Although
the capacity region of the two-user Gaussian interference channel is still not
known exactly, it can be approximated to within one bit [1] using a Han-
Kobayashi power splitting strategy [2].

The use of cooperative communication for interference mitigation has received
much attention recently. For example, [3, 4, 5] studied the Gaussian
Z-interference channel with a unidirectional receiver cooperation link, and
[6, 7, 8, 9] studied the Gaussian interference channel with bi-directional
transmitter/receiver cooperation links. In addition, the Gaussian interference
channel with an additional relay node has also been studied extensively in the
literature. Depending on the types of the links between the relay and the
transmitters/receivers, the relay-interference channel can be categorized as
having in-band transmission/reception [10, 11, 12, 13, 14, 15, 16, 17], out-
of-band transmission/reception [18, 19, 20], out-of-band transmission and in-
band reception [21, 22, 23, 24], or in-band transmission and out-of-band
reception [25], the last of which is directly related to the channel model in
this paper. In the following, we review different transmission schemes and
relaying strategies that have emerged for each of these cases.

For interference channels equipped with an in-band transmission and reception
relay, the relay interacts with both transmitters and receivers in the same
frequency band. Relaying strategies that have been investigated in the
literature include decode-and-forward, compress-and-forward, and amplify-and-
forward. For example, [12, 13] show that decoding-and-forwarding either the
intended signal or the interfering signal to a receiver can both be
beneficial. The former is termed as signal relaying, the latter interference
forwarding. Decode-and-forward and half-duplex amplify-and-forward strategies
are also studied in [14, 16]. When combining decode-and-forward relaying
strategy and the Han-Kobayashi rate splitting input scheme, [17] gives an
achievable rate region that has a shape similar to the Chong-Motani-Garg (CMG)
region for the interference channel [26]. The exact capacity for this type of
relay-interference channel is in general open, but there is a special potent-
relay case [11] for which the sum capacity is known in some specific regimes.

The difficulty in establishing the capacity of the interference channel with
in-band transmission/reception relay is in part due to the fact that the
relay’s received and transmit signals intertwine with that of the underlying
interference channel. To simplify the matter, the interference channel with an
out-of-band transmission/reception relay has been studied in [18, 20, 19]. In
this channel model, the relay essentially operates on a separate set of
parallel channels. Based on signal relaying and interference forwarding
strategies, [18] identifies the condition under which the capacity region can
be achieved with separable or nonseparable coding between the out-of-band
relay and the underlying interference channel. Further, [19] studies this
channel model in a symmetric setting and characterizes the sum capacity to
within $1.15$ bits. The transmission scheme of [19] involves further splitting
of the common messages in the Han-Kobayashi scheme and a relay strategy that
combines nested lattice coding and Gaussian codes. It is shown that in the
strong interference regime, the use of structured codes is optimal.

\begin{overpic}[width=231.26378pt]{./figures/intercell_new}
\put(30.0,23.0){\small$h_{11}$} \put(40.0,22.0){\small$h_{21}$}
\put(53.0,21.0){\small$h_{12}$} \put(66.0,19.0){\small$h_{22}$}
\put(35.0,30.0){\small$g_{1}$} \put(58.0,29.5){\small$g_{2}$}
\put(40.0,11.0){\small$\mathsf{C}_{1}$}
\put(55.0,11.0){\small$\mathsf{C}_{2}$} \put(23.0,37.0){\small$P_{1}$}
\put(72.0,37.0){\small$P_{2}$} \end{overpic} Figure 1: A two-cell network with
an in-band reception and out-of-band-broadcasting relay for interference
mitigation

Another variation of the relay-interference channel involves an out-of-band
reception and in-band transmission relay. This channel is studied in [21], in
which the transmitter further splits the transmit signal according to the Han-
Kobayashi scheme; the relay decodes only part of the message depending the
capacity of the transmitter-relay links; the rest of the codewords are
transmitted directly from the sources to the destinations without the help of
the relay. With this partial decode-and-forward relaying scheme, the sum
capacity is found under a so-called strong relay-interference condition.

The interference channel with an in-band reception/out-of-band transmission
relay has been briefly discussed in [25], and studied in [22, 23] for a case
where the relay-destination links are shared between the two receivers.
Conventional decode-and-forward and compress-and-forward relay strategies are
not well matched for helping both receivers simultaneously with a common
relayed message. Thus, [22, 23] consider a generalized hash-and-forward (GHF)
strategy, which generalizes the conventional compress-and-forward scheme, and
is shown to achieve the capacity region of this channel model to within a
constant number of bits in the regime where the shared relay-destination link
rate is sufficiently small. The channel model under consideration in this
paper further extends the shared relay-destinations link to be a degraded
broadcast channel. We focus on a different weak-relay regime. The main
objective is similar: to efficiently use the relay bits to simultaneously
benefit both users and to achieve capacity to within a constant gap.

Finally, the GHF relay strategy used in this paper is essentially the same as
the noisy network coding [27, 28, 29] and the quantize-map-and-forward relay
strategies [30]. The result of this paper can be thought of as an effort in
generalizing these relay strategies to a particular case of the multiple
unicast setting, for which constant-gap result continues to hold for certain
channel-parameter regimes. Related works for the multiple unicast problem
include [31, 32, 33].

###  I-B Main Contributions

This paper considers a relay-interference channel with in-band reception and
out-of-band degraded broadcasting links from the relay to the receivers. The
key features of the transmission strategy and the main results of the paper
are as follows.

####  I-B1 Incremental Relaying

This paper uses a GHF relaying strategy to take advantage of the in-band
reception link and the out-of-band broadcasting link from the relay to the
receivers. In GHF, the relay quantizes its observation, which is a linear
combination of the transmitted signals, using a fixed quantizer, then bins and
forwards the quantized observation to the receivers. This strategy of fixing
the quantization level is near optimal when a certain weak-relay condition is
satisfied, and is ideally matched to the degraded broadcasting relay-to-
receiver links with capacities $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$, because
it allows an incremental binning strategy at the relay. Assuming that
$\mathsf{C}_{1}\leq\mathsf{C}_{2}$, the relay may first bin its quantized
observation into $2^{n\mathsf{C}_{1}}$ bins and send the bin index to both
receivers, then further divide each bin into
$2^{n(\mathsf{C}_{2}-\mathsf{C}_{1})}$ sub-bins and sends the extra bin index
to receiver $2$ only. Thus, the relay message to the first receiver is a
degraded version of the message to the second receiver.

####  I-B2 Oblivious Power Splitting

The transmission scheme used in this paper consists of a Han-Kobayashi power
splitting strategy [2] at the transmitter. The common-private power splitting
ratio in such a strategy is crucial. In a study of the interference channel
with conferencing links [6], Wang and Tse used the power splitting strategy of
Etkin, Tse and Wang [1] where the private power is set at the noise level at
the receivers. This is sensible for the conferencing-receiver model considered
in [6], but not necessarily so for the interference channel with an
independent relay, unless again a certain weak-relay condition is satisfied.
This strategy of fixing the power splitting at the transmitter to be
independent of the relay is termed oblivious power splitting in [23].
Oblivious power splitting is used in this paper as well.

####  I-B3 Constant Gap to Capacity in the weak-relay Regime

The main result of this paper is that when the relay links are not unboundedly
stronger than the interfering links, i.e.,

$\max\left\\{\frac{|g_{1}|^{2}}{|h_{12}|^{2}},\frac{|g_{2}|^{2}}{|h_{21}|^{2}}\right\\}=\rho<\infty,$
(1)

for some fixed $\rho$, the capacity of the relay-interference channel with a
broadcast link can be achieved to within a constant gap, where the gap is a
function of $\rho$ but otherwise independent of channel parameters. This
operating regime is called the weak-relay regime in this paper.

The main result of this paper is motivated by the results in [22] and [23],
which studies a two-user interference channel augmented with a shared digital
relay link to the receivers of rate $R_{0}$, and obtains a constant-gap-to-
capacity result under a certain small-$R_{0}$ condition using GHF and
oblivious power splitting. The relay strategy studied in this paper goes one
step further in that the relay-to-receivers link is modeled as a degraded
broadcast channel. Moreover, the weak-relay regime studied in this paper is a
counterpart of the small-$R_{0}$ regime studied in [23], as can be visualized
in the practical setup of Fig. 1. When the mobiles are close to their
respective cell centers, the relay link capacities $\mathsf{C}_{1}$ and
$\mathsf{C}_{2}$ are small, thereby satisfying the small-$R_{0}$ condition of
[23]. In the more practically important regime where the mobile terminals are
close to the cell edge, the channel falls into the weak-relay regime of this
paper. An interesting feature of the result in this paper is that the gap to
capacity is a function of $\rho$, the relative channel strength between the
interfering channel and the channel to the relay; the gap becomes smaller as
$\rho\rightarrow 1$. In the limiting case with $\rho=1$, corresponding to the
situation where the mobiles are at the cell edge, the capacity region can be
achieved to within $\frac{1}{2}\log\frac{5+\sqrt{33}}{2}=1.2128$ bits.

A technical contribution of this paper is a particular set of capacity region
outer bounds which are established by giving different combinations of side
information (genies) to the receivers and by applying the known outer-bound
results of the Gaussian interference channel [1] and the single-input
multiple-output (SIMO) Gaussian interference channel [34]. It is shown that
there are two constraints for the individual rates $R_{1}$ and $R_{2}$, twelve
constraints for the sum rate $R_{1}+R_{2}$, six constraints for
$2R_{1}+R_{2}$, and six constraints for $R_{1}+2R_{2}$. Furthermore, the outer
bounds established in this paper hold for all channel parameters. This set of
outer bounds is tight to within a constant gap in the weak-relay regime.

To obtain insights from the performance gain brought by the relay, this paper
further investigates the improvement in the generalized degrees of freedom
(GDoF) per user for the relay-interference channel due to a broadcasting link.
In the symmetric setting, it is shown that a common broadcast link can improve
the sum capacity by two bits per each relay bit in the very weak, moderately
weak, and very strong interference regimes, but by one bit per each relay bit
in other regimes. This asymptotic behavior can be interpreted by noting that
the relay link essentially behaves like a deterministic channel in the high
signal-to-noise-ratio (SNR) regime. Further, in the symmetric setting, the
sum-capacity gain due to the relay can be thought of as solely coming from the
rate improvement of the common messages, or alternatively in a very weak
interference regime as solely coming from the rate improvement of the private
messages.

In asymmetric settings, the improvement in the sum capacity by the relay can
be interpreted in different ways. To illustrate this point, this paper
investigates a special case of the channel model, where the relay link is
available to only one but not both destinations. In this case, the relay may
forward information about both the intended signal and the interference, and
the capacity can benefit from both signal-relaying and interference-
forwarding. This paper shows that a constant-gap-to-capacity result can be
derived for this setting under a more relaxed weak-relay condition that
requires only $|g_{2}|\leq\sqrt{\rho}|h_{21}|$ (and not
$|g_{1}|\leq\sqrt{\rho}|h_{12}|$). Moreover, this paper shows that in term of
GDoF, when the relay link is above a certain threshold, the sum-capacity gain
is equivalent to that of that of a single relay link from user $1$. When the
relay link is below the threshold, the sum-capacity gain is equivalent to that
of a single relay link from user $2$.

Finally, the results of this paper show that GHF is sufficient for achieving
the approximated capacity region of an in-band reception and out-of-band
transmission Gaussian relay-interference channel in the weak-relay regime.
Thus, more recently proposed relay techniques based on compute-and-forward
[35] or lattice coding [36] is not necessary in this regime as far as constant
gap to capacity is concerned . Outside of the weak-relay regime, the optimal
relay strategies remain an open problem; lattice coding strategies may be
helpful.

###  I-C Organization of This Paper

The rest of the paper is organized as follows. Section II introduces the
Gaussian relay-interference channel model, derives capacity region outer
bounds that hold for all channel parameters and an achievable rate region, and
presents the main constant-gap theorem and the GDoF analysis. Section III
deals with the relay-interference channel with a single relay link, derives
the corresponding constant-gap result, and gives a quantitative analysis on
the relation between signal relaying and interference forwarding. Section IV
concludes the paper.

##  II Gaussian Relay-Interference Channel: General Case

Figure 2: Gaussian relay-interference channel with two independent digital
relay links

###  II-A Channel Model and Definitions

A Gaussian relay-interference channel consists of two transmitter-receiver
pairs and an independent relay. Each transmitter communicates with the
intended receiver while causing interference to the other transmitter-receiver
pair. The relay receives a linear combination of the two transmit signals and
helps the transmitter-receiver pairs by forwarding a message to receiver $1$
and another message to receiver $2$ through rate-limited digital links with
capacities $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$ respectively. We start by
treating a channel model with independent relay links, and later show that
requiring one relay message to be a degraded version of the other is without
loss of approximate optimality. As shown in Fig. 2, $X_{1},X_{2}$ and
$Y_{1},Y_{2}$ are real-valued input and output signals, respectively, and
$Y_{R}$ is the observation of the relay. The receiver noises are assumed to be
independent and identically distributed (i.i.d.) Gaussian random variables
with variance one, i.e., $Z_{i}\sim\mathcal{N}(0,1),i=1,2$ and $R$. The input-
output relationship can be described by

$\displaystyle Y_{1}$ $\displaystyle=h_{11}X_{1}+h_{21}X_{2}+Z_{1},$ (2)
$\displaystyle Y_{2}$ $\displaystyle=h_{22}X_{2}+h_{12}X_{1}+Z_{2},$ (3)
$\displaystyle Y_{R}$ $\displaystyle=g_{1}X_{1}+g_{2}X_{2}+Z_{R},$ (4)

where $h_{ij}$ is the channel gain from transmitter $i$ to receiver $j$, and
$g_{j}$ is the channel gain from transmitter $j$ to the relay, all real
valued. The powers of the input signals are normalized to one, i.e.,
$\mathbb{E}[|X_{i}|^{2}]\leq 1,i=1,2$.

Define the signal-to-noise ratios and interference-to-noise ratios as follows:

$\displaystyle\mathsf{SNR}_{i}=|h_{ii}|^{2},\;$
$\displaystyle\quad\mathsf{SNR}_{ri}=|g_{i}|^{2},\;\;i=1,2$
$\displaystyle\mathsf{INR}_{1}=|h_{12}|^{2},$
$\displaystyle\quad\mathsf{INR}_{2}\;\;=|h_{21}|^{2}.$

Define functions $\alpha(\cdot)$ and $\beta(\cdot)$ as

$\alpha(x)=\frac{1}{2}\log(2x+2+\rho),\quad\beta(x)=\frac{1}{2}+\frac{1}{2}\log\left(1+\frac{1+\rho}{x}\right),$
(5)

where $\log(\cdot)$ is base $2$ and $\rho$ is defined as

$\rho\triangleq\max\left\\{\frac{|g_{1}|^{2}}{|h_{12}|^{2}},\frac{|g_{2}|^{2}}{|h_{21}|^{2}}\right\\}.$
(6)

This paper considers a weak-relay regime where $\rho$ is a finite constant.

###  II-B Outer Bounds and Achievable Rate Region

We first present outer bounds and achievability results that are applicable to
the relay-interference channel model with two independent digital relays as
shown in Fig. 2.

######  Theorem 1 (Capacity Region Outer Bounds).

The capacity region of the Gaussian relay-interference channel as depicted in
Fig. 2 is contained in the outer bound $\overline{\mathcal{C}}$ given by the
set of $(R_{1},R_{2})$ for which

$\displaystyle R_{1}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1})$ (7)
$\displaystyle+\min\left\\{\mathsf{C}_{1},\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{r1}}{1+\mathsf{SNR}_{1}}\right)\right\\}$
$\displaystyle R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{2})$ (8)
$\displaystyle+\min\left\\{\mathsf{C}_{2},\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{r2}}{1+\mathsf{SNR}_{2}}\right)\right\\}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{2}+\mathsf{INR}_{1})$ (9)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)+\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})$ (10)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)+\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{INR}_{2}+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{INR}_{1}+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)+\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}}\right)$
(12)
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})$
$\displaystyle\qquad\quad+\mathsf{SNR}_{r2}+\mathsf{INR}_{1}+\mathsf{SNR}_{r1})+\mathsf{C}_{1}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})$ (13)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right)+\mathsf{C}_{1}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}}+\mathsf{INR}_{2}\right)$
(14)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)+\mathsf{C}_{1}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}}\right)$
(15)
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}$
$\displaystyle\qquad\quad+\mathsf{INR}_{2}+\mathsf{SNR}_{r2})+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{2}+\mathsf{INR}_{1})$ (16)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}}+\mathsf{INR}_{1}\right)$
(17)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}}\right)$
(18)
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}$
$\displaystyle\qquad\quad+\mathsf{INR}_{1}+\mathsf{SNR}_{r1})$ $\displaystyle
R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}}\right)$
(19)
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}$
$\displaystyle\qquad\quad+\mathsf{INR}_{2}+\mathsf{SNR}_{r2})$ $\displaystyle
R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}}\right.$
(20)
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2}\right)$
(21)
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{INR}_{1}+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)+2\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}}\right)$
(22)
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})$ (23)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)+\mathsf{C}_{1}$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)$
(24)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}}+\mathsf{INR}_{1}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{2}+\mathsf{SNR}_{2}\right)+\mathsf{C}_{2}$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})$ (25)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)+2\mathsf{C}_{1}$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})$ (26)
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{INR}_{1}+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)$
$\displaystyle+\mathsf{C}_{1}+\mathsf{C}_{2},$

and $R_{1}+2R_{2}$ bounded by (21)-(26) with indices $1$ and $2$ switched,
where $\phi_{1}^{2}$ and $\phi_{2}^{2}$ are defined as

$\phi_{1}^{2}=\left|\frac{g_{1}h_{21}}{g_{2}h_{11}}-1\right|^{2},\quad\phi_{2}^{2}=\left|\frac{g_{2}h_{12}}{g_{1}h_{22}}-1\right|^{2}.$
(27)

###### Proof:

The above outer bounds can be proved in a genie-aided approach. See Appendix
-A for details. ∎

######  Theorem 2 (Achievable Rate Region).

Let $\mathcal{P}$ denote the set of probability distributions $P(\cdot)$ that
factor as

$\displaystyle
P(q,w_{1},w_{2},x_{1},x_{2},y_{1},y_{2},y_{R},\hat{y}_{R1},\hat{y}_{R2})$ (28)
$\displaystyle=p(q)p(x_{1},w_{1}|q)p(x_{2},w_{2}|q)p(y_{1},y_{2},y_{R}|x_{1},x_{2},q)$
$\displaystyle\qquad p(\hat{y}_{R1},\hat{y}_{R2}|y_{R},q).$

For a fixed distribution $P\in\mathcal{P}$, let $\mathcal{R}(P)$ be the set of
all rate pairs $(R_{1},R_{2})$ satisfying

$\displaystyle 0\leq R_{1}$ $\displaystyle\leq$ $\displaystyle
d_{1}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{d}_{1}\right\\},$ (29)
$\displaystyle 0\leq R_{2}$ $\displaystyle\leq$ $\displaystyle
d_{2}+\min\left\\{(\mathsf{C}_{2}-\xi_{2})^{+},\Delta{d}_{2}\right\\},$ (30)
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+g_{2}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{a}_{1}\right\\}$
(31)
$\displaystyle+\min\left\\{(\mathsf{C}_{2}-\xi_{2})^{+},\Delta{g}_{2}\right\\},$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{2}+g_{1}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{g}_{1}\right\\}$
(32)
$\displaystyle+\min\left\\{(\mathsf{C}_{2}-\xi_{2})^{+},\Delta{a}_{2}\right\\},$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
e_{1}+e_{2}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{e}_{1}\right\\}$
(33)
$\displaystyle+\min\left\\{(\mathsf{C}_{2}-\xi_{2})^{+},\Delta{e}_{2}\right\\},$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+g_{1}+e_{2}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{a}_{1}\right\\}$
(34)
$\displaystyle+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{g}_{1}\right\\}$
$\displaystyle+\min\left\\{(\mathsf{C}_{2}-\xi_{2})^{+},\Delta{e}_{2}\right\\},$
$\displaystyle R_{1}+2R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{2}+g_{2}+e_{1}+\min\left\\{(\mathsf{C}_{2}-\xi_{2})^{+},\Delta{a}_{2}\right\\}$
(35)
$\displaystyle+\min\left\\{(\mathsf{C}_{2}-\xi_{2})^{+},\Delta{g}_{2}\right\\}$
$\displaystyle+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{e}_{1}\right\\},$

where

$\displaystyle a_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1};Y_{1}|W_{1},W_{2},Q),$ (36) $\displaystyle d_{1}$ $\displaystyle=$
$\displaystyle I(X_{1};Y_{1}|W_{2},Q),$ (37) $\displaystyle e_{1}$
$\displaystyle=$ $\displaystyle I(X_{1},W_{2};Y_{1}|W_{1},Q),$ (38)
$\displaystyle g_{1}$ $\displaystyle=$ $\displaystyle I(X_{1},W_{2};Y_{1}|Q),$
(39) $\displaystyle\Delta{a}_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1};\hat{Y}_{R1}|Y_{1},W_{1},W_{2},Q),$ (40) $\displaystyle\Delta{d}_{1}$
$\displaystyle=$ $\displaystyle I(X_{1};\hat{Y}_{R1}|Y_{1},W_{2},Q),$ (41)
$\displaystyle\Delta{e}_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1},W_{2};\hat{Y}_{R1}|Y_{1},W_{1},Q),$ (42) $\displaystyle\Delta{g}_{1}$
$\displaystyle=$ $\displaystyle I(X_{1},W_{2};\hat{Y}_{R1}|Y_{1},Q),$ (43)
$\displaystyle\xi_{1}$ $\displaystyle=$ $\displaystyle
I(Y_{R};\hat{Y}_{R1}|Y_{1},X_{1},W_{2},Q),$ (44)

and
$a_{2},\Delta{a}_{2},d_{2},\Delta{d}_{2},e_{2},\Delta{e}_{2},g_{2},\Delta{g}_{2}$,
and $\xi_{2}$ are defined by (36)-(44) with indices $1$ and $2$ switched. Then

$\mathcal{R}=\bigcup_{P\in\mathcal{P}}\mathcal{R}(P)$ (45)

is an achievable rate region for the Gaussian relay-interference channel as
shown in Fig. 2.

###### Proof.

The achievable scheme consists of a Han-Kobayashi strategy at the transmitters
and a generalized hash-and-forward strategy at the relay. They are the same
strategies as adopted in [23] except that unlike the GHF relaying scheme in
[23, Theorem 2], where the relay quantizes the received signal and broadcasts
its bin index to both receivers through a shared digital link, the relay here
quantizes the received signal with two different quantization resolutions,
then sends the bin indices of the quantized signals to the receivers through
separated digital links of rates $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$. The
following is a sketch of the encoding/decoding process.

Encoding: Each transmit signal is comprised of a common message of rate
$T_{i}$ and a private message of rate $S_{i}$. The common message codewords
$W_{i}^{n}(j)$, $j=1,2,\cdots,2^{nT_{i}}$ of length $n$ are generated
according to the probability distribution $\Pi_{i=1}^{n}p(w_{i}|q)$, where
$q\sim p(q)$ serves as the time-sharing random variable. Based on the common
message codewords, user $i$ generates codewords
$X_{i}^{n}(j,k),k=1,2,\cdots,2^{nS_{i}}$ of length $n$ following the
conditional distribution $\Pi_{i=1}^{n}p(x_{i}|w_{i},q)$. Each input message
$\theta_{i}\in[1,2,\cdots,2^{S_{i}+T_{i}}],i=1,2$ is mapped to a message pair
$(s_{i},t_{i})\in[1,\cdots,2^{S_{i}}]\times[1,\cdots,2^{T_{i}}]$, then sent to
the destinations as $X_{i}^{n}(s_{i},t_{i})$. At the relay, the quantization
codebook is generated according to the probability distribution
$p(\hat{y}_{R1},\hat{y}_{R2}|y_{R},q)$. After receiving $Y_{R}^{n}$, the relay
quantizes $Y_{R}^{n}$ into $\hat{Y}_{R1}^{n}$ and $\hat{Y}_{R2}^{n}$, then
bins $\hat{Y}_{R1}^{n}$ to $2^{nC_{1}}$ bins, and bins $\hat{Y}_{R1}^{n}$ to
$2^{nC_{1}}$ bins, and sends the bin indices to the receivers through the
digital links.

Decoding: The decoding process follows the Han-Kobayashi framework:
$X_{1}^{n}$ and $W_{2}^{n}$ are decoded by receiver $1$ with the help of the
index of the relayed message $\hat{Y}_{R1}^{n}$; $X_{2}^{n}$ and $W_{1}^{n}$
are decoded by receiver $2$ with the help of the index of the relayed message
$\hat{Y}_{R2}^{n}$. To decode, receiver $1$ first constructs a list of
candidates for the relayed message $\hat{Y}_{R1}^{n}$, then jointly decodes
$X_{1}^{n}$, $W_{2}^{n}$ and $\hat{Y}_{R1}^{n}$ using typicality decoding.
Similarly, receiver $2$ jointly decodes $X_{2}^{n}$, $W_{1}^{n}$ and
$\hat{Y}_{R2}^{n}$. Following the error probability analysis in [23, Theorem
2], the rate tuple $(S_{1},T_{1},S_{2},T_{2})$ satisfying the following
constraints is achievable:

Constraints at receiver 1:

$\displaystyle S_{1}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{1};Y_{1}|W_{1},W_{2},Q)+(\mathsf{C}_{1}-\xi_{1})^{+},$
(46) $\displaystyle\qquad\;I(X_{1};Y_{1},\hat{Y}_{R1}|W_{1},W_{2},Q)\\}$
$\displaystyle S_{1}+T_{1}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{1};Y_{1}|W_{2},Q)+(\mathsf{C}_{1}-\xi_{1})^{+},$
(47) $\displaystyle\qquad\;I(X_{1};Y_{1},\hat{Y}_{R1}|W_{2},Q)\\}$
$\displaystyle S_{1}+T_{2}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{1},W_{2};Y_{1}|W_{1},Q)+(\mathsf{C}_{1}-\xi_{1})^{+},$
(48) $\displaystyle\qquad\;I(X_{1},W_{2};Y_{1},\hat{Y}_{R1}|W_{1},Q)\\}$
$\displaystyle S_{1}+T_{1}+T_{2}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{1},W_{2};Y_{1}|Q)+(\mathsf{C}_{1}-\xi_{1})^{+},$
(49) $\displaystyle\qquad\;I(X_{1},W_{2};Y_{1},\hat{Y}_{R1}|Q)\\}$

Constraints at receiver 2:

$\displaystyle S_{2}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{2};Y_{2}|W_{1},W_{2},Q)+(\mathsf{C}_{2}-\xi_{2})^{+},$
(50) $\displaystyle\qquad\;I(X_{2};Y_{2},\hat{Y}_{R2}|W_{1},W_{2},Q)\\}$
$\displaystyle S_{2}+T_{2}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{2};Y_{2}|W_{1},Q)+(\mathsf{C}_{2}-\xi_{2})^{+},$
(51) $\displaystyle\qquad\;I(X_{2};Y_{2},\hat{Y}_{R2}|W_{1},Q)\\}$
$\displaystyle S_{2}+T_{1}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{2},W_{1};Y_{2}|W_{2},Q)+(\mathsf{C}_{2}-\xi_{2})^{+},$
(52) $\displaystyle\qquad\;I(X_{2},W_{1};Y_{2},\hat{Y}_{R2}|W_{2},Q)\\}$
$\displaystyle S_{2}+T_{2}+T_{1}$ $\displaystyle\leq$
$\displaystyle\min\\{I(X_{2},W_{1};Y_{2}|Q)+(\mathsf{C}_{2}-\xi_{2})^{+},$
(53) $\displaystyle\qquad\;I(X_{2},W_{1};Y_{2},\hat{Y}_{R2}|Q)\\}$

The achievable rate region consists of all rate pairs $(R_{1},R_{2})$ such
that $R_{1}=S_{1}+T_{1}$ and $R_{2}=S_{2}+T_{2}$. Applying the Fourier-Motzkin
elimination procedure [37] gives the achievable rate region (29)-(35). ∎

We remark here that although both Theorem 1 and Theorem 2 are stated for the
digital noise-free relay-destination links, it can be easily verified that
both results continue to hold when the digital links are replaced by analog
additive Gaussian noise channels. The fact that the achievable rate region for
the analog channel is at least as large as the rate region for the digital
channel is obvious since one can always digitize the analog link. The fact
that the outer bound continues to hold can be verified by going through the
proof of that converse in Appendix -A. The outer bounds in the converse
involve terms like $I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})$, which is in turn upper
bounded by $I(X_{1}^{n};Y_{1}^{n})+n\mathsf{C}_{1}$. It is easy to show that
when the digital link $\mathsf{C}_{1}$ is replaced by an analog link with
input $X_{a1}$ and output $Y_{a1}$, the mutual information term is upper
bounded by $I(X_{1}^{n};Y_{1}^{n})+I(X_{a1}^{n};Y_{a1}^{n})$. As a result, all
the outer bounds in Theorem 1 continue to hold in the case of the analog relay
link with $\mathsf{C}_{1}$ replaced by $I(X_{a1};Y_{a1})$ and $\mathsf{C}_{2}$
replaced by $I(X_{a2};Y_{a2})$.

###  II-C Constant Gap in the Weak-Relay Regime

We now specialize to the Gaussian case, and show that under the weak-relay
condition (1), the achievable rate region and the outer bounds of the Gaussian
relay-interference channel with independent relay links can be made to be
within a constant gap to each other. The relaying strategy that achieves this
capacity to within a constant gap turns out to be naturally suited for the
Gaussian relay-interference channel with a degraded broadcasting relay, thus
establishing the constant-gap result for the broadcasting-relay case as well.

Assuming Gaussian codebooks and a Gaussian quantization scheme, the key design
parameters are the choice of common-private power splitting ratio at the
transmitters and the quantization level at the relay. Our choice of design
parameters is inspired by that of Wang and Tse [6], where the capacity region
of a Gaussian interference channel with rate-limited receiver cooperation is
characterized to within a constant gap. Two key observations are made in [6].
First, the Etkin-Tse-Wang strategy [1] of setting the private power to be at
the noise level at the opposite receiver is used. Second, the relay quantizes
its observation at the private signal level in order to preserve all the
information of interest to the destinations. At the destinations, a joint
decoding (see [38, 39, 22, 30]) is performed to recover the source messages.

Consider now the optimal power splitting in a Gaussian relay-interference
channel with independent relay links. The Etkin-Tse-Wang strategy, i.e.,
setting private powers $P_{ip}$ as

$P_{1p}=\min\\{1,h_{12}^{-2}\\},\quad P_{2p}=\min\\{1,h_{21}^{-2}\\}.$ (54)

is near optimal for the Gaussian interference channel with conferencing
receivers, but is not necessarily so for relay-interference channel shown in
Fig. 2 in its most general form. Consider an extreme scenario of
$\mathsf{C}_{1},\mathsf{C}_{2}\rightarrow\infty$. In this case, the relay
fully cooperates with both receivers, so the relay-interference channel
becomes a single-input multiple-output (SIMO) interference channel with two
antennas at the receivers. Thus, the private powers at the transmitters must
be set at the effective noise level for the two-antenna output in order to
achieve capacity to within constant bits [34] [40], i.e.,

$P_{1p}=\min\\{1,(g_{1}^{2}+h_{12}^{2})^{-1}\\},\quad
P_{2p}=\min\\{1,(g_{2}^{2}+h_{21}^{2})^{-1}\\}.$ (55)

When $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$ are finite, the optimal power
splitting strategy is expected to be a function of not only $h_{12}$ and
$h_{21}$ but also $g_{1}$, $g_{2}$, $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$,
lying somewhere between (54) and (55).

This complication can be avoided, however, if we focus on the weak-relay
regime (1), namely $|g_{1}|\leq\sqrt{\rho}|h_{12}|$ and
$|g_{2}|\leq\sqrt{\rho}|h_{21}|$ for some finite constant $\rho$. In this
case, the power splittings (54) and (55) differ by at most a constant factor.
The main result of this section shows that in this weak-relay regime, the
Etkin-Tse-Wang’s original power splitting (54) is sufficient for achieving the
capacity of the Gaussian relay-interference channel to within a constant gap
(which is a function of $\rho$).

Consider next the optimization of the quantization level. Applying the insight
of [6] to the Gaussian relay-interference channel with independent relay links
shown in Fig. 2, the quantized messages for two receivers can be expressed as

$\displaystyle\hat{Y}_{R1}=g_{1}U_{1}+g_{1}W_{1}+g_{2}W_{2}+\overbrace{g_{2}U_{2}+Z_{R}}^{\text{of
no interest at $Y_{1}$}}+\eta_{1}$ (56)
$\displaystyle\hat{Y}_{R2}=g_{1}W_{1}+g_{2}U_{2}+g_{2}W_{2}+\underbrace{g_{1}U_{1}+Z_{R}}_{\text{of
no interest at $Y_{2}$}}+\eta_{2}$ (57)

where $W_{i}$ and $U_{i}$ are common message and private message respectively,
and $\eta_{i}\sim\mathcal{N}(0,\mathsf{q}_{i})$ is the quantization noise,
$i=1,2$. Therefore, a reasonable choice of the quantization levels for
receiver $1$ and receiver $2$ is

$\mathsf{q}_{1}=1+g_{2}^{2}P_{2p},\quad\mathsf{q}_{2}=1+g_{1}^{2}P_{1p}.$ (58)

Now observe that in the weak-relay regime, i.e.,
$|g_{1}|\leq\sqrt{\rho}|h_{12}|,|g_{2}|\leq\sqrt{\rho}|h_{21}|$, the above
quantization levels (with Etkin-Tse-Wang power splitting) are between $1$ and
the constant $\rho+1$. Thus, we can choose the quantization levels to be a
constant and optimize it between $1$ and $\rho+1$.

######  Theorem 3 (Constant Gap in the Weak-Relay Regime).

For the Gaussian relay-interference channel with independent relay links as
depicted in Fig. 2, in the weak-relay regime, using the generalized hash-and-
forward relaying scheme with quantization levels
$\mathsf{q}_{1}=\mathsf{q}_{2}=\frac{\sqrt{\rho^{2}+16\rho+16}-\rho}{4}$,
where $\rho$ is defined in (6), and using the Han-Kobayashi scheme with Etkin-
Tse-Wang power splitting strategy, $X_{i}=U_{i}+W_{i},i=1,2$, where $U_{i}$
and $W_{i}$ are both Gaussian distributed with the powers of $U_{1}$ and
$U_{2}$ set according to $P_{1p}=\min\\{1,h_{12}^{-2}\\}$ and
$P_{2p}=\min\\{1,h_{21}^{-2}\\}$, respectively, the achievable rate region
given in Theorem 2 is within

$\delta=\frac{1}{2}\log\left(2+\frac{\rho+\sqrt{\rho^{2}+16\rho+16}}{2}\right)$
(59)

bits of the capacity region outer bound in Theorem 1.

###### Proof:

The main step is to show that using superposition coding
$X_{i}=U_{i}+W_{i},i=1,2$, where $U_{i}\sim\mathcal{N}(0,P_{ip})$ and
$W_{i}\sim\mathcal{N}(0,P_{ic})$ with $P_{ip}+P_{ic}=1$,
$P_{1p}=\min\\{1,h_{12}^{-2}\\}$, and $P_{2p}=\min\\{1,h_{21}^{-2}\\}$, each
of the achievable rate constraints in (29)-(35) is within a finite gap to the
corresponding upper bound in (7)-(26). Specifically, it is shown in Appendix
-C that

(i) Individual rate (29) is within

$\delta_{R_{1}}=\max\left\\{\alpha(\mathsf{q}_{1}),\beta(\mathsf{q}_{1})\right\\}$
(60)

bits of the upper bound (7), where $\alpha(\cdot)$ and $\beta(\cdot)$ are as
defined in (5);

(ii) Individual rate (30) is within

$\delta_{R_{2}}=\max\left\\{\alpha(\mathsf{q}_{2}),\beta(\mathsf{q}_{2})\right\\}$
(61)

bits of the upper bound (8);

(iii) Sum rates (31), (32), and (33) are within

$\displaystyle\delta_{R_{1}+R_{2}}$ $\displaystyle=$
$\displaystyle\max\left\\{\alpha(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2}),\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{2}),\right.$
(62)
$\displaystyle\quad\left.\beta(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2}),\beta(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})\right\\}$

bits of the upper bounds (9)-(20);

(iv) $2R_{1}+R_{2}$ rate (34) is within

$\displaystyle\delta_{2R_{1}+R_{2}}$ $\displaystyle=$
$\displaystyle\max\left\\{2\alpha(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2}),2\beta(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2}),\right.$
(63)
$\displaystyle\qquad\;\;\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2}),$
$\displaystyle\qquad\;\;2\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{2}),2\beta(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})$
$\displaystyle\qquad\;\;\left.\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})\right\\}$

bits of the upper bounds (21)-(26);

(v) $R_{1}+2R_{2}$ rate (35) is within

$\displaystyle\delta_{R_{1}+2R_{2}}$ $\displaystyle=$
$\displaystyle\max\left\\{\alpha(\mathsf{q}_{1})+2\alpha(\mathsf{q}_{2}),\alpha(\mathsf{q}_{1})+2\beta(\mathsf{q}_{2}),\right.$
(64)
$\displaystyle\qquad\;\;\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})+\alpha(\mathsf{q}_{2}),$
$\displaystyle\qquad\;\;\beta(\mathsf{q}_{1})+2\alpha(\mathsf{q}_{2}),\beta(\mathsf{q}_{1})+2\beta(\mathsf{q}_{2}),$
$\displaystyle\qquad\;\;\left.\beta(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})+\alpha(\mathsf{q}_{2})\right\\}$

bits of the upper bounds not shown explicitly in Theorem 1 but can be obtained
by switching the indices $1$ and $2$ of (21)-(26).

Since $\alpha(\cdot)$ is a monotonically increasing function and
$\beta(\cdot)$ is a monotonically decreasing function. In order to minimize
the above gaps over $\mathsf{q}_{1}$ and $\mathsf{q}_{2}$, the quantization
levels should be set such that

$\alpha(\mathsf{q}_{1}^{*})=\beta(\mathsf{q}_{1}^{*})=\alpha(\mathsf{q}_{2}^{*})=\beta(\mathsf{q}_{2}^{*}),$
(65)

which results in
$\mathsf{q}_{1}^{*}=\mathsf{q}_{2}^{*}=\frac{\sqrt{\rho^{2}+16\rho+16}-\rho}{4}$.
Substituting $\mathsf{q}_{1}^{*}$ and $\mathsf{q}_{2}^{*}$ into the above
gaps, we prove that the constant gap is $\delta$ bits per dimension, where
$\delta$ is given in (59). ∎

Note that the finite capacity gap is an increasing function of $\rho$: smaller
$\rho$ results in a smaller gap. In the case that $\rho=1$, i.e.,
$|g_{1}|\leq|h_{12}|$ and $|g_{2}|\leq|h_{21}|$, the optimal quantization
levels are $\mathsf{q}_{1}^{*}=\mathsf{q}_{2}^{*}=\frac{\sqrt{33}-1}{4}$, and
the gap to the capacity is given by
$\frac{1}{2}\log\left(\frac{5+\sqrt{33}}{4}\right)=1.2128$ bits.

###  II-D Gaussian Relay-Interference Channel with a Broadcasting Relay

(a) GHF

(b) Incremental GHF with a refinement process

(c) Universal GHF

Figure 3: Evolution of the generalized hash-and-forward relay scheme

The GHF relaying scheme originally stated in Theorem 2 requires independent
relay links. As shown in Fig. 3(a), the relay observation $Y_{R}^{n}$
undergoes two separate quantization and binning processes to obtain the two
messages for the two receivers. However, in the weak-relay regime, Theorem 3
shows that using an identical quantization level for the two receivers is
without loss of approximate optimality, thus a common quantization process can
be shared between the two receivers. Further, since the same $\hat{Y}_{R}^{n}$
is binned into bins of sizes $2^{n\mathsf{C}_{1}}$ and $2^{n\mathsf{C}_{2}}$,
this is equivalent to first binning $\hat{Y}_{R}^{n}$ into
$2^{n\mathsf{C}_{1}}$ bins (assuming $\mathsf{C}_{1}\leq\mathsf{C}_{2}$) then
further binning each bin into $2^{n(\mathsf{C}_{2}-\mathsf{C}_{1})}$ sub-bins,
as shown in Fig. 3(b). The message sent to receiver 2 can be thought of as the
refinement of the message sent to receiver 1. This is exactly the incremental
relaying strategy we seek for the Gaussian interference channel with a
broadcasting relay, where the message to receiver 1 is a degraded version of
the message to receiver 2\. Finally, if
$\mathsf{C}_{1}=\mathsf{C}_{2}=\mathsf{C}$, the relay-interference channel
reduces to the universal relaying scheme studied in [23], where a digital link
is shared between the relay and the receivers, as shown in Fig. 3(c). We note
here that the outer bounds for the independent relay link case (Theorem 1)
continues to hold for the degraded broadcast relay case.

######  Corollary 1.

The constant-gap-to-capacity result stated in Theorem 3 holds also for the
Gaussian relay-interference channel with degraded broadcasting relay links,
where (assuming $\mathsf{C}_{1}\leq\mathsf{C}_{2}$) the message sent through
the link with capacity $\mathsf{C}_{1}$ must be a degraded version of the
message sent through the link with capacity $\mathsf{C}_{2}$.

###  II-E Comments on the Strong-Relay Regime

The constant-gap result in this paper holds only in the weak-relay regime of
$|g_{1}|\leq\sqrt{\rho}|h_{12}|$ and $|g_{2}|\leq\sqrt{\rho}|h_{21}|$, where
$\rho$ is finite. The main difficulty in extending this result to the general
case is that both the choice of the Han-Kobayashi power splitting ratio and
the GHF relay strategy are no longer optimal in the strong-relay regime. As
mentioned earlier, the Etkin-Tse-Wang power splitting is not optimal when the
relay links $g_{i},i=1,2$ grow unboundedly stronger than the interference
links $h_{12}$ and $h_{21}$. Further, GHF may not be an appropriate relay
strategy. To see this, assume a channel model with separate relay links and
consider an extreme scenario where the relay links $g_{i},i=1,2$ go to
infinity, while all other channel parameters are kept constant. This special
case is known as the cognitive relay-interference channel [41]. The capacity
region outer bound of Theorem 1 for this case reduces to

$\displaystyle R_{1}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1})+\mathsf{C}_{1}$ (66)
$\displaystyle R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{2})+\mathsf{C}_{2}$ (67)
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{2}+\mathsf{INR}_{1})$ (68)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)+\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})$ (69)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)+\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{INR}_{2}+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{INR}_{1}+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)+\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2}\right)$
(71)
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{INR}_{1}+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)+2\mathsf{C}_{1}+\mathsf{C}_{2}$
$\displaystyle R_{1}+2R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{SNR}_{2}+\mathsf{INR}_{1}\right)$
(72)
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{INR}_{2}+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)+\mathsf{C}_{1}+2\mathsf{C}_{2},$

which is in fact the outer bound of the underlying interference channel
expanded by $\mathsf{C}_{1}$ bits in the $R_{1}$ direction and
$\mathsf{C}_{2}$ in the $R_{2}$ direction. In this special case, a decode-and-
forward strategy can easily achieve the capacity region to within a constant
gap. This is because the relay is capable of decoding all the source messages,
so it can simply forward the bin indices of the privates messages to achieve
$(R_{1}+\mathsf{C}_{1},R_{2}+\mathsf{C}_{2})$ for any achievable rate pair
$(R_{1},R_{2})$ in the absence of the relay. Etkin-Tse-Wang power splitting
with decode-and-forward then achieves the outer bound to within a constant
gap. In contrast, GHF cannot achieve the capacity region to within a constant
gap in this case.

###  II-F Generalized Degrees of Freedom

We can gain further insights into the effect of relaying on the Gaussian
interference channel by analyzing the GDoF of the sum rate in the symmetric
channel setting. Consider the case where
$\mathsf{INR}_{1}=\mathsf{INR}_{2}=\mathsf{INR}$,
$\mathsf{SNR}_{1}=\mathsf{SNR}_{2}=\mathsf{SNR}$,
$\mathsf{SNR}_{r1}=\mathsf{SNR}_{r2}=\mathsf{SNR}_{r}$, and
$\mathsf{C}_{1}=\mathsf{C}_{2}=\mathsf{C}$. In the high SNR regime, similar to
[1, 6], define

$\displaystyle\alpha$ $\displaystyle:=$
$\displaystyle\lim_{\mathsf{SNR}\rightarrow\infty}\frac{\log\mathsf{INR}}{\log\mathsf{SNR}},$
(73) $\displaystyle\beta$ $\displaystyle:=$
$\displaystyle\lim_{\mathsf{SNR}\rightarrow\infty}\frac{\log\mathsf{SNR}_{r}}{\log\mathsf{SNR}},$
(74) $\displaystyle\kappa$ $\displaystyle:=$
$\displaystyle\lim_{\mathsf{SNR}\rightarrow\infty}\frac{\mathsf{C}}{\frac{1}{2}\log\mathsf{SNR}}.$
(75)

The GDoF of the sum capacity is defined as

$d_{\mathrm{sum}}=\left.\lim_{\mathsf{SNR}\rightarrow\infty}\frac{C_{\mathrm{sum}}}{\frac{1}{2}\log\mathsf{SNR}}\right|_{\mathrm{fixed}\;\alpha,\beta,\kappa}$
(76)

As a direct consequence of the constant-gap result, $d_{\mathrm{sum}}$ can be
characterized in the weak-relay regime as follows.

######  Corollary 2.

For the symmetric Gaussian relay-interference channel in the weak-relay regime
(i.e., $\beta\leq\alpha$), the GDoF of the sum capacity is given by the
following. When $0\leq\alpha<1$

$\displaystyle d_{\mathrm{sum}}$ $\displaystyle=$
$\displaystyle\min\left\\{2-\alpha+\min\\{\beta,\kappa\\},2\max\\{\alpha,1-\alpha\\}+2\kappa,\right.$
(77) $\displaystyle\left.\qquad\;2\max\\{\alpha,1+\beta-\alpha\\}\right\\}.$

When $\alpha\geq 1$

$\displaystyle
d_{\mathrm{sum}}=\min\left\\{\alpha+\kappa,\alpha+\beta,2(1+\kappa),2\max\\{1,\beta\\}\right\\}.$
(78)

Note that when $\alpha=1$, the GDoF of the sum capacity is in fact not well
defined. This is because both $\mathsf{INR}=\gamma\mathsf{SNR}$ (where
$\gamma\neq 1$ is finite) and $\mathsf{INR}=\mathsf{SNR}$ result in the same
$\alpha=1$. However, in the case of $\mathsf{INR}=\mathsf{SNR}$, the channel
becomes ill conditioned, i.e. $\phi_{1}=\phi_{2}=0$, which results in a
$d_{\mathrm{sum}}$ other than the one in (78). In other words, multiple values
of $d_{\mathrm{sum}}$ correspond to the same $\alpha=1$. This is similar to
the situation of [6, Theorem 7.3]. Applying the similar argument that the
event $\left\\{\mathsf{INR}=\mathsf{SNR}\right\\}$ is of zero measure, we have
the GDoF of the sum capacity as shown in (78) almost surely.

When the relay links and the interference links share the same channel gain,
i.e. $\alpha=\beta$, the GDoF of the sum capacity reduces to

$\displaystyle
d_{\mathrm{sum}}=\min\left\\{2+\kappa-\alpha,2\max\\{\alpha,1-\alpha\\}+2\kappa,2\right\\}$
(79)

for $0\leq\alpha<1$, and

$d_{\mathrm{sum}}=\min\left\\{\alpha+\kappa,2(1+\kappa),2\alpha\right\\},$
(80)

for $\alpha\geq 1$. Interestingly, this is the same as the sum capacity (in
GDoF) of the Gaussian interference channel with rate-limited receiver
cooperation [6]. Therefore, the same sum capacity GDoF gain can be achieved
with either receiver cooperation or with an independent in-band-reception and
out-of-band-transmission relay assuming that the source-relay links are the
same as the interfering links of the underlying interference channel (i.e.
$\alpha=\beta$).

Fig. 4 shows the GDoF gain due to the relay for the $\alpha=\beta$ case. There
are several interesting features. When $\kappa=0.2$, the GDoF curve remains
the “W” shape for the conventional Gaussian interference channel [1]. The sum-
capacity gain is $2\kappa$ in the very and moderately weak interference
regimes (when $0.2\leq\alpha\leq 0.6$) or the very strong interference regime
($\alpha\geq 2.2$), and is $\kappa$ in other regimes
($\frac{2}{3}\leq\alpha\leq 2$). As $\kappa$ gets larger, the left “V” branch
of the “W” curve becomes smaller, and it disappears completely at the critical
point of $\kappa=0.5$. As $\kappa$ keeps increasing, the right “V” of the “W”
curve also eventually disappears. The detailed sum-capacity gains for
different values of $\alpha$ are listed in Table I.

TABLE I: Sum-capacity GDoF gain due to the relay for the symmetric Gaussian relay-interference channel for the $\alpha=\beta$ and $\kappa\leq\frac{1}{2}$ case Range of $\alpha$ | $\alpha\leq\kappa$ | $\kappa\leq\alpha\leq\frac{2-\kappa}{3}$ | $\frac{2-\kappa}{3}\leq\alpha\leq\frac{2}{3}$ | $\frac{2}{3}\leq\alpha\leq 2$ | $2\leq\alpha\leq 2+\kappa$ | $\alpha\geq 2+\kappa$
---|---|---|---|---|---|---
Gain | $2\alpha$ | $2\kappa$ | $2-3\alpha+\kappa$ | $\kappa$ | $\alpha+\kappa-2$ | $2\kappa$
Figure 4: The GDoF gain due to the relay in a symmetric Gaussian relay-
interference channel for the $\alpha=\beta$ case

###  II-G Interpretation via the Deterministic Relay Channel

In the Han-Kobayashi framework, each input signal of the interference channel
consists of both a common message and a private message. The sum-capacity gain
due to the relay in the relay-interference channel therefore in general
includes improvements in both the common and the private message rates. This
section illustrates that in the asymptotic high SNR regime, the rate
improvement can be interpreted as either a private rate gain alone, or a
common rate gain alone. Further, the one-bit-per-relay-bit or the two-bits-
per-relay-bits GDoF improvement shown in the previous section can be
interpreted using a deterministic relay model. The rest of this section
illustrates this point for the symmetric Gaussian relay-interference channel
in the $\alpha=\beta$ and $\kappa\leq\frac{1}{2}$ case as an example.

####  II-G1 Very Weak Interference Regime

For the symmetric Gaussian interference channel, in the very weak interference
regime of $0\leq\alpha\leq\frac{1}{2}$, common messages do not carry any
information (although it can be assigned nonzero powers as in the Etkin-Tse-
Wang power splitting strategy). Setting $X_{1}$ and $X_{2}$ to be private
messages only is capacity achieving in terms of GDoF ([1, 42, 43, 44]).

Assigning $X_{1}$ and $X_{2}$ to be private only is also optimal for GDoF for
the symmetric Gaussian relay-interference channel in the very weak
interference regime. This is because when $X_{1}$ and $X_{2}$ are both private
messages and are treated as noises at $Y_{2}$ and $Y_{1}$ respectively, the
relay-interference channel asymptotically becomes two deterministic relay
channels in the high SNR regime. Consider the relay operation for $Y_{1}$ as
illustrated in Fig. 5(a). When noise variances of $Z_{1}$ and $Z_{R}$ go down
to zero, the observation at the relay becomes $Y_{R}=gX_{1}+gX_{2}$ and the
received signal at receiver $1$ becomes $Y_{1}=h_{d}X_{1}+h_{c}X_{2}$. In this
case, the relay’s observation is a deterministic function of $X_{1}$ and
$Y_{1}$, i.e. $Y_{R}=gX_{1}+\frac{g}{h_{c}}(Y_{1}-h_{d}X_{1})$. Thus $X_{1}$
and $Y_{1}$, along with the relay $Y_{R}$ form a deterministic relay channel
of the type studied in [45]. According to [45], the achievable rate of user
$1$ is given by

$\displaystyle R_{1}$ $\displaystyle=$
$\displaystyle\min\left\\{I(X_{1};Y_{1},Y_{R}),I(X_{1};Y_{1})+\mathsf{C}\right\\}$
(81) $\displaystyle=$
$\displaystyle\min\left\\{\frac{1}{2}\log(1+h_{d}^{2}),\frac{1}{2}\log\left(1+\frac{h_{d}^{2}}{h_{c}^{2}}\right)+\mathsf{C}\right\\}$
$\displaystyle\rightarrow$ $\displaystyle\min\\{1,1-\alpha+\kappa\\},$

resulting in one-bit improvement for each relay bit in the regime
$\kappa\leq\alpha\leq\frac{1}{2}$. Similarly, as illustrated in Fig. 5(b),
$X_{2}$, $Y_{2}$, and $Y_{R}$ form another deterministic relay channel with
$X_{2}$ as the input, $Y_{2}$ as the output, and $Y_{R}$ as the relay. Thus,
the achievable rate of user $2$ is the same as user $1$, resulting in the same
one-bit-per-relay-bit improvement. Further, as shown in [45], a hash-and-
forward relay strategy achieves the capacity for deterministic relay channels.
As the hashing operation is the same for both case, the same relay bit can
therefore benefit both receivers at the same time, resulting in two-bit
increase in sum capacity for one relay bit, as first pointed out in [22].

(a) At receiver $1$, $X_{2}$ is treated as noise.

(b) At receiver $2$, $X_{1}$ is treated as noise.

Figure 5: Asymptotic deterministic relay channels in the very weak
interference regime $\kappa\leq\alpha\leq\frac{1}{2}$.

####  II-G2 Moderately Weak and Strong Interference Regimes

The above interpretation, which states that the GDoF improvement in the very
weak interference regime comes solely from the private rate gain, is not the
only possible interpretation. The rate gain can also be interpreted as
improvement in common information rate — an interpretation that applies not
only to the very weak interference regime, but in fact to all regimes (for the
symmetric rate with symmetric channels). In the following, we illustrate this
point by focusing on a two-stage Han-Kobayashi strategy, where common messages
are decoded first, then the private messages. This is the same two-stage Han-
Kobayashi scheme used in [1] for the Gaussian interference channel without the
relay.

Specifically, the relay uses the same GHF relaying strategy as in Theorem 3,
but it is now designed to help the common messages only. Here, both common
messages $W_{1}^{n}$ and $W_{2}^{n}$ are decoded and subtracted at both
receivers with the help of the GHF relay first (while treating private
messages as noise), the private messages are then decoded at each receiver
treating each other as noise. The decoding of the private message at the
second stage results in

$\displaystyle R_{u}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{p}}{1+\mathsf{INR}_{p}}\right)$
(82) $\displaystyle\rightarrow$ $\displaystyle\max\\{0,1-\alpha\\},$

Note that the relay does not help the private rate.

In the common-message decoding stage, $W_{1}^{n}$ and $W_{2}^{n}$ are jointly
decoded at both receiver $1$ and receiver $2$ with the help of the GHF relay.
As a result, $(W_{1}^{n},W_{2}^{n},Y_{1}^{n},Y_{R}^{n})$ forms a multiple-
access relay channel at receiver $1$ with $W_{1}^{n},W_{2}^{n}$ as the inputs,
$Y_{1}^{n}$ as the output and $Y_{R}^{n}$ as the relay. The achievable rate
region of such a multiple-access channel with a GHF relay is given by

$\displaystyle R_{w1}$ $\displaystyle\leq$ $\displaystyle
I(W_{1};Y_{1}|W_{2})$
$\displaystyle+\min\left\\{(\mathsf{C}-\xi)^{+},I(W_{1};\hat{Y}_{R}|Y_{1},W_{2})\right\\}$
$\displaystyle R_{w2}$ $\displaystyle\leq$ $\displaystyle
I(W_{2};Y_{1}|W_{1})$
$\displaystyle+\min\left\\{(\mathsf{C}-\xi)^{+},I(W_{2};\hat{Y}_{R}|Y_{1},W_{1})\right\\}$
$\displaystyle R_{w1}+R_{w2}$ $\displaystyle\leq$ $\displaystyle
I(W_{1},W_{2};Y_{1})$
$\displaystyle+\min\left\\{(\mathsf{C}-\xi)^{+},I(W_{1},W_{2};\hat{Y}_{R}|Y_{1})\right\\}.$

With the Etkin-Tse-Wang input strategy (i.e.
$P_{1p}=\min\\{1,h_{12}^{-2}\\},P_{2p}=\min\\{1,h_{21}^{-2}\\}$) and the GHF
relaying scheme with
$\mathsf{q}_{1}=\mathsf{q}_{2}=\frac{\sqrt{\rho^{2}+16\rho+16}-\rho}{4}$, it
can be shown that the common-message rate region for the receiver 1 in the
high SNR regime in term of GDoF is given as follows. When $0\leq\alpha\leq 1$

$\displaystyle R_{w1}$ $\displaystyle\leq$ $\displaystyle\alpha$
$\displaystyle R_{w2}$ $\displaystyle\leq$
$\displaystyle\min\\{\alpha,\kappa+\max\\{2\alpha-1,0\\}\\}$ $\displaystyle
R_{w1}+R_{w2}$ $\displaystyle\leq$
$\displaystyle\alpha+\min\\{\alpha,\kappa\\}.$

When $\alpha\geq 1$

$\displaystyle R_{w1}$ $\displaystyle\leq$
$\displaystyle\min\\{\alpha,1+\kappa\\}$ $\displaystyle R_{w2}$
$\displaystyle\leq$ $\displaystyle\alpha$ $\displaystyle R_{w1}+R_{w2}$
$\displaystyle\leq$ $\displaystyle\alpha+\kappa.$

Due to symmetry, the rate region for the multiple-access relay channel at
receiver $2$ can be obtained by switching the indices $1$ and $2$.

Note that in suitable interference regimes, both the individual rate and the
sum rate can potentially be increased by one bit for each relay bit. This is
again a consequence of the fact that the relay operation has a deterministic
relay channel interpretation in the high SNR regime. For example, in the
strong interference regime where $1\leq\alpha\leq 2+\kappa$, the sum rate of
the multiple-access relay channel benefits by one bit for each relay bit in
the high SNR regime as shown in Fig. 6(a). In the very strong interference
regime, the interference can be decoded, subtracted or can serve as side
information, therefore the individual rate increases by one bit for each relay
bit as shown in Fig. 6(b).

(a) $Y_{1}$ decodes both $X_{1}$ and $X_{2}$.

(b) $X_{2}$ is decoded and serves as side information.

Figure 6: Asymptotic deterministic relay channels in the strong and very
strong interference regimes.

Now, the achievable rates of common messages can be obtained by intersecting
the two rate regions. Taking the achievable rates of private messages in (82)
into account, it is easy to verify that this two-stage Han-Kobayashi scheme
achieves the sum capacity in (79) and (80). As depicted in Fig. 4, the sum-
capacity gain due to the relay can be one-bit-per-bit or two-bits-per-bit. In
the following, we demonstrate in Fig. 7 how these gains are obtained by
pictorially showing the intersection of the two common-message rate regions
for different values of $\alpha$.

(a) $0\leq\alpha\leq\kappa$

(b) $\kappa\leq\alpha\leq\frac{1}{2}$

(c) $\frac{1}{2}\leq\alpha\leq\frac{2-\kappa}{3}$

(d) $\frac{2}{3}\leq\alpha\leq 1$

(e) $1\leq\alpha\leq 1+\kappa$

(f) $\alpha\geq 2+\kappa$

Figure 7: Generalized-degree-of-freedom gain due to relaying is roughly
$\kappa$ or $2\kappa$ depending on how the two common-message multiple-access
regions are intersected

  * •

When $\alpha\leq\kappa$, as can be seen from Fig. 7(a), the two rate regions
are identical and are both given by
$\left\\{(R_{w1},R_{w2}):R_{w1}\leq\alpha,R_{w2}\leq\alpha\right\\}$. The
intersection of the two is the same rectangle with the top-right corner
located at $(\alpha,\alpha)$. This gives a $2\alpha$-bit gain over the
baseline, which is located at the origin.

  * •

As $\alpha$ increases to $\kappa\leq\alpha\leq\frac{1}{2}$, the baseline rate
pair is still at the origin. With the help of the relay, the two common-
message rate regions become rectangles
$\left\\{(R_{w1},R_{w2}):R_{w1}\leq\alpha,R_{w2}\leq\kappa\right\\}$ and
$\left\\{(R_{w1},R_{w2}):R_{w1}\leq\kappa,R_{w2}\leq\alpha\right\\}$
respectively. As shown in Fig. 7(b), the intersection of the two gives a
square with the top-right corner located at $(\kappa,\kappa)$. As a result,
the sum-capacity gain is $2\kappa$ bits.

  * •

As $\alpha$ increases to $\frac{1}{2}\leq\alpha\leq 1$, the common-message
rate regions at receivers $1$ and $2$ become pentagons. However, depending on
the value of $\alpha$, the sum rate improves by different amounts. When
$\alpha\leq\frac{2-\kappa}{3}$, as shown in Fig. 7(c), the intersection of the
two pentagon regions gives a square shape with the top-right corner located at
$(2\alpha-1+\kappa,2\alpha-1+\kappa)$. Compared with $(2\alpha-1,2\alpha-1)$
achieved without the relay, a sum-capacity gain of $2\kappa$ bits is obtained.
However, when $\alpha\geq\frac{2-\kappa}{3}$, as depicted in Fig. 7(d), the
intersection of the two rate regions is still a pentagon with the sum-capacity
limited by $R_{w1}+R_{w2}\leq 2-\alpha+\kappa$. In this case, depending on the
value of $\alpha$, the sum-rate gain is $2-3\alpha+\kappa$ bits when
$\frac{2-\kappa}{3}\leq\alpha\leq\frac{2}{3}$, and is $\kappa$ bits when
$\frac{2}{3}\leq\alpha\leq 1$. (The latter case is shown in Fig. 7(d).)

  * •

When $1\leq\alpha\leq 2+\kappa$, the common-message rate regions are again
pentagons and the interpretation is similar to the
$\frac{2-\kappa}{3}\leq\alpha\leq 1$ case. Fig. 7(e) shows an example of
$1\leq\alpha\leq 1+\kappa$. In this case, the two rate regions are identical
pentagons with the sum capacity limited by $R_{w1}+R_{w2}\leq\alpha+\kappa$.
Compared with the baseline sum capacity, a $\kappa$-bits gain is obtained.
When $1+\kappa\leq\alpha\leq 2+\kappa$, the intersection of the two common-
message rate regions again gives a sum-capacity of $\alpha+\kappa$. However,
since the baseline sum capacity becomes saturated when when $\alpha\geq 2$
([1, 46, 47]), the sum-capacity gain over the baseline is $\kappa$ bits when
$1\leq\alpha\leq 2$, and is $\alpha+\kappa-2$ bits when $2\leq\alpha\leq
2+\kappa$.

  * •

Finally, $\alpha\geq 2+\kappa$ falls into the very strong interference regime.
The intersection of the two common-message rate regions is a rectangle with
the top-right corner located at $(1+\kappa,1+\kappa)$ as shown in Fig. 7(f).
The sum-capacity gain is thus $2\kappa$ bits in the very strong interference
regime.

##  III Gaussian Relay-Interference Channel With a Single Digital Link

The result of the previous section shows that for the symmetric channel, the
sum-capacity improvement can be thought as coming solely from the improvement
of the common message rate, or in a very weak interference regime as coming
solely from the improvement of the private message rates. Thus, the function
of the relay for the symmetric rate in symmetric channel is solely in
forwarding useful signals. This interpretation does not necessarily hold for
the asymmetric cases. In this section, we study a particular asymmetric
channel to illustrate the composition of the sum-capacity gain. We are
motivated by the fact that the relay’s observation in a relay-interference
channel is a linear combination of the intended signal and the interfering
signal. Clearly, forwarding the intended signal and the interfering signal can
both be beneficial (e.g. [12]). This section illustrates that depending on the
different channel parameters, the sum-rate gain from forwarding both intended
signal and interference signal happens to be the same as that of forwarding
intended signal only or forwarding interference signal only.

Specifically, we focus on a particular asymmetric model as shown in Fig. 8,
where the digital relay link exists only for receiver $1$, and not for
receiver $2$, i.e., $\mathsf{C}_{2}=0$. This section first derives a constant-
gap-to-capacity result for this channel. Note that this channel is a special
case of the general channel model studied in the previous section, but the
constant-gap-to-capacity result can be established in this special case for a
broader set of channels. Unlike the weak-relay assumption
$|g_{1}|\leq\sqrt{\rho}|h_{12}|$ and $|g_{2}|\leq\sqrt{\rho}|h_{21}|$ made in
the previous section, this section assumes that
$|g_{2}|\leq\sqrt{\rho}|h_{21}|$ only with no constraints on $g_{1}$ or
$h_{12}$. Under this channel setup, it can be shown that in the high SNR
regime, the sum capacity improvement can also be obtained as if only the
intended signal is forwarded or only the interference signal is forwarded.
Note that this conclusion applies to the case of a single relay-destination
link only, and not necessarily to the general case with two relay-destination
links.

###  III-A Capacity Region to within Constant Gap in the Weak-Relay Regime

Since the channel model studied in Fig. 8 is a special case of the general
Gaussian relay-interference channel, we first simplify the achievable rate
region in Theorem 2 to the following corollary by setting $\mathsf{C}_{2}=0$.
The only difference in the coding scheme is that instead of performing two
quantizations as in the general relay-interference channel, the relay in Fig.
8 does one quantization of the received signal $Y_{R}$ into $\hat{Y}_{R1}$ and
sends the bin index of $\hat{Y}_{R1}$ to receiver $1$ through the digital link
$\mathsf{C}_{1}$.

######  Corollary 3.

Figure 8: Gaussian relay-interference channel with a single digital link

For the Gaussian relay-interference channel with a single digital link as
shown in Fig. 8, the following rate region is achievable:

$\displaystyle 0\leq R_{1}$ $\displaystyle\leq$ $\displaystyle
d_{1}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{d}_{1}\right\\}$ (83)
$\displaystyle 0\leq R_{2}$ $\displaystyle\leq$ $\displaystyle d_{2}$ (84)
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+g_{2}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{a}_{1}\right\\}$
(85) $\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{2}+g_{1}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{g}_{1}\right\\}$
(86) $\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
e_{1}+e_{2}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{e}_{1}\right\\}$
(87) $\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+g_{1}+e_{2}+\min\left\\{2(\mathsf{C}_{1}-\xi_{1})^{+},\right.$ (88)
$\displaystyle\left.\quad(\mathsf{C}_{1}-\xi_{1})^{+}+\Delta{a}_{1},\Delta{a}_{1}+\Delta{g}_{1}\right\\}$
$\displaystyle R_{1}+2R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{2}+g_{2}+e_{1}+\min\left\\{(\mathsf{C}_{1}-\xi_{1})^{+},\Delta{e}_{1}\right\\},$

where all the parameters are as defined in Theorem 2.

The proof follows directly from Theorem 2. Note that in (88), we apply the
fact that $\Delta{a}_{1}\leq\Delta{g}_{1}$. Likewise, the capacity region
outer bound in Theorem 1 also simplifies when $\mathsf{C}_{2}=0$. We can now
prove the following constant-gap theorem for the Gaussian relay-interference
channel with a single digital link.

######  Theorem 4.

For the Gaussian relay-interference channel with a single digital link as
depicted in Fig. 8, with the same signaling strategy as in Theorem 3, i.e. a
combination of the Han-Kobayashi scheme with Etkin-Tse-Wang power splitting
strategy and the GHF relaying scheme with the fixed quantization level
$\mathsf{q}_{1}=\frac{\sqrt{\rho^{2}+16\rho+16}-\rho}{4}$, in the weak-relay
regime of $|g_{2}|\leq\sqrt{\rho}|h_{21}|$, the achievable rate region in
Corollary 3 is within $\delta$ bits of the capacity region outer bound in
Theorem 1 (with $\mathsf{C}_{2}$ set to zero), where $\delta$ is defined in
Theorem 3.

###### Proof:

Although the signalling scheme and the constant gap result resemble those of
Theorem 3, Theorem 4 is not simply obtained by setting $\mathsf{C}_{2}=0$ in
Theorem 3, since the weak-relay condition has been relaxed. In the following,
we prove the constant-gap result by directly comparing each achievable rate
expression with its corresponding upper bound.

Applying the inequalities of Lemma 1 and following along the same lines of the
proof of Theorem 3 in Appendix -C, it is easy to show that each of the
achievable rates in (83)-(LABEL:R12R2_1_single_digital_link) achieves to
within a constant gap of its corresponding upper bound in Theorem 1 (with
$\mathsf{C}_{2}$ set to zero) in the weak-relay regime. The constant gaps are
shown as follows:

(i) Individual rate (83) is within

$\delta_{R_{1}}=\max\left\\{{\alpha}(\mathsf{q}_{1}),{\beta}(\mathsf{q}_{1})\right\\}$
(90)

bits of (7).

(ii) Individual rate (84) is within

$\delta_{R_{2}}=\frac{1}{2}$ (91)

bits of (8).

(iii) Sum rates (85), (86) and (87) are within

$\delta_{R_{1}+R_{2}}=\frac{1}{2}+\max\left\\{{\alpha}(\mathsf{q}_{1}),{\beta}(\mathsf{q}_{1})\right\\}$
(92)

bits of their upper bounds (9), (16), (10), (15),
(LABEL:sumrate_bound_3_twolinks), and (17). Specifically,

  * •

The first term of (85) is within $\frac{1}{2}+{\beta}(\mathsf{q}_{1})$ bits of
(9). The second term is within $\frac{1}{2}+{\alpha}(\mathsf{q}_{1})$ bits of
(16).

  * •

The first term of (86) is within $\frac{1}{2}+{\beta}(\mathsf{q}_{1})$ bits of
(10). The second term is within $\frac{1}{2}+{\alpha}(\mathsf{q}_{1})$ bits of
(15).

  * •

The first term of (87) is within $\frac{1}{2}+{\beta}(\mathsf{q}_{1})$ bits of
(LABEL:sumrate_bound_3_twolinks). The second term is within
$\frac{1}{2}+{\alpha}(\mathsf{q}_{1})$ bits of (17).

Therefore, the achievable sum rate in (85)-(87) is within a constant gap of
the sum-rate upper bound specified by (9)-(20) in the weak-relay regime.

(iv) $2R_{1}+R_{2}$ rate (88) is within

$\delta_{2R_{1}+R_{2}}=\frac{1}{2}+\max\left\\{2{\alpha}(\mathsf{q}_{1}),{\alpha}(\mathsf{q}_{1})+{\beta}(\mathsf{q}_{1}),2{\beta}(\mathsf{q}_{1})\right\\}$
(93)

bits of the upper bounds (21), (26), and (24). Specifically, the first term of
(88) is within $\frac{1}{2}+2{\beta}(\mathsf{q}_{1})$ bits of (21). The second
term is within $\frac{1}{2}+{\alpha}(\mathsf{q}_{1})+{\beta}(\mathsf{q}_{1})$
bits of (26). The third term is within $\frac{1}{2}+2{\alpha}(\mathsf{q}_{1})$
bits of (24).

(v) $R_{1}+2R_{2}$ rate (LABEL:R12R2_1_single_digital_link) is within

$\delta_{R_{1}+2R_{2}}=1+\max\left\\{{\alpha}(\mathsf{q}_{1}),{\beta}(\mathsf{q}_{1})\right\\}$
(94)

bits of the upper bounds

$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{SNR}_{2}+\mathsf{INR}_{1}\right)$
(95)
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{INR}_{2}+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}\right)+\mathsf{C}_{1}$
$\displaystyle 2R_{1}+R_{2}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{2}+\mathsf{INR}_{1})$ (96)
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}}\right)$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right.$
$\displaystyle\left.\qquad\qquad+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right),$

which are not shown explicitly in Theorem 1 but can be obtained by switching
the indices $1$ and $2$ of (21) and (25) followed by setting
$\mathsf{C}_{2}=0$.

Since ${\alpha}(\cdot)$ is an increasing function and ${\beta}(\cdot)$ is a
decreasing function, to minimize the gaps above, we need

${\alpha}(\mathsf{q}_{1}^{*})={\beta}(\mathsf{q}_{1}^{*}),$ (97)

which results in the quantization level
$\mathsf{q}_{1}^{*}=\frac{\sqrt{\rho^{2}+16\rho+16}-\rho}{4}$. With this
optimal quantization level applied to the gaps above, we prove that the
achievable rate region (83)-(LABEL:R12R2_1_single_digital_link) is within

$\displaystyle\max\left\\{\frac{1}{2},\frac{1}{2}\log\left(2+\frac{\rho+\sqrt{\rho^{2}+16\rho+16}}{2}\right)\right\\}$
(98) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(2+\frac{\rho+\sqrt{\rho^{2}+16\rho+16}}{2}\right)$

bits of the capacity region. ∎

###  III-B Generalized Degree of Freedom

We now derive the GDoF of the channel depicted in Fig. 8, for the case where
the underlying interference channel is symmetric, i.e.,
$\mathsf{INR}_{1}=\mathsf{INR}_{2}=\mathsf{INR}$ and
$\mathsf{SNR}_{1}=\mathsf{SNR}_{2}=\mathsf{SNR}$. In the high SNR regime,
define

$\displaystyle\beta_{i}$ $\displaystyle:=$
$\displaystyle\lim_{\mathsf{SNR}\rightarrow\infty}\frac{\log\mathsf{SNR}_{ri}}{\log\mathsf{SNR}},\;\;i=1,2,$
(99) $\displaystyle\kappa_{1}$ $\displaystyle:=$
$\displaystyle\lim_{\mathsf{SNR}\rightarrow\infty}\frac{\mathsf{C}_{1}}{\frac{1}{2}\log\mathsf{SNR}},$
(100)

Applying Theorem 4, we have the following result on the GDoF:

######  Corollary 4.

In the weak-relay regime where $\beta_{2}\leq\alpha$, the GDoF sum capacity of
the symmetric relay-interference channel with a single digital link is given
by the following. For $0\leq\alpha<1$

$\displaystyle
d_{\mathrm{sum}}=\left\\{\begin{array}[]{l}\min\\{2-\alpha,2\max(\alpha,1-\alpha)+\kappa_{1},\max(\alpha,1-\alpha)\\\
\qquad+\max(\beta_{1},1+\beta_{2}-\alpha,\alpha)\\},\qquad\qquad\beta_{1}\leq
1\\\ \min\\{2-\alpha+\kappa_{1},2\max(\alpha,1-\alpha)+\kappa_{1},\\\ \qquad
1+\beta_{1}-\alpha\\},\quad\qquad\qquad\qquad\qquad\quad\beta_{1}\geq
1\end{array}\right.$ (103)

and for $\alpha\geq 1$

$d_{\mathrm{sum}}=\min\\{\alpha,2+\kappa\\}.$ (104)

TABLE II: Sum-capacity GDoF gain due to the relay for the symmetric Gaussian relay-interference channel with a single digital relay link for $\alpha=\beta_{1}=\beta_{2}$ Range of $\alpha$ | $\alpha\leq\kappa$ | $\kappa\leq\alpha\leq\frac{2-\kappa}{3}$ | $\frac{2-\kappa}{3}\leq\alpha\leq\frac{2}{3}$ | $\frac{2}{3}\leq\alpha\leq 2$ | $2\leq\alpha\leq 2+\kappa$ | $\alpha\geq 2+\kappa$
---|---|---|---|---|---|---
Gain | $\alpha$ | $\kappa$ | $2-3\alpha$ | $0$ | $\alpha-2$ | $\kappa$
Figure 9: Impact of the relay-destination link on sum capacity

Table II and Fig. 9 illustrate the GDoF gain due to the relay where the direct
links, the interference links and the links to the relay are symmetric for
both users, and where $\alpha=\beta_{1}=\beta_{2}$. The main feature here is
that there is no gain in sum capacity for $\frac{2}{3}\leq\alpha\leq 2$. In
other regimes of $\alpha$, the sum-capacity gain is roughly one bit per relay
bit.

###  III-C Signal Relaying vs. Interference Forwarding

In the relay-interference channel, the relay observes a corrupted version of
the weighted sum of two source signals $X_{1}$ and $X_{2}$, and forwards a
description to the receiver. Intuitively, the observations about both source
signals are helpful. For the receiver $1$, the observation about $X_{1}$ helps
receiver $1$ reinforce the signal intended for it; the observation about
$X_{2}$ helps receiver $1$ mitigate the interference. The former can be
thought of as signal relaying, the latter interference forwarding.

In this section, we show that the sum-capacity gain in a Gaussian interference
channel due to a single relay link is equivalent to that achievable with
signal relaying alone or with interference forwarding alone, depending on the
channel parameters. Toward this end, we first set the source-relay link from
$X_{2}$ to zero, i.e., $g_{2}=0$, and compute the GDoF of the sum capacity. In
this case, the sum-capacity gain must be solely due to forwarding intended
signal $X_{1}$. Similarly, we can also set $g_{1}=0$, and compute the GDoF of
the sum-capacity gain due solely to forwarding interference signal $X_{2}$. By
comparing these rates we show that interestingly when the relay link of user
$1$ is under certain threshold, i.e., $\beta_{1}\leq 1-\alpha+\beta_{2}$, the
sum-capacity gain is equivalent to that achievable by interference forwarding.
When $\beta_{1}\geq 1-\alpha+\beta_{2}$, the sum-capacity gain is equivalent
to that achievable by signal relaying.

More specifically, with $g_{2}=0$, the sum-capacity can be computed as

$\displaystyle
d_{SR}=\left\\{\begin{array}[]{l}\min\\{2-\alpha,2\max(\alpha,1-\alpha)+\kappa_{1},\max(\alpha,1-\alpha)\\\
\qquad+\max(\beta_{1},1-\alpha,\alpha)\\},\qquad\qquad\qquad\;\;\beta_{1}\leq
1\\\ \min\\{2-\alpha+\kappa_{1},2\max(\alpha,1-\alpha)+\kappa_{1},\\\
\qquad\;1+\beta_{1}-\alpha\\}.\qquad\qquad\qquad\qquad\qquad\beta_{1}\geq
1\end{array}\right.$ (107)

Similarly, let $g_{1}=0$. The sum-capacity GDoF obtained by forwarding
interference signal is

$\displaystyle d_{IF}$ $\displaystyle=$
$\displaystyle\min\\{2-\alpha,2\max(\alpha,1-\alpha)+\kappa_{1},\max(\alpha,1-\alpha)$
(108) $\displaystyle\qquad\;+\max(1+\beta_{2}-\alpha,\alpha)\\}.$

Comparing (103), (107), and (108), it is easy to verify that

$\displaystyle d_{sum}=\left\\{\begin{array}[]{ll}d_{IF}&{\rm\ when\ \
}\beta_{1}\leq 1+\beta_{2}-\alpha\\\ d_{SR}&{\rm\ when\ \ }\beta_{1}\geq
1+\beta_{2}-\alpha\end{array}\right..$ (111)

Therefore, we observe the following threshold effects. When the relay link
from user $1$ is weak, the sum-capacity gain is equivalent to a channel with a
single source-relay link from $X_{2}$. As the source-relay link from $X_{1}$
grows stronger and crosses a threshold $\beta_{1}\geq
1+\beta_{2}-\alpha\triangleq\beta_{1}^{*}$, the sum-capacity gain becomes
equivalent to that of a single source-relay link from $X_{1}$. Note that this
is a GDoF phenomenon in the high SNR regime. In the general SNR regime, the
sum-capacity gain contains contributions from both signal relaying and
interference forwarding.

Figure 10: Signal relaying vs. interference forwarding

To visualize the interaction of signal relaying and interference forwarding, a
numerical example is provided in Fig. 10. The channel parameters are set to
$\alpha=0.5$, $\beta_{2}=0.2$, and $\kappa_{1}=0.5$. The GDoF of the sum
capacity is plotted as a function of $\beta_{1}$. The sum capacity of the
interference channel without the relay serves as the baseline:

$d_{BL}=\min\left\\{2-\alpha,2\max(\alpha,1-\alpha)\right\\}.$ (112)

Fig. 10 shows the sum-capacity gain due to the relay. When
$\beta_{1}\leq\beta_{1}^{*}=0.7$, the gain (labeled as $\mathcal{R}_{1}$) is
equivalent to that by forwarding interference signal only. When $\beta\geq
0.7$, the gain (labeled as $\mathcal{R}_{2}$) is equivalent to that by
forwarding intended signal only.

##  IV Conclusion

This paper investigates GHF as an incremental relay strategy for a Gaussian
interference channel augmented with an out-of-band broadcasting relay, in
which the relay message to one receiver is a degraded version of the message
to the other receiver. We focus on a weak-relay regime, where the transmitter-
to-relay links are not unboundedly stronger than the interfering links of the
interference channel, and show that GHF achieves to within a constant gap to
the capacity region in the weak-relay regime. Further, in a symmetric setting,
each common relay bit can be worth either one or two bits in the sum capacity
gain, illustrating the potential for a cell-edge relay in improving the system
throughput of a wireless cellular network.

Furthermore, the Gaussian relay-interference channels with a single relay link
is also studied. The capacity region is characterized to within a constant gap
for a larger range of channel parameters. It is shown that in the high SNR
regime, the sum-capacity improvement is equivalent either to that of a single
source-relay link from user $1$ or that of a single source-relay link from
user $2$.

###  -A Proof of Theorem 1

Define $V_{1}^{n}$ as the output of the digital link $\mathsf{C}_{1}$, and
$V_{2}^{n}$ as the output of the digital link $\mathsf{C}_{2}$. The outer
bounds are proved as follows:

(i) Individual-rate bounds: First, the first term of (7) is the simple cut-set
upper bound for $R_{1}$. For the second term, starting from Fano’s inequality,
we have

$\displaystyle n(R_{1}-\epsilon_{n})$ $\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})$ $\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n},X_{2}^{n})$ $\displaystyle\leq$
$\displaystyle\frac{n}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}).$

The outer bound of $R_{2}$ in (8) can be proved in the same way.

(ii) Sum-rate bounds:

  * •

First, (9)-(LABEL:sumrate_bound_3_twolinks) are obtained from Fano’s
inequalities, i.e.,

$\displaystyle n(R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle=$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n})+I(X_{2}^{n};Y_{2}^{n})+I(X_{1}^{n};V_{1}^{n}|Y_{1}^{n})$
$\displaystyle+I(X_{2}^{n};V_{2}^{n}|Y_{2}^{n})$ $\displaystyle\leq$
$\displaystyle
I(X_{1}^{n};Y_{1}^{n})+I(X_{2}^{n};Y_{2}^{n})+h(V_{1}^{n})+h(V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
nC_{sum}(0)+n\mathsf{C}_{1}+n\mathsf{C}_{2},$

where $C_{sum}(0)$ is the sum capacity of the interference channel without
relay. Clearly, the sum-rate gain due to the digital relay is upper bounded by
the rates of digital links. Although the sum-rate capacity $C_{sum}(0)$ is not
known in general, its upper bound has been studied in literature [1, 34, 42,
43, 44, 48]. Applying the sum-rate outer bounds in [34], we obtain
(9)-(LABEL:sumrate_bound_3_twolinks).

  * •

Second, (12)-(14) can be obtained by the following steps:

$\displaystyle n(R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n})+h(V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},Y_{R}^{n}),$

where in (a) we give genie $Y_{R}^{n}$ to receiver $2$ and apply the fact that
$\hat{Y}_{R}$ is a function of $Y_{R}$. Note that
$I(X_{1}^{n};Y_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},Y_{R}^{n})$ is upper bounded by
the sum capacity of the SIMO interference channel with $X_{1}^{n}$ and
$X_{2}^{n}$ as the input, and $Y_{1}^{n}$ and $(Y_{2}^{n},Y_{R}^{n})$ as the
output. The sum-rate outer bound of such a SIMO interference channel has been
studied in [34], which along with $h(V_{1}^{n})\leq n\mathsf{C}_{1}$ gives the
outer bounds of (12)-(14).

  * •

Third, (15)-(17) can be similarly derived following the same steps of
(12)-(14) with indices $1$ and $2$ switched.

  * •

Fourth, (18)-(20) can be obtained by giving $Y_{R}^{n}$ as a genie to both
receivers, i.e.,

$\displaystyle n(R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n})+I(X_{2}^{n};Y_{2}^{n},Y_{R}^{n}),$

which is upper bounded by the sum capacity of the SIMO interference channel
with $X_{1}^{n}$ and $X_{2}^{n}$ as input, and $(Y_{1}^{n},Y_{R}^{n})$ and
$(Y_{2}^{n},Y_{R}^{n})$ as output. Applying the result in [34], we have
(18)-(20).

(iii) $2R_{1}+R_{2}$ bounds: Six upper bounds on $2R_{1}+R_{2}$.

  * •

First, (21) is simply the cut-set bound, i.e.,

$\displaystyle n(2R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$
$\displaystyle
2I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
2I(X_{1}^{n};Y_{1}^{n})+I(X_{2}^{n};Y_{2}^{n})+2h(V_{1}^{n})+h(V_{2}^{n}),$

where $2I(X_{1}^{n};Y_{1}^{n})+I(X_{2}^{n};Y_{2}^{n})$ is upper bounded by the
$2R_{1}+R_{2}$ bound of the interference channel with $X_{1}^{n}$ and
$X_{2}^{n}$ as the input, and $Y_{1}^{n}$ and $Y_{2}^{n}$ as the output, which
together with $h(V_{1}^{n})\leq n\mathsf{C}_{1}$ and $h(V_{2}^{n})\leq
n\mathsf{C}_{2}$ gives the upper bound in (21).

  * •

Second, (22) can be derived by giving genie $Y_{R}^{n}$ to both receivers:

$\displaystyle n(2R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$
$\displaystyle
2I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
2I(X_{2}^{n};Y_{1}^{n},Y_{R}^{n})+I(X_{2}^{n};Y_{2}^{n},Y_{R}^{n}),$

which is upper bounded by the $2R_{1}+R_{2}$ bound of the SIMO interference
channel with $X_{1}^{n}$ and $X_{2}^{n}$ as the input, and
$(Y_{1}^{n},Y_{R}^{n})$ and $(Y_{2}^{n},Y_{R}^{n})$ as the output. Applying
the result of [34], we obtain (22).

  * •

Third, (23) can be obtained by giving genies $(X_{2}^{n},Y_{R}^{n},S_{1}^{n})$
to $Y_{1}^{n}$ in one of the two $R_{1}$ expressions and
$(S_{2}^{n},Y_{R}^{n})$ to $Y_{2}^{n}$, where genies $S_{1}^{n}$ and
$S_{2}^{n}$ are defined as

$S_{1}^{n}=h_{12}X_{1}^{n}+Z_{2},\qquad S_{2}^{n}=h_{21}X_{2}^{n}+Z_{1}.$
(119)

According to Fano’s inequality, we have

$\displaystyle n(2R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$
$\displaystyle
2I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n},S_{1}^{n},X_{2}^{n})+I(X_{1}^{n};Y_{1}^{n})+h(V_{1}^{n})$
$\displaystyle+I(X_{2}^{n};Y_{2},Y_{R}^{n},S_{2}^{n})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n},S_{1}^{n}|X_{2}^{n})+h(Y_{1}^{n})-h(S_{2}^{n})+n\mathsf{C}_{1}$
$\displaystyle+I(X_{2}^{n};S_{2}^{n})+I(X_{2}^{n};Y_{2}^{n},Y_{R}^{n}|S_{2}^{n})$
$\displaystyle=$ $\displaystyle
I(X_{1}^{n};S_{1}^{n})+I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n}|S_{1}^{n},X_{2}^{n})+h(Y_{1}^{n})$
$\displaystyle-h(S_{2}^{n})+n\mathsf{C}_{1}+h(S_{2}^{n})-h(Z_{1}^{n})$
$\displaystyle+h(Y_{2}^{n},Y_{R}^{n}|S_{2}^{n})-h(S_{1}^{n})-h(Y_{R}^{n}|Y_{2}^{n},X_{2}^{n})$
$\displaystyle=$ $\displaystyle
h(Y_{1}^{n})-h(Z_{1}^{n})+h(Y_{1}^{n},Y_{R}^{n}|S_{1}^{n},X_{2}^{n})+n\mathsf{C}_{1}$
$\displaystyle-h(Z_{1}^{n},Z_{R}^{n})+h(Y_{2}^{n},Y_{R}^{n}|S_{2}^{n})-h(Z_{2}^{n},Z_{R}^{n})$
$\displaystyle-I(Y_{R}^{n};X_{1}^{n}|X_{2}^{n},Y_{2}^{n})$ $\displaystyle\leq$
$\displaystyle
h(Y_{1}^{n})-h(Z_{1}^{n})+h(Y_{1}^{n},Y_{R}^{n}|S_{1}^{n},X_{2}^{n})+n\mathsf{C}_{1}$
$\displaystyle-h(Z_{1}^{n},Z_{R}^{n})+h(Y_{2}^{n},Y_{R}^{n}|S_{2}^{n})-h(Z_{2}^{n},Z_{R}^{n}),$

where in (a) we use the fact that $X_{1}^{n}$ is independent with $X_{2}^{n}$.
Note that, the last inequality of (• ‣ -A) is maximized by Gaussian inputs
$X_{1}^{n}$ and $X_{2}^{n}$ with i.i.d $\mathcal{N}(0,1)$ entries, because

    * –

$h(Y_{1}^{n})$ is maximized by Gaussian distributions, and

    * –

$h(Y_{1}^{n},Y_{R}^{n}|S_{1}^{n},X_{2}^{n})$ and
$h(Y_{2}^{n},Y_{R}^{n}|S_{2}^{n})$ are both maximized by Gaussian inputs since
the conditional entropy under a power constraint is maximized by Gaussian
distributions.

Applying Gaussian distributions to the last inequality of (• ‣ -A), we have
(23).

  * •

Fourth, (24) can be obtained by giving genie $Y_{R}^{n}$ to $Y_{1}^{n}$, i.e.,

$\displaystyle n(2R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$
$\displaystyle
2I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
2I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n})+I(X_{2}^{n};Y_{2}^{n})+h(V_{2}^{n}),$

where $2I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n})+I(X_{2}^{n};Y_{2}^{n})$ is upper
bounded by the $2R_{1}+R_{2}$ bound of the SIMO interference channel with
$X_{1}^{n}$ and $X_{2}^{n}$ as the input, and $(Y_{1}^{n},Y_{R}^{n})$ and
$Y_{2}^{n}$ as the output. Applying the result of [34] and the fact that
$h(V_{2}^{n})\leq n\mathsf{C}_{2}$, we obtain (24).

  * •

Fifth, (25) can be obtained by giving genie $Y_{R}^{n}$ to $Y_{2}^{n}$, i.e.,

$\displaystyle n(2R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$
$\displaystyle
2I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
2I(X_{1}^{n};Y_{1}^{n})+2h(V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},Y_{R}^{n}),$

where $2I(X_{1}^{n};Y_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},Y_{R}^{n})$ is upper
bounded by the $2R_{1}+R_{2}$ bound of the SIMO interference channel with
$X_{1}^{n}$ and $X_{2}^{n}$ as the input, and $Y_{1}^{n}$ and
$(Y_{2}^{n},Y_{R}^{n})$ as the output. Applying the result of [34] and the
fact that $h(V_{1}^{n})\leq n\mathsf{C}_{1}$, we obtain (25).

  * •

Sixth, (26) can be obtained by giving genies $(X_{2}^{n},Y_{R}^{n},S_{1}^{n})$
to $Y_{1}^{n}$ in one of the two $R_{1}$ expressions, and $S_{2}^{n}$ to
$Y_{2}^{n}$, i.e.,

$\displaystyle n(2R_{1}+R_{2}-\epsilon_{n})$ $\displaystyle\leq$
$\displaystyle
2I(X_{1}^{n};Y_{1}^{n},V_{1}^{n})+I(X_{2}^{n};Y_{2}^{n},V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};Y_{1}^{n},Y_{R}^{n},S_{1}^{n},X_{2}^{n})+I(X_{1}^{n};Y_{1}^{n})+h(V_{1}^{n})$
$\displaystyle+I(X_{2}^{n};Y_{2}^{n},S_{2}^{n})+h(V_{2}^{n})$
$\displaystyle\leq$ $\displaystyle
I(X_{1}^{n};S_{1}^{n})+I(X_{1}^{n};Y_{1}^{n}Y_{R}^{n}|S_{1}^{n},X_{2}^{n})+h(Y_{1}^{n})$
$\displaystyle-h(S_{2}^{n})+I(X_{2}^{n};S_{2}^{n})+I(X_{2}^{n};Y_{2}^{n}|S_{2}^{n})$
$\displaystyle+n\mathsf{C}_{1}+n\mathsf{C}_{2}$ $\displaystyle\leq$
$\displaystyle
h(S_{1}^{n})-h(Z_{2}^{n})+h(Y_{1}^{n},Y_{R}^{n}|S_{1}^{n},X_{2}^{n})$
$\displaystyle-h(Z_{1}^{n},Z_{R}^{n})+h(Y_{1}^{n})-h(S_{2}^{n})+h(S_{2}^{n})-h(Z_{1}^{n})$
$\displaystyle+h(Y_{2}^{n}|S_{2}^{n})-h(S_{1}^{n})+n\mathsf{C}_{1}+n\mathsf{C}_{2}$
$\displaystyle=$ $\displaystyle
h(Y_{1}^{n})-h(Z_{1}^{n})+h(Y_{1}^{n},Y_{R}^{n}|S_{1}^{n},X_{2}^{n})$
$\displaystyle-h(Z_{1}^{n},Z_{R}^{n})+h(Y_{2}^{n}|S_{2}^{n})-h(Z_{2}^{n})+n\mathsf{C}_{1}+n\mathsf{C}_{2},$

which is maximized by Gaussian distributions of $X_{1}^{n}$ and $X_{2}^{n}$
with i.i.d entries following $\mathcal{N}(0,1)$. Applying Gaussian
distributions to (• ‣ -A), we obtain (26).

###  -B Useful Inequalities

This appendix provides several inequalities that are useful to prove the
constant-gap theorems.

######  Lemma 1.

For
$\Delta{a}_{i},a_{i},\Delta{d}_{i},d_{i},\Delta{e}_{i},e_{i},\Delta{g}_{i},g_{i}$
and $\xi_{i},i=1,2$ as defined in (36)-(44), with $Q$ set as a constant, when
$W_{i},X_{i}$ are generated from a superposition coding of $X_{i}=U_{i}+W_{i}$
with $U_{i}\sim~{}\mathcal{N}(0,P_{ip})$ and $W_{i}\sim\mathcal{N}(0,P_{ic})$,
where $P_{ip}+P_{ic}=1$ and
$P_{1p}=\min\\{1,h_{12}^{-2}\\},P_{2p}=\min\\{1,h_{21}^{-2}\\}$, and when the
GHF quantization variables are set to
$\hat{Y}_{R1}=Y_{R}+e_{1},\hat{Y}_{R2}=Y_{R}+e_{2}$, where
$e_{1}\sim\mathcal{N}(0,\mathsf{q}_{1})$ and
$e_{2}\sim\mathcal{N}(0,\mathsf{q}_{2})$, in the weak-relay regime of
$|g_{1}|\leq\sqrt{\rho}|h_{12}|,|g_{2}|\leq\sqrt{\rho}|h_{21}|$, the mutual
information terms in (36)-(44) can be bounded as follows:

$\displaystyle a_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)-\frac{1}{2},$
(124) $\displaystyle a_{1}+\Delta{a}_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)-\alpha(\mathsf{q}_{1}),$
(125) $\displaystyle d_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1})-\frac{1}{2},$ (126)
$\displaystyle d_{1}+\Delta{d}_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{SNR}_{r1})-\alpha(\mathsf{q}_{1}),$
(127) $\displaystyle e_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}+\mathsf{INR}_{2}\right)-\frac{1}{2},$
(128) $\displaystyle e_{1}+\Delta{e}_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right.$
(129)
$\displaystyle\left.\qquad\;\;+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)-\alpha(\mathsf{q}_{1}),$
$\displaystyle g_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})-\frac{1}{2}$
(130) $\displaystyle g_{1}+\Delta{g}_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}\right.$
(131)
$\displaystyle\left.\qquad\;\;+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)-\alpha(\mathsf{q}_{1}),$
$\displaystyle\xi_{1}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{1+\rho}{\mathsf{q}_{1}}\right)=\beta(\mathsf{q}_{1})-\frac{1}{2},$
(132)

and the lower bounds of
$a_{2},a_{2}+\Delta{a}_{2},d_{2},d_{2}+\Delta{d}_{2},e_{2},e_{2}+\Delta{e}_{2},g_{2},g_{2}+\Delta{g}_{2}$
and the upper bound of $\xi_{2}$ can be obtained by switching the indices of
$1$ and $2$ in (124)-(132).

###### Proof:

First, define the signal-to-noise and interference-to-noise ratios of the
private messages as

$\displaystyle\mathsf{SNR}_{1p}$
$\displaystyle=|h_{11}|^{2}P_{1p},\qquad\mathsf{SNR}_{2p}$
$\displaystyle=|h_{22}|^{2}P_{2p},$ (133) $\displaystyle\mathsf{INR}_{1p}$
$\displaystyle=|h_{12}|^{2}P_{1p},\qquad\mathsf{INR}_{2p}$
$\displaystyle=|h_{21}|^{2}P_{2p},$ (134) $\displaystyle\mathsf{SNR}_{r1p}$
$\displaystyle=|g_{1}|^{2}P_{1p},\qquad\mathsf{SNR}_{r2p}$
$\displaystyle=|g_{2}|^{2}P_{2p},$ (135)

which can be lower bounded or upper bounded as follows:

$\displaystyle\mathsf{SNR}_{1p}$ $\displaystyle=$
$\displaystyle|h_{11}|^{2}P_{1p}$ (136) $\displaystyle=$
$\displaystyle\min\left\\{|h_{11}|^{2},\frac{|h_{11}|^{2}}{|h_{12}|^{2}}\right\\}$
$\displaystyle=$
$\displaystyle\min\left\\{\mathsf{SNR}_{1},\frac{\mathsf{SNR}_{1}}{\mathsf{INR}_{1}}\right\\}$
$\displaystyle\geq$
$\displaystyle\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}},$

and

$\displaystyle 0\leq\mathsf{INR}_{1p}=\min\\{1,\mathsf{INR}_{1}\\}\leq 1,$
(137)

and

$\displaystyle\mathsf{SNR}_{r1p}$ $\displaystyle=$
$\displaystyle|g_{1}|^{2}P_{1p}$ (138) $\displaystyle=$
$\displaystyle\min\left\\{|g_{1}|^{2},\frac{|g_{1}|^{2}}{|h_{12}|^{2}}\right\\}$
$\displaystyle=$
$\displaystyle\min\left\\{\mathsf{SNR}_{r1},\frac{\mathsf{SNR}_{r1}}{\mathsf{INR}_{1}}\right\\}$
$\displaystyle\geq$
$\displaystyle\frac{\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}.$

Since $|g_{1}|\leq\sqrt{\rho}|h_{12}|$, $\mathsf{SNR}_{r1p}$ is upper bounded
by $\rho$. Therefore

$\rho\geq\mathsf{SNR}_{r1p}\geq\frac{\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}.$
(139)

Switching the indices of $1$ and $2$, we have

$\displaystyle\mathsf{SNR}_{2p}$
$\displaystyle\geq\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}},$ (140)
$\displaystyle 1\geq\mathsf{INR}_{2p}$ $\displaystyle\geq 0,$ (141)
$\displaystyle\rho\geq\mathsf{SNR}_{r2p}$
$\displaystyle\geq\frac{\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}.$ (142)

Now, starting from (124), we prove the inequalities one by one.

  * •

First, (124) is lower bounded by

$\displaystyle a_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1};Y_{1}|W_{1},W_{2})$ (143) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{1+\mathsf{SNR}_{1p}+\mathsf{INR}_{2p}}{1+\mathsf{INR}_{2p}}\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1p})-\frac{1}{2}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)-\frac{1}{2},$

where (a) holds because $0\leq\mathsf{INR}_{2p}\leq 1$ and (b) is due to the
fact that $\mathsf{SNR}_{1p}\geq\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}$.

  * •

Second, (125) is lower bounded by (144),

$\displaystyle a_{1}+\Delta{a}_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1};Y_{1}|W_{1},W_{2})+I(X_{1};\hat{Y}_{R1}|Y_{1},W_{1},W_{2})$ (144)
$\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{(\mathsf{q}_{1}+1)(1+\mathsf{SNR}_{1p}+\mathsf{INR}_{2p})+\mathsf{SNR}_{r1p}+\mathsf{SNR}_{r2p}(1+\phi_{1}^{2}\mathsf{SNR}_{1p})}{(\mathsf{q}_{1}+1)(1+\mathsf{INR}_{2p})+\mathsf{SNR}_{r2p}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1p}+\mathsf{SNR}_{r1p})-\frac{1}{2}\log((\mathsf{q}_{1}+1)(1+\mathsf{INR}_{2p})+\mathsf{SNR}_{r2p})$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)-\alpha(\mathsf{q}_{1}),$

where (a) holds because
$\mathsf{SNR}_{1p}\geq\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}$,
$\mathsf{SNR}_{r1p}\geq\frac{\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}$, and

$\displaystyle\frac{1}{2}\log((\mathsf{q}_{1}+1)(1+\mathsf{INR}_{2p})+\mathsf{SNR}_{r2p})$
(145) $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log((\mathsf{q}_{1}+1)(1+1)+\rho)$ $\displaystyle=$
$\displaystyle\alpha(\mathsf{q}_{1}).$

  * •

Third, (126) is lower bounded by

$\displaystyle d_{1}$ $\displaystyle=$ $\displaystyle I(X_{1};Y_{1}|W_{2})$
(146) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{1+\mathsf{SNR}_{1}+\mathsf{INR}_{2p}}{1+\mathsf{INR}_{2p}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1})-\frac{1}{2}.$

  * •

Fourth, (127) is lower bounded by (147).

$\displaystyle d_{1}+\Delta{d}_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1};Y_{1}|W_{2})+I(X_{1};\hat{Y}_{R1}|Y_{1},W_{2})$ (147) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{(\mathsf{q}_{1}+1)(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2p})+\mathsf{SNR}_{r1}+\mathsf{SNR}_{r2p}(1+\phi_{1}^{2}\mathsf{SNR}_{1})}{(\mathsf{q}_{1}+1)(1+\mathsf{INR}_{2p})+\mathsf{SNR}_{r2p}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{SNR}_{r1})-\alpha(\mathsf{q}_{1}).$

  * •

Fifth, (128) is lower bounded by

$\displaystyle e_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1},W_{2};Y_{1}|W_{1})$ (148) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{1+\mathsf{SNR}_{1p}+\mathsf{INR}_{2}}{1+\mathsf{INR}_{2p}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}+\mathsf{INR}_{2}\right)-\frac{1}{2}.$

  * •

Sixth, (129) is lower bounded by (149).

$\displaystyle e_{1}+\Delta{e}_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1},W_{2};Y_{1}|W_{1})+I(X_{1},W_{2};\hat{Y}_{R1}|Y_{1},W_{1})$ (149)
$\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{(\mathsf{q}_{1}+1)(1+\mathsf{SNR}_{1p}+\mathsf{INR}_{2})+\mathsf{SNR}_{r1p}+\mathsf{SNR}_{r2}(1+\phi_{1}^{2}\mathsf{SNR}_{1p})}{(\mathsf{q}_{1}+1)(1+\mathsf{INR}_{2p})+\mathsf{SNR}_{r2p}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)-\alpha(\mathsf{q}_{1}).$

  * •

Seventh, (130) is lower bounded by

$\displaystyle g_{1}$ $\displaystyle=$ $\displaystyle I(X_{1},W_{2};Y_{1})$
(150) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{1+\mathsf{SNR}_{1}+\mathsf{INR}_{2}}{1+\mathsf{INR}_{2p}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})-\frac{1}{2}.$

  * •

Eighth, (131) is lower bounded by (151).

$\displaystyle g_{1}+\Delta{g}_{1}$ $\displaystyle=$ $\displaystyle
I(X_{1},W_{2};Y_{1})+I(X_{1},W_{2};\hat{Y}_{R1}|Y_{1})$ (151) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(\frac{(\mathsf{q}_{1}+1)(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})+\mathsf{SNR}_{r1}+\mathsf{SNR}_{r2}(1+\phi_{1}^{2}\mathsf{SNR}_{1})}{(\mathsf{q}_{1}+1)(1+\mathsf{INR}_{2p})+\mathsf{SNR}_{r2p}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)-\alpha(\mathsf{q}_{1}).$

  * •

Ninth, (132) is upper bounded by

$\displaystyle\xi_{1}$ $\displaystyle=$ $\displaystyle
I(Y_{R}:\hat{Y}_{R1}|Y_{1},X_{1},W_{2})$ (152) $\displaystyle=$
$\displaystyle\frac{1}{2}\log\left(1+\frac{1}{\mathsf{q}_{1}}\left(1+\frac{\mathsf{SNR}_{r2p}}{1+\mathsf{INR}_{2p}}\right)\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{1+\rho}{\mathsf{q}_{1}}\right)$

∎

###  -C Proof of Theorem 3

In this appendix, we show that using the Han-Kobayashi power splitting
strategy with the private message power set to
$P_{1p}=\min\\{1,h_{12}^{-2}\\}$ and $P_{2p}=\min\\{1,h_{21}^{-2}\\}$, all the
achievable rates in (29)-(35) are within constant bits of their corresponding
outer bounds in Theorem 1. Note that, in the following proof, inequalities in
Appendix -B are implicitly used without being mentioned.

(i) First, (29) is within constant bits of (7), and (30) is within constant
bits of (8). To see this, the first term of (29) is lower bounded by

$\displaystyle d_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1})-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1})+\mathsf{C}_{1}-\left(\frac{1}{2}+\frac{1}{2}\log\left(1+\frac{1+\rho}{\mathsf{q}_{1}}\right)\right)$

which is within $\beta(\mathsf{q}_{1})$ bits of the first term of (7).

According to Lemma 1, the second term of (29) is lower bounded by

$\displaystyle d_{1}+\Delta{d}_{1}$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{SNR}_{r1})-\alpha(\mathsf{q}_{1}),$

which is within $\alpha(\mathsf{q}_{1})$ bits of the second term of (7). As a
result, the gap between (29) and (7) is bounded by

$\delta_{R_{1}}=\max\left\\{\alpha(\mathsf{q}_{1}),\beta(\mathsf{q}_{1})\right\\}.$
(155)

Due to symmetry, (30) is within

$\delta_{R_{2}}=\max\left\\{\alpha(\mathsf{q}_{2}),\beta(\mathsf{q}_{2})\right\\}$
(156)

bits of the upper bound (8).

(ii) Second, (31)-(33) are within constant bits of their upper bounds
(9)-(20). To see this, inspecting the expressions of the achievable sum rates,
it is easy to see that each of (31)-(33) has four possible combinations:
having both $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$, having $\mathsf{C}_{1}$
only, having $\mathsf{C}_{2}$ only, and having none of $\mathsf{C}_{1}$ and
$\mathsf{C}_{2}$. In the following, we show that, when specialized into the
above four combinations, (31)-(33) are within constant gap to the upper bounds
(9)-(20). The constant gaps are given by
$\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})}$,
$\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{0})}$,
$\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{C}_{2})}$, and
$\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})}$ (to be defined later)
respectively, each corresponding to a specific combination.

  * •

First, when having both $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$, (31)-(33)
become

$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+g_{2}+(\mathsf{C}_{1}-\xi_{1})^{+}+(\mathsf{C}_{2}-\xi_{2})^{+},$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{2}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+(\mathsf{C}_{2}-\xi_{2})^{+},$
$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
e_{1}+e_{2}+(\mathsf{C}_{1}-\xi_{1})^{+}+(\mathsf{C}_{2}-\xi_{2})^{+},$

which are within constant bits of (9)-(LABEL:sumrate_bound_3_twolinks)
respectively. To show this, first, according to Lemma 1, (• ‣ -C) is lower
bounded by

$\displaystyle
a_{1}+g_{2}+(\mathsf{C}_{1}-\xi_{1})^{+}+(\mathsf{C}_{2}-\xi_{2})^{+}$ (160)
$\displaystyle\geq\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)-\frac{1}{2}$
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{2}+\mathsf{INR}_{1})-\frac{1}{2}$
$\displaystyle+\mathsf{C}_{1}-\xi_{1}+\mathsf{C}_{2}-\xi_{2},$

which is within

$\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})}=\beta(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})$
(161)

bits of the upper bound (9). Due to symmetry, (• ‣ -C) is within
$\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})}$ bits of the upper
bound (10) as well. Now applying Lemma 1, (• ‣ -C) is lower bounded by

$\displaystyle
e_{1}+e_{2}+(\mathsf{C}_{1}-\xi_{1})^{+}+(\mathsf{C}_{2}-\xi_{2})^{+}$ (162)
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}+\mathsf{INR}_{2}\right)-\frac{1}{2}$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}+\mathsf{INR}_{1}\right)-\frac{1}{2}$
$\displaystyle+\mathsf{C}_{1}-\xi_{1}+\mathsf{C}_{2}-\xi_{2},$

which is within $\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})}$ bits
of the upper bound (LABEL:sumrate_bound_3_twolinks). Therefore, when
specialized to the form with both $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$ as
shown in (• ‣ -C)-(• ‣ -C), (31)-(33) have a gap of
$\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})}$ bits to their upper
bounds (9)-(LABEL:sumrate_bound_3_twolinks).

  * •

Second, when having $\mathsf{C}_{1}$ only, (31)-(33) become

$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+g_{2}+\Delta{g}_{2}+(\mathsf{C}_{1}-\xi_{1})^{+},$ (163) $\displaystyle
R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{2}+\Delta{a}_{2}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+},$ (164) $\displaystyle
R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
e_{1}+e_{2}+\Delta{e}_{2}+(\mathsf{C}_{1}-\xi_{1})^{+},$ (165)

where (163) is lower bounded by

$\displaystyle a_{1}+g_{2}+\Delta{g}_{2}+(\mathsf{C}_{1}-\xi_{1})^{+}$ (166)
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)-\alpha(\mathsf{q}_{2}),$

which is within

$\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{0})}=\alpha(\mathsf{q}_{2})+\beta(\mathsf{q}_{1})$
(167)

bits of the upper bound (12), and (164) is lower bounded by

$\displaystyle a_{2}+\Delta{a}_{2}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right)-\alpha(\mathsf{q}_{2})$
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})-\frac{1}{2}+\mathsf{C}_{1}+\xi_{1},$

which is within $\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{0})}$ bits of
the upper bound (13), and (165) can be lower bounded by

$\displaystyle e_{1}+e_{2}+\Delta{e}_{2}+(\mathsf{C}_{1}-\xi_{1})^{+}$ (169)
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}+\mathsf{INR}_{2}\right)-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\qquad\qquad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)-\alpha(\mathsf{q}_{2}),$

which is within $\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{0})}$ bits of
the upper bound (14).

  * •

Third, when having $\mathsf{C}_{2}$ only, (31)-(33) become

$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+\Delta{a}_{1}+g_{2}+(\mathsf{C}_{2}-\xi_{2})^{+},$ (170) $\displaystyle
R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{2}+g_{1}+\Delta{g}_{1}+(\mathsf{C}_{2}-\xi_{2})^{+},$ (171) $\displaystyle
R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
e_{1}+\Delta{e}_{1}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+}.$ (172)

Due to the symmetry between (170)-(172) and (163)-(165), and the symmetry
between their upper bounds, we can see that (170), (171) and (172) are within

$\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{C}_{2})}=\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})$
(173)

bits of the upper bounds (15), (16), and (17) respectively.

  * •

Fourth, when having none of $\mathsf{C}_{1}$ and $\mathsf{C}_{2}$, (31)-(33)
become

$\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
a_{1}+\Delta{a}_{1}+g_{2}+\Delta{g}_{2},$ (174) $\displaystyle R_{1}+R_{2}$
$\displaystyle\leq$ $\displaystyle a_{2}+\Delta{a}_{2}+g_{1}+\Delta{g}_{1},$
(175) $\displaystyle R_{1}+R_{2}$ $\displaystyle\leq$ $\displaystyle
e_{1}+\Delta{e}_{1}+e_{2}+\Delta{e}_{2},$ (176)

where (174) is lower bounded by

$\displaystyle a_{1}+\Delta{a}_{1}+g_{2}+\Delta{g}_{2}$ (177)
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}\right.$
$\displaystyle\qquad\quad\;\;\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)-\alpha(\mathsf{q}_{2}),$

which is within

$\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})}=\alpha(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2})$
(178)

bits of the upper bound (18). Due to symmetry, (175) is within
$\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})}$ bits of the upper bound (19)
as well. Further, (176) can be lower bounded by

$\displaystyle e_{1}+\Delta{e}_{1}+e_{2}+\Delta{e}_{2}$ (179)
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right.$
$\displaystyle\qquad\quad\left.+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\qquad\qquad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)-\alpha(\mathsf{q}_{2}),$

which is within $\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})}$ bits of the
upper bound (20). Therefore, when specialized into the form with none of
$\mathsf{C}_{1}$ and $\mathsf{C}_{2}$, (31)-(33) is within
$\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})}$ bits of their upper bounds
(18)-(20).

Overall, the gap between the achievable sum-rates (31)-(33) and the upper
bounds in (9)-(20) is upper bounded as follows:

$\delta_{R_{1}+R_{2}}=\max\left\\{\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})},\delta_{R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{0})},\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{C}_{2})},\delta_{R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})}\right\\}.$
(180)

(iii) Third, the achievable rate (34) is within constant bits of upper bounds
(21)-(26). To see this, note that (34) has $8$ different forms as follows:

$\displaystyle
a_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+},$
(181) $\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+\Delta{g}_{1}+e_{2}+\Delta{e}_{2},$ (182)
$\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+\Delta{e}_{2},$
(183) $\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+\Delta{g}_{1}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+},$
(184) $\displaystyle
a_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+\Delta{e}_{2},$
(185) $\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+},$
(186) $\displaystyle
a_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+g_{1}+\Delta{g}_{1}+e_{2}+\Delta{e}_{2},$
(187) $\displaystyle
a_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+g_{1}+\Delta{g}_{1}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+},$
(188)

where (187) is redundant compared with (183) and (188) is redundant compared
with (186) due to the fact that $\Delta{g}_{1}\geq\Delta{a}_{1}$. Therefore,
there are six active rate constraints in total. In the following, we prove
that all active achievable rates of $2R_{1}+R_{2}$ in (181)-(186) are within
constant bits of their corresponding upper bounds in (21)-(26).

  * •

First, (181) is lower bounded by

$\displaystyle
a_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}+\mathsf{INR}_{1}\right)-\frac{1}{2}+\mathsf{C}_{2}-\xi_{2},$

which is within

$\delta_{2R_{1}+R_{2}}^{(2\mathsf{C}_{1},\mathsf{C}_{2})}=2\beta(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})$
(190)

bits of the upper bound (21).

  * •

Second, (182) is lower bounded by

$\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+g_{1}+\Delta{g}_{1}+e_{2}+\Delta{e}_{2}$ (191)
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}\right.$
$\displaystyle\qquad\quad\;\;\left.+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\qquad\qquad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)-\alpha(\mathsf{q}_{2}),$

which is within

$\delta_{2R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})}=2\alpha(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2})$
(192)

bits of the upper bound (22).

  * •

Third, (183) is lower bounded by

$\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+\Delta{e}_{2}$
(193) $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\left.\qquad\qquad+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)-\alpha(\mathsf{q}_{2}),$

which is within

$\delta_{2R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{0})}=\alpha(\mathsf{q}_{1})+\alpha(\mathsf{q}_{2})+\beta(\mathsf{q}_{1})$
(194)

bits of the upper bound (23).

  * •

Fourth, (184) is lower bounded by

$\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+\Delta{g}_{1}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+}$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log\left(1+\mathsf{SNR}_{1}(1+\phi_{1}^{2}\mathsf{SNR}_{r2})+\mathsf{SNR}_{r1}\right.$
$\displaystyle\left.\qquad\quad\;\;+\mathsf{INR}_{2}+\mathsf{SNR}_{r2}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}+\mathsf{INR}_{1}\right)-\frac{1}{2}+\mathsf{C}_{2}-\xi_{2},$

which is within

$\delta_{2R_{1}+R_{2}}^{(\mathsf{0},\mathsf{C}_{2})}=2\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})$
(196)

bits of the upper bound (24).

  * •

Fifth, (185) is lower bounded by

$\displaystyle
a_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+\Delta\tilde{e}_{2}$
(197) $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}}{1+\mathsf{INR}_{1}}\right)-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}(1+\phi_{2}^{2}\mathsf{SNR}_{r1})+\mathsf{SNR}_{r2}}{1+\mathsf{INR}_{2}}\right.$
$\displaystyle\qquad\qquad\left.+\mathsf{INR}_{1}+\mathsf{SNR}_{r1}\right)-\alpha(\mathsf{q}_{2}),$

which is within

$\delta_{2R_{1}+R_{2}}^{(2\mathsf{C}_{1},\mathsf{0})}=\alpha(\mathsf{q}_{2})+2\beta(\mathsf{q}_{1})$
(198)

bits of the upper bound (25).

  * •

Sixth, (186) is lower bounded by

$\displaystyle
a_{1}+\Delta{a}_{1}+g_{1}+(\mathsf{C}_{1}-\xi_{1})^{+}+e_{2}+(\mathsf{C}_{2}-\xi_{2})^{+}$
(199) $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{1}+\mathsf{SNR}_{r1}}{1+\mathsf{INR}_{1}}\right)-\alpha(\mathsf{q}_{1})$
$\displaystyle+\frac{1}{2}\log(1+\mathsf{SNR}_{1}+\mathsf{INR}_{2})-\frac{1}{2}+\mathsf{C}_{1}-\xi_{1}$
$\displaystyle+\frac{1}{2}\log\left(1+\frac{\mathsf{SNR}_{2}}{1+\mathsf{INR}_{2}}+\mathsf{INR}_{1}\right)$
$\displaystyle-\frac{1}{2}+\mathsf{C}_{2}-\xi_{2},$

which is within

$\delta_{2R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})}=\alpha(\mathsf{q}_{1})+\beta(\mathsf{q}_{1})+\beta(\mathsf{q}_{2})$
(200)

bits of the upper bound (26).

Therefore, the gap between the achievable rate (34) and the corresponding
upper bounds (21)-(26) is bounded by the following constant

$\displaystyle\delta_{2R_{1}+R_{2}}$ $\displaystyle=$
$\displaystyle\max\left\\{\delta_{2R_{1}+R_{2}}^{(2\mathsf{C}_{1},\mathsf{C}_{2})},\delta_{2R_{1}+R_{2}}^{(\mathsf{0},\mathsf{0})},\delta_{2R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{0})},\delta_{2R_{1}+R_{2}}^{(\mathsf{0},\mathsf{C}_{2})},\right.$
(201)
$\displaystyle\left.\qquad\;\;\delta_{2R_{1}+R_{2}}^{(2\mathsf{C}_{1},\mathsf{0})},\delta_{2R_{1}+R_{2}}^{(\mathsf{C}_{1},\mathsf{C}_{2})}\right\\}.$

Due the the symmetry between (35) and (34), and the symmetry between their
corresponding upper bounds, it is easy to see that (35) is also within
constant gap to the upper bounds. The constant gap $\delta_{R_{1}+2R_{2}}$ can
be obtained by simply switching indices of $1$ and $2$ in
$\delta_{2R_{1}+R_{2}}$.

## References

  * [1] R. Etkin, D. N. C. Tse, and H. Wang, “Gaussian interference channel capacity to within one bit,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 12, pp. 5534–5562, Dec. 2008.
  * [2] T. S. Han and K. Kobayashi, “A new achievable rate region for the interference channel,” _IEEE Trans. Inf. Theory_ , vol. 27, no. 1, pp. 49–60, Jan. 1981.
  * [3] L. Zhou and W. Yu, “Gaussian Z-interference channel with a relay link: Achievability region and asymptotic sum capacity,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 4, pp. 2413–2426, Apr. 2012.
  * [4] L. Zhou and W. Yu, “Gaussian Z-Interference channel with a relay link: Achievable rate region and asymptotic sum capacity,” in _Proc. Int. Symp. Inf. Theory and Its App. (ISITA)_ , Dec. 2008, pp. 1–6.
  * [5] W. Yu and L. Zhou, “Gaussian Z-interference channel with a relay link: Type II channel and sum capacity bound,” in _Proc. Inf. Theory and App. (ITA) Workshop_ , Feb. 2009, pp. 439–446.
  * [6] I.-H. Wang and D. N. C. Tse, “Interference mitigation through limited receiver cooperation,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 5, pp. 2913–2940, May 2011.
  * [7] I.-H. Wang and D. N. C. Tse, “Interference mitigation through limited transmitter cooperation,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 5, pp. 2941–2965, May 2011.
  * [8] V. M. Prabhakaran and P. Viswanath, “Interference channels with destination cooperation,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 1, pp. 187–209, Jan. 2011.
  * [9] V. M. Prabhakaran and P. Viswanath, “Interference channels with source cooperation,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 1, pp. 156–186, Jan. 2011.
  * [10] O. Sahin and E. Erkip, “Achievable rates for the Gaussian interference relay channel,” in _Proc. Global Telecommun. Conf. (Globecom)_ , Nov. 2007, pp. 1627–1631.
  * [11] Y. Tian and A. Yener, “The Gaussian interference relay channel: Improved achievable rates and sum rate upper bounds using a potent relay,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 5, pp. 2865–2879, May 2011.
  * [12] R. Dabora, I. Marić, and A. Goldsmith, “Relay strategies for interference-forwarding,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , May 2008, pp. 46–50.
  * [13] I. Marić, R. Dabora, and A. Goldsmith, “On the capacity of the interference channel with a relay,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , Jul. 2008, pp. 554–558.
  * [14] A. Chaaban and A. Sezgin, “Achievable rates and upper bounds for the interference relay channel,” in _Conf. Record Forty-Fourth Asilomar Conf. Signals, Systems and Computers_ , Nov. 2010, pp. 267–271.
  * [15] A. Chaaban and A. Sezgin, “On the generalized degrees of freedom of the Gaussian interference relay channel,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 7, pp. 4432–4461, Jul. 2012.
  * [16] J. Lou, P. S. C. Thejaswi, J. Zhang, G. Yue, and T. Luo, “Achievable rates for a relay-aided interference channel,” in _Proc. IEEE Int. Conf. Commun. (ICC)_ , May 2010, pp. 1–5.
  * [17] O. Sahin and E. Erkip, “Achievable rates for the Gaussian interference relay channel,” in _Proc. Global Telecommun. Conf. (Globecom)_ , Nov. 2007, pp. 1627–1631.
  * [18] O. Sahin, O. Simeone, and E. Erkip, “Interference channel with an out-of-band relay,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 5, pp. 2746–2764, May 2011.
  * [19] Y. Tian and A. Yener, “Symmetric capacity of the Gaussian interference channel with an out-of-band relay to within $1.15$ bits,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 8, pp. 5151–5171, Aug. 2012.
  * [20] O. Simeone, E. Erkip, and S. Shamai, “On codebook information for interference relay channels with out-of-band relaying,” _IEEE Trans. Inf. Theory_ , vol. 57, no. 5, pp. 2880–2888, May 2011.
  * [21] O. Sahin, O. Simeone, and E. Erkip, “Gaussian interference channel aided by a relay with out-of-band reception and in-band transmission,” _IEEE Trans. Commun._ , vol. 59, no. 11, pp. 2976–2981, Nov. 2011.
  * [22] P. Razaghi and W. Yu, “Universal relaying for the interference channel,” in _Proc. Inf. Theory and App. (ITA) Workshop_ , Feb. 2010, pp. 1–6.