Symbol-Level Precoding Design for Max-Min SINR
in Multiuser MISO Broadcast Channels
Alireza Haqiqatnejad, Farbod Kayhan, and Björn Ottersten
Interdisciplinary Centre for Security, Reliability and Trust (SnT), University of Luxembourg
email: {alireza.haqiqatnejad,farbod.kayhan,bjorn.ottersten}@uni.lu

arXiv:1803.06871v1 [] 19 Mar 2018

Abstract
In this paper, we address the symbol level precoding (SLP) design problem under max-min SINR criterion in the downlink
of multiuser multiple-input single-output (MISO) channels. First, we show that the distance preserving constructive interference
regions (DPCIR) are always polyhedral angles (shifted pointed cones) for any given constellation point with unbounded decision
region. Then we prove that any signal in a given unbounded DPCIR has a norm larger than the norm of the corresponding vertex
if and only if the convex hull of the constellation contains the origin. Using these properties, we show that the power of the
noiseless received signal lying on an unbounded DPCIR is an strictly increasing function of two parameters. This allows us to
reformulate the originally non-convex SLP max-min SINR as a convex optimization problem. We discuss the loss due to our
proposed convex reformulation and provide some simulation results.
Index Terms
Distance preserving constructive interference region, max-min SINR, multiuser MISO, symbol-level precoding.

I. I NTRODUCTION
Multiuser interference (MUI) is a major performance limiting factor in multiuser systems, which reduces the maximum
reliable transmission rate of individual users. One approach to mitigate the MUI is to precompensate for its undesired effect
on the received signal through some signal processing at the transmitter [1], which is known as multiuser precoding.
The multiuser precoding problem is usually expressed as a constrained optimization problem (see [1], [2] and the
references therein). In general, the design problem aims at keeping a balance between some network-centric and usercentric objectives/requirements, depending on the network’s operator strategy. Power and sum-rate are commonly regarded
as network-centric criteria [2]. On the other hand, as a user-centric criterion, signal-to-interference-plus-noise ratio (SINR) is
an effective measure of quality-of-service (QoS) in multiuser interference channels [3]. In particular, both bit error rate (BER)
and capacity, which are two relevant criteria from a practical point of view, are closely related with maximizing SINR. Taking
into account different types of optimization criteria, some well-known formulations for the multiuser precoding problem are
power minimization with SINR constraints [4], SINR balancing [5], and (weighted) sum-rate maximization [2]. In this paper,
we mainly focus on the SINR balancing problem through ensuring max-min fairness among users.
Conventional linear multiuser precoding techniques try to design the precoder in order to mitigate the MUI. This requires
the knowledge of the instantaneous channel state information (CSI) to calculate the precoder matrix. Following the notion of
constructive interference (CI), one can turn the MUI into a useful source of signal power instead of treating it as an unwanted
distortion [6]. Accordingly, in addition to CSI, the instantaneous data information (DI) of all users are used to design the
precoder, which leads to introducing symbol-level precoding (SLP) [7]. When compared to conventional schemes, it has been
shown that significant gains can be achieved, but at the cost of higher transmitter complexity [6]. In SLP scheme, one may
also form a virtual multicast formulation to directly find the optimal transmit vector, as proposed in [7], instead of finding the
precoder matrix.
The SINR balancing problem in multiuser multiple-input single-output (MISO) channels has been extensively investigated
for conventional precoding techniques, and addressed in both multicast (single data stream) and broadcast (independent data
streams) downlink scenarios. The problem is not convex in general and hence, alternate optimization approaches have been
proposed. The authors in [3] prove that the max-min SINR problem for downlink multicasting is NP-hard; however, it can
be solved approximately through semidefinite relaxation. For downlink broadcast channels, it is shown in [5] that the power
minimization and the max-min SINR are inverse problems. Using this property, the SINR optimization problem can be solved
through iteratively solving the power optimization. Furthermore, direct solutions for max-min SINR are provided in [5] via
conic optimization, where the problem is formulated as a quasiconvex standard generalized eigenvalue program (GEVP). Using
the concept of uplink-downlink duality, in [4] it is verified that the global optimum of max-min SINR is equivalently obtained
from solving a dual uplink problem, which has an easier-to-handle analytical structure.
Concerning SLP design in multiuser downlink channels, the optimization constraints push each user’s (noiseless) received
signal to a predefined region, called constructive interference region (CIR), enhancing (or guaranteeing a certain level of) the
detection accuracy. This causes the constraints to depend on both the constellation set and the decision regions. In [7], the
non-convex SLP max-min SINR problem is solved using its relation to the power minimization via a bisection search. The

proposed method is restricted to PSK constellations and has high computational complexity. This problem is also studied in
[6] and an alternate convex formulation is provided for PSK constellations. However, there is no general solution method or
convex formulation for the SLP max-min SINR problem being valid for generic constellations of any order and shape.
In this paper, our goal is to find alternate convex formulations for the originally non-convex SLP max-min SINR problem,
based on the definition of distance preserving constructive interference regions (DPCIR) [8]. To obtain such reformulation, we
first show that any DPCIR associated with a boundary constellation point is always a polyhedral angle, and hence unbounded.
Then, we prove that any signal in a given unbounded DPCIR has a norm larger than the corresponding vertex under the
necessary and sufficient condition that the constellation contains the origin in its convex hull. Based on these two results, we
derive two alternate convex formulations for the SLP max-min SINR. This is done by noticing that the noise-free received
signal at each user’s receiver is an increasing function of two parameters.
The remainder of this paper is organized as follows. In Section II, we describe our system model. In Section III, we overview
the DPCIRs and their properties. We discuss the SLP max-min SINR in Section IV and reformulate it as alternate convex
problems. In Section V, we provide some simulation results. Finally, we conclude the paper in Section VI.
Notations: We use uppercase and lowercase bold-faced letters to denote matrices and vectors, respectively, and lowercase
normal letters to denote scalars. For matrices and vectors, [·]T denotes the transpose operator. For vectors, k · k represents the
l2 norm, and  (or ≻) denotes componentwise inequality. ℜ{·} and ℑ{·} denote the respectively real-part and imaginary-part
operators. For any set A, |A| denotes the cardinality of A.
II. S YSTEM M ODEL
We consider the downlink of a multiuser MISO broadcast channel, where a base station (BS) transmits independent data
streams to K users. The BS is equipped with N transmit antennas while each user has a single receive antenna. A complex
channel vector is assumed between the BS’s transmit antennas and the k-th user, which is denoted by h k ∈ C1×N . It is further
assumed that perfect channel knowledge is available to the BS.
At a given symbol time, K independent symbols are to be sent to K users (throughout the paper, we drop the symbol’s
time index to simplify the notation). We collect these symbols in users’ symbol vector s = [s1 , . . . , sK ]T ∈ CK×1 with
sk denoting the symbol intended for the k-th user. Each symbol sk is drawn from a finite equiprobable two-dimensional
constellation set. Without loss of generality, we assume an M -ary constellation set χ = {xi |xi ∈ C}M
i=1 with unit average
power for all K users. The user’s symbol vector s is mapped onto N transmit antennas. This is done by a symbol-level
precoder yielding the BS’s transmit vector u ∈ CN ×1 . The received signal at the k-th user’s receiver is then rk = h ku + wk ,
where wk ∼ CN (0, σk2 ) is the complex additive white Gaussian noise at the k-th receiver. Again without loss of generality,
we assume identical noise distributions across the receivers, i.e., σk = σ, k = 1, ..., K. From the received scalar rk , the user
k may apply the maximum-likelihood (ML) decision rule to detect its own symbol sk .
III. D ISTANCE P RESERVING C ONSTRUCTIVE I NTERFERENCE R EGIONS
In this section, we provide an overview of DPCIRs and their properties which will be useful in formulating the SLP design
problem. Hereafter, we denote each complex-valued constellation point by its equivalent real-valued vector notation, hence the
xi |x
x i ∈ R2 } M
set of points in χ is denoted by {x
i=1 .
The DPCIRs can be described based on the hyperplane representation of ML decision regions [8]. For the equiprobable
constellation set χ, the ML decision rule corresponds to the Voronoi regions of χ which are bounded by hyperplanes. For a
given constellation point x i and one of its neighboring points x j , the hyperplane separating the Voronoi regions of x i and
x | x ∈ R2 , a Ti,j x = bi,j }, where a i,j = x i − x j (or any non-zero scalar multiplication of x i − x j ), and
x j is given by {x
T x
bi,j = a i,j (x i + x j )/2. This hyperplane indicates a decision boundary (Voronoi edge) between x i and x j , which splits R2
x | x ∈ R2 , a Ti,j x ≥ bi,j } contains the decision region of x i , where
plane into two halfspaces. The closed halfspace Hi,j = {x
a i,j is the inward normal and bi,j determines the offset from the origin. The Voronoi region of x i is then given by intersecting
all such halfspaces, i.e.,
\
Di,ML =
Hi,j
x j ∈Si
(1)

2 T
xj ∈ Si ,
= x | x ∈ R , a i,j x ≥ bi,j , ∀x
where Si denotes the set of neighboring points of x i with |Si | = Mi . Each Voronoi region can be either an unbounded or
bounded polyhedron, depending on the relative location of x i in χ. It can be easily verified that all types of polyhedra (i.e.,
bounded or unbounded), and hence the Voronoi regions, are convex sets [9]. The Voronoi region (1) can be expressed in a
more compact form as

(2)
Di,ML = x | x ∈ R2 , A ix  b i ,
where A i ∈ RMi ×2 and b i ∈ RMi contain a Ti,j and bi,j , respectively, for all x j ∈ Si .

Fig. 1. The AWGN-optimized 8-ary constellation and one of its boundary points x i with unbounded Voronoi region. The associated DPCIR is a polyhedral
angle with two infinite edges starting from x i .


x | x ∈ R2 , a Ti,j x = bi,j }, the set of points x | x ∈ R2 , a Ti,j x = bi,j + ci,j , ci,j ∈ R+ represents a
For any hyperplane {x
ai,j k in the direction of a i,j . Let di,j denote the distance between x i
parallel hyperplane with the orthogonal distance ci,j /ka
and x j . Since the DPCIRs are defined so as to not decrease the original distances between the constellation points, the distance
preserving margin is equal to di,j /2. Therefore, the DPCIR associated with x i can be described as

(3)
Di,DP = x | x ∈ R2 , A ix  b i + c i,DP ,
i
ai,j k/2 for all x j ∈ Si . Similar to Di,ML , Di,DP is the intersection of a
where c i,DP ∈ RM
+ is the vector containing di,j ka
number of closed halfspaces and thus is a polyhedron. Furthermore, the bounding hyperplanes of Di,DP are parallel to their
corresponding Voronoi edges. It is straightforward to show that the following properties hold for DPCIRs:

Property 1. For any x i ∈ χ and x ∈ Di,DP , we have
i. Di,DP ⊆ Di,ML .
x − y k ≥ kx
xi − x j k = di,j , ∀x
x j ∈ χ, y ∈ Dj,DP .
ii. kx
x − x j k ≥ kx
xi − x j k, ∀x
xj ∈ χ, where equality holds only when x = x i .
iii. kx
From the constellation set χ, one can easily derive its convex hull conv
convχ, i.e., the smallest convex set containing χ (see
Fig. 1). The set of points belonging to the boundary of conv
convχ is denoted by bd
bdχ, and the set of interior points of conv
convχ,
bd
i.e., conv
convχ\bd
bdχ, is shown by int
intχ. It follows from (3) that if Di,ML is bounded, then Di,DP = x i . On the other hand, for
an unbounded Di,ML , the associated Di,DP is an unbounded polyhedron (more specifically, a polyhedral angle as depicted in
Fig. 1) which is uniquely characterized using the two following lemmas.
Lemma 1. A point x i ∈ χ lies on the boundary of (or is a vertex of) conv
convχ iff its Voronoi region Di,ML is unbounded [10,
Lemma 2.2].
Lemma 2. For every x i ∈ χ with unbounded Di,ML , Di,DP is a polyhedral angle with a vertex at x i , and each of its edges
is perpendicular to one of the two line segments connecting x i to its two neighboring points on bd
bdχ.
. See Appendix A-A.
Lemma 2 implicitly states that neither changing the location of any constellation point x j ∈ int
intχ nor adding a new
constellation point on bd
bdχ does not affect Di,DP for any x i ∈ bd
bdχ, as they both keep the direction of a i,j unchanged for all
x j ∈ Si ∩ bd
bdχ. This leads to the following two lemmas.
xk ≥ kx
xi k, ∀x
x ∈ Di,DP iff conv
Lemma 3. For any constellation point x i ∈ χ, we have kx
convχ contains the origin. Equality is
achieved only when x = x i .

. See Appendix A-B.
Lemma 4. If 0 ∈
/ conv
convχ, there exists at least one constellation point x l ∈ χ for which for any x ∈ Dl,DP , 0 ∈
/ conv χ̃x l ,xx ,
x}.
where χ̃x l ,xx = χ ∪ {x
S
x}, let define Ci =
conv χ̃x i ,xx . Having
. If 0 ∈
/ conv
convχ, for any x i ∈ χ and any x ∈ Di,DP with χ̃x i ,xx = χ ∪ {x
x∈Di,DP
T
x i ∈ χ, then 0 ∈ conv
conv
convχ ⊆ conv χ̃x i ,xx , it follows from the definition of convex hull that conv
convχ =
Ci . If 0 ∈ Ci , ∀x
convχ
x i ∈χ

which contradicts our assumption. Hence there must exist at least one constellation point, say x l , for which Cl and therefore
x ∈ Dl,DP contains the origin, as required.
none of conv χ̃x l ,xx , ∀x
To proceed, it is more convenient to express the linear inequalities of (3) by an equivalent set of linear equations as
o
n
i
x ∈ R2, A ix = b i + c i,DP + ∆ i , ∆ i ∈ RM
.
Di,DP = x |x
+

(4)

The linear equations in (4) indicate that any x ∈ Di,DP can be specified as the intersection point of Mi hyperplanes, each
of which is parallel to a boundary hyperplane of Di,DP but has a different offset due to the term ∆ i . Finally, we state the
following theorem which is the main result of this section.
x) = kx
xk over its domain Di,DP
Theorem 1. For any constellation point x i ∈ χ with Di,DP as expressed in (4), function f (x
is a strictly monotonic increasing function of the elements of ∆ i iff conv
convχ contains the origin.
. See Appendix A-C
IV. S YMBOL - LEVEL P RECODING D ESIGN P ROBLEM
A symbol-level precoder designs the vector to be transmitted at each symbol time via solving a constrained optimization
problem. The solution of the SLP problem, i.e., the transmit vector u , is in general a function of instantaneous DI and CSI
as well as the set of given system constraints or user-specific requirements. When power is a strict system restriction on the
downlink transmission, fairness might be a relevant design criterion [5]. In particular, we are interested in the SLP max-min
SINR problem subject to a total power constraint Pmax which aims at maximizing the worst SINR among all users. Assuming
the CIRs to be distance preserving, the problem is not convex in its original form. In this section, we derive two alternate
convex formulations for this problem. This is done by noticing that the noise-free received signal at each user is a increasing
function of two parameters.
x i }M
For any user k = 1, ..., K, the symbol sk corresponds to one of the points {x
i=1 in χ. In the following, we denote by ik the
T
index of the constellation point corresponding to sk , i.e., [ℜ{sk }, ℑ{sk }] = x ik , where ik ∈ {1, ..., M }. Furthermore,
vectors

u = [ℜ{u
u}, ℑ{u
u}]T ∈ R2N ×1 and H k = [ℜ{h
hk }, ℑ{h
hk }]T , [−ℑ{h
hk }, ℜ{h
hk }]T ∈ R2×2N , k =
u and h k are rearranged as ũ
u represents the noise-free received signal at the k-th user’s receiver.
1, ..., K, respectively, such that H kũ
The symbol-level SINR for user k is proportional to the instantaneous received power by the k-th receiver at each symbol
time (recall that the same noise variance σ 2 is assumed for all K users). Accordingly, the DPCIR-based SLP max-min SINR
problem can be formulated as
o
n
u
uT H Tk H kũ
maximize min ũ
u,{∆
∆ ik }K
ũ
k=1

k

k∈K

u = σ (bbik + c ik + ∆ ik ), k = 1, ..., K,
subject to A ik H k ũ
∆ ik  0k , k = 1, ..., K,

(5)

uT ũ
u ≤ Pmax ,
ũ
bd
where the index set K = {k|k = 1, ..., K, x ik ∈bd
bdχ} refers to those users with a symbol in the boundary of their corresponding
constellation, and 0k denotes an all-zeros vector of appropriate dimension. By introducing a slack variable t, one can recast (5)
as
maximize t
u,{∆
∆ ik }K
ũ
k=1

u = σ (bbik + c ik + ∆ ik ), k = 1, ..., K,
subject to A ik H k ũ
∆ ik  0k , k = 1, ..., K,

(6)

u ≥ t, k ∈ K,
uT H Tk H kũ
ũ
uT ũ
u ≤ Pmax ,
ũ
which is not convex due to the third set of constraints. As a consequence of Lemma 1 and Lemma 2, and with respect to (4),
any point in Dik ,DP can be uniquely specified by ∆ ik = [δik ,1 , δik ,2 ]T ∈ R2+ for all x ik ∈ bd
bdχ. It follows from Theorem 1 that
T
T
2
uk is strictly increasing in each element of ∆ ik , ∀k ∈ K, i.e., assuming either δik ,1 or δik ,2 to be fixed,
u = kH
H kũ
u H k H kũ
ũ

u is a monotonically increasing function of the other. This suggests that if the optimal value of one of the elements,
u T H Tk H kũ
ũ
e.g., δik ,1 , is given for all k ∈ K, then the optimization (6) is equivalent to the convex problem
maximize t
u ,δik ,2 :k∈K
ũ

u = σ (bbik + c ik + ∆ ik ), k = 1, ..., K,
subject to A ik H kũ
δik ,2 ≥ t, k ∈ K, ∆ ik = 0k , k ∈
/ K,

(7)

uT ũ
u ≤ Pmax ,
ũ
u in (6). In fact, achieving the optimum of (6) requires an exhaustive
uT H Tk H kũ
where the parameter δik ,2 is substituted for ũ
search over all possible (non-negative) values of δik ,1 , ∀k ∈ K and solving (7) for each choice of δik ,1 . The optimal solution is
then obtained by picking δik ,1 for which the objective function is maximum among all other choices. Practically speaking, due
to the power limitation induced by Pmax , one can bound and discretize the search interval to choose δik ,1 , ∀k ∈ K from a finite
set, which of course leads to a sub-optimal solution. The gap to the optimal solution depends on whether the search interval
includes the optimal value, and also on the step size of discretization. In general, the smaller the step size is, the higher the
computational complexity will be.
Another alternate, but not equivalent, convex formulation for problem (6) is to jointly optimize δik ,1 and δik ,2 for all k ∈ K,
i.e.,
maximize

u,{∆
∆ ik }K
ũ
k=1

t

u = σ (bbik + c ik + ∆ ik ), k = 1, ..., K,
subject to A ik H k ũ
∆ ik  t 1k , k ∈ K, ∆ ik = 0k , k ∈
/ K,

(8)

uT ũ
u ≤ Pmax .
ũ
where 1k is an all-ones vector. The optimal solution of this problem can be regarded as a lower bound on the optimum of SLP
max-min SINR. It should be noted that for PSK constellations, problem (8) is equivalent to the alternate convex formulation
for the SLP SINR balancing provided in [6].
V. S IMULATION R ESULTS
In this section, we provide the simulation results to evaluate the performance of the two proposed alternate convex formulations
for the SLP max-min SINR problem. In the simulations, we have considered a downlink multiuser scenario with N = K = 4
and σ = 1, where the BS employs the AWGN-optimized 8-ary constellation for all users. For any user k, the complex channel
vector h k follows an i.i.d. complex Gaussian distribution with zero-mean and unit variance. The results are averaged over 500
symbol slots.
Figure 2 shows the optimized minimum SINR across the users obtained from the joint optimization problem (8) and from
an exhaustive search over interval [0,2.5] with step size 0.5 for all possible combinations of δik ,1 , ∀k ∈ K. For the exhaustive
search, the number of convex problems to be solved in every symbol time is of order 5K . As it can be observed, the loss due
to the joint, but convex, optimization is not significant (around 1-1.5 dBW). This loss is, however, a consequence of highly
reducing the computational complexity to solving only one convex problem in each symbol time.
VI. C ONCLUSION
In this paper, we addressed the problem of SLP SINR balancing with max-min fairness criterion in a downlink multiuser
MISO channel. The original formulation of this problem is known to be non-convex. For the so-called DPCIRs, we proposed
two alternate convex formulations. Both formulations are based on the observation that the noise-free received signal power is
an strictly increasing function of two parameters for any given unbounded DPCIR, under the necessary and sufficient condition
that the convex hull of the constellation contains the origin. The first formulation is solvable via an exhaustive search and even
though it provides the optimal solution, it is computationally expensive to be implemented in a realistic scenario. The second
formulation, though sub-optimal, reduces the problem to a convex optimization.
ACKNOWLEDGMENT
The authors are supported by the Luxembourg National Research Fund under CORE Junior project: C16/IS/11332341
Enhanced Signal Space opTImization for satellite comMunication Systems (ESSTIMS).

12

Worst user SINR (dBW)

11.5
11
10.5
10
9.5
9
Joint optimization
Exhaustive search

8.5
8
14

14.5

15

15.5

16

Pmax (dBW)
Fig. 2. The worst user SINR versus total power constraint.

A PPENDIX A
A. Proof of Lemma 2
The intersection of finitely many closed halfspaces is an unbounded polyhedron if and only if the outward normals to the
associated boundary hyperplanes lie on a single closed halfspace [11, p. 20, Theorem 4]. Accordingly, for any x i ∈ χ with
ai,j , ∀x
xj ∈ Si lie on a single halfspace. Since Di,DP has the same set of
unbounded Di,ML , the outward normal vectors −a
ai,j , ∀x
xj ∈ Si , it is also unbounded. An unbounded polyhedron is uniquely determined from its
outward normal vectors −a
vertices and the directions of its infinite edges [11, p. 31, Theorem 4]. It is straightforward to check that x i is the unique
solution of A ix = b i + c i,DP , i.e., all the hyperplanes have a common intersection point x i . Therefore, Di,DP , which is given by
the solution set of A ix  b i + c i,DP , has a single vertex at x i and two infinite edges, i.e., a polyhedral angle. In addition, since
any two neighboring points share a common Voronoi edge, the two infinite edges of Di,DP correspond to the two neighboring
bd
points of x i on bd
bdχ (i.e., Si ∩bd
bdχ) with unbounded Voronoi regions. Each infinite edge of Di,DP is then parallel to a hyperplane
with normal vector a i,j = x i − x j , where x j ∈ Si ∩ bd
bdχ; therefore it is perpendicular to x i − x j . This completes the proof.
B. Proof of Lemma 3
Sufficiency: Having 0 ∈ conv
convχ, let further assume that 0 ∈ χ. This assumption, as mentioned earlier, does not have any
impact on Di,DP for any x i ∈ bd
bdχ, regardless of whether 0 ∈ bd
bdχ or 0 ∈ int
intχ. By substituting x j = 0 in Property 1 (iii), for
xk ≥ kx
xi k, ∀x
x ∈ Di,DP . This completes the proof of sufficiency.
all x i ∈ χ we have kx
We use the following well-known property of convex sets to prove the necessity.
Property 2. v o is the minimum distance vector from the origin to the convex set V iff for any vector v ∈ V we have v To v ≥ v To v o ,
with equality for v lying on the hyperplane orthogonal to v o [12, p. 69, Theorem 1].
Necessity: By contradiction, if 0 ∈
/ conv
convχ, let assume a new constellation set χ̃ having all the points of χ including
the origin, i.e., χ̃ = χ ∪ {0}, hence conv
convχ ⊂ conv χ̃. Clearly, 0 ∈ bd χ̃ and according to Lemma 2, there always exist
exactly two constellation points on bd χ̃ that 0 contributes to their DPCIRs. Suppose x l be one of these points with Dl,DP
and D̃l,DP denoting its
 associated DPCIR relative to χ and χ̃, repectively. We denote by S̃l the set of neighboring points of
x l in χ̃. Let Hl,o = x | x ∈ R2 , x Tl x ≥ x Tl x l be the distance preserving halfspace from0 to x l . Since 0 ∈ S̃l , we have
D̃l,DP = Hl,o ∩ Dl,DP 6= Dl,DP , i.e., the halfspace Hl,o does not contain Dl,DP . Hence, x | x ∈ R2 , x Tl x = x Tl x l is not
a supporting hyperplane for Dl,DP at x l [9, p. 51]. This implies that there exist some x ∈ Dl,DP for which x Tl x < x Tl x l .
According to Property 2 (which gives a necessary and sufficient condition), x l is not the minimum distance vector from the
xk ≥ kx
xl k does not hold for some x ∈ Dl,DP which contradicts kx
xk ≥ kx
xl k, ∀x
x ∈ Dl,DP .
origin in Dl,DP . Consequently, kx

C. Proof of Theorem 1
Sufficiency: Suppose 0 ∈ conv
convχ. Assuming a constellation point x i ∈ χ and its DPCIR Di,DP , let y 1 and y 2 be two
i
points in Di,DP such that A iy 1 = b i + c i,DP + ∆ i,1 and A iy 2 = b i + c i,DP + ∆ i,2 with ∆ i,1 , ∆ i,2 ∈ RM
+ and ∆ i,1 ≺ ∆ i,2 .
Let consider a new constellation χ̃= χ ∪ {yy 1 }. It is clear that conv
convχ ⊆ conv χ̃, and therefore 0 ∈ conv χ̃. The DPCIR of
i
¯ = ∆ i,2 − ∆ i,1 , then
. Let ∆
y 1 can be described as Dy 1 ,DP = x | x ∈ R2 , A ix = b i + c i,DP + ∆ i,1 + ∆ 1 , ∆ 1 ∈ RM
+
Mi
¯
¯
A iy 2 = b i + c i,DP + ∆ i,1 + ∆ , ∆ ∈ R++ , which means that y 2 ∈ Dy 1 ,DP . As a consequence, from Lemma 3, we have
kyy 1 k < kyy 2 k and the proof of sufficiency is complete.
Necessity: By contradiction, suppose 0 ∈
/ conv
convχ. Then, based on Lemma 4, there exists a constellation point x l for which
l
x ∈ Dl,DP . Let y1 ∈ Dl,DP , then A ly 1 = b l + c l,DP + ∆ l,1 with ∆ l,1 ∈ RM
0∈
/ conv χ̃x l ,xx , ∀x
+ . The DPCIR associated with
Ml
2
/ conv χ̃x l ,yy 1 , it follows
y 1 can be expressed as Dy 1 ,DP = x | x ∈ R , A lx = b l + c l,DP + ∆ l,1 + ∆ 1 , ∆ 1 ∈ R+ . Since 0 ∈
¯ ,∆
¯ ∈ RMl , for which
from Lemma 3 and Property 2 that there exists y 2 ∈ Dy 1 ,DP such that A ly 2 = b l + c l,DP + ∆ l,1 + ∆
++
¯ = ∆ l,2 yields ∆ l,2 ≻ ∆ l,1 which is a contradiction. This completes the proof.
kyy 2 k < kyy 1 k. But ∆ l,1 + ∆
R EFERENCES
[1] E. Björnson, M. Bengtsson, and B. Ottersten, “Optimal multiuser transmit beamforming: A difficult problem with a simple solution structure,” IEEE
Signal Process. Mag., vol. 31, no. 4, pp. 142–148, Jul. 2014.
[2] Y. F. Liu, Y. H. Dai, and Z. Q. Luo, “Coordinated beamforming for MISO interference channel: Complexity analysis and efficient algorithms,” IEEE
Trans. Signal Process., vol. 59, no. 3, pp. 1142–1157, Mar. 2011.
[3] N. D. Sidiropoulos, T. N. Davidson, and Z.-Q. Luo, “Transmit beamforming for physical-layer multicasting,” IEEE Trans. Signal Process., vol. 54, no. 6,
pp. 2239–2251, Jun. 2006.
[4] M. Schubert and H. Boche, “Solution of the multiuser downlink beamforming problem with individual SINR constraints,” IEEE Trans. Veh. Technol.,
vol. 53, no. 1, pp. 18–28, Jan. 2004.
[5] A. Wiesel, Y. C. Eldar, and S. Shamai, “Linear precoding via conic optimization for fixed MIMO receivers,” IEEE Trans. Signal Process., vol. 54, no. 1,
pp. 161–176, Jan. 2006.
[6] C. Masouros and G. Zheng, “Exploiting known interference as green signal power for downlink beamforming optimization,” IEEE Trans. Signal Process.,
vol. 63, no. 14, pp. 3628–3640, Jul. 2015.
[7] M. Alodeh, S. Chatzinotas, and B. Ottersten, “Constructive multiuser interference in symbol level precoding for the MISO downlink channel,” IEEE
Trans. Signal Process., vol. 63, no. 9, pp. 2239–2252, May 2015.
[8] A. Haqiqatnejad, F. Kayhan, and B. Ottersten, “Constructive interference for generic constellations,” IEEE Signal Process. Lett., In Press.
[9] S. Boyd and L. Vandenberghe, Convex Optimization. Cambridge Univ. Press, 2004.
[10] F. Aurenhammer and R. Klein, Handbook of computational geometry, 2000, ch. Voronoi diagrams, pp. 201–290.
[11] A. D. Alexandrov, Convex Polyhedra. Springer Science & Business Media, 2005.
[12] D. G. Luenberger, Optimization by Vector Space Methods. New York: Wiley, 1988.

