# Approximation Algorithms For The Dispersion Problems in a Metric Space

Pawan K. Mishra Department of Computer Science and Engineering, Indian
Institute of Technology Guwahati  Gautam K. Das Department of Mathematics,
Indian Institute of Technology Guwahati

###### Abstract

In this article, we consider the $c$-dispersion problem in a metric space
$(X,d)$. Let $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ be a set of $n$ points in a
metric space $(X,d)$. For each point $p\in P$ and $S\subseteq P$, we define
$cost_{c}(p,S)$ as the sum of distances from $p$ to the nearest $c$ points in
$S\setminus\\{p\\}$, where $c\geq 1$ is a fixed integer. We define
$cost_{c}(S)=\min_{p\in S}\\{cost_{c}(p,S)\\}$ for $S\subseteq P$. In the
$c$-dispersion problem, a set $P$ of $n$ points in a metric space $(X,d)$ and
a positive integer $k\in[c+1,n]$ are given. The objective is to find a subset
$S\subseteq P$ of size $k$ such that $cost_{c}(S)$ is maximized.

We propose a simple polynomial time greedy algorithm that produces a
$2c$-factor approximation result for the $c$-dispersion problem in a metric
space. The best known result for the $c$-dispersion problem in the Euclidean
metric space $(X,d)$ is $2c^{2}$, where $P\subseteq\mathbb{R}^{2}$ and the
distance function is Euclidean distance [ Amano, K. and Nakano, S. I., Away
from Rivals, CCCG, pp.68-71, 2018 ]. We also prove that the $c$-dispersion
problem in a metric space is $W[1]$-hard.

##  1 Introduction

In facility location problem(FLP), we are given a set of $n$ locations on
which some desired facilities to be placed and a positive integer $k$. The
goal is to place facilities on $k$ locations out of $n$ given locations such
that specific objective is satisfied. Here, specific objective depends on the
nature of the problem. Suppose that the objective is to place $k$ facilities
on $k$ locations, such that the closeness of chosen locations are undesirable.
By closeness, we mean distance between a pair of facilities. We refer this FLP
as a _dispersion problem_. More specifically in the dispersion problem, we
wish to minimize the interference between the placed facilities. One of the
most studied dispersion problems is the _max-min dispersion problem_.

In the _max-min dispersion problem_ , we are given a set
$P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ of $n$ locations, the non-negative distance
$d(p,q)$ between each pair of locations $p,q\in P$, and a positive integer $k$
($k\leq n$). Here, $k$ refers to the number of facilities to be opened and
distances are assumed to be symmetric. The objective is to find a $k$ size
subset $S\subseteq P$ of locations such that $cost(S)=\min\\{d(p,q)\mid p,q\in
S\\}$ is maximized. This problem is known as $1$-dispersion problem in the
literature.

With reference to above mentioned problem, we extend the concept of closeness
of a point $p_{i}\in S$ from one closest neighbor to given some specified
number of closest neighbor. Therefore, to preserve this notion of closeness of
a point $p_{i}$, we need to add distances between point $p_{i}$ and its
specified number of nearest neighbors. We refer to such problem as
$c$-dispersion problem. Now, we define $c$-dispersion problem in a metric
space $(X,d)$ as follows:

_c-dispersion problem:_ _Let $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ be a set of
$n$ points in a metric space $(X,d)$. For each point $p\in P$ and $S\subseteq
P$, we define $cost_{c}(p,S)$ as the sum of distances from $p$ to the first c
nearest points in $S\setminus\\{p\\}$. We also define $cost_{c}(S)=\min_{p\in
S}\\{cost_{c}(p,S)\\}$ for each $S\subseteq P$. In the $c$-dispersion problem,
a set $P$ of $n$ points in a metric space $(X,d)$ and a positive integer
$k\in[c+1,n]$ are given. The objective is to find a subset $S\subseteq P$ of
size $k$ such that $cost_{c}(S)$ is maximized. _

In the real world, the dispersion problem has a huge number of applications.
The possibility of opening chain stores in a community has piqued our interest
in the dispersion problem. We need to open stores that are far apart from each
other to eliminate/prevent self-competition among the stores. Installing
dangerous facilities, such as nuclear power plants and oil tanks, is another
condition in which dispersion is a concern. These facilities must be dispersed
to the greatest extent possible, so that an accident at one site does not
affect others. The dispersion problem is often used in information retrieval
when we try to find a small subset of data with some desired variety from a
large data set so that the small subset can be used as a valid sample to
overview the large data set.

##  2 Related Work

In 1977, Shier [17] studied the two variants of the facility location problems
on a tree network, namely the $k$-center problem and the max-min dispersion
problem. Sheir considered the continuum set of points on the rectifiable edges
of a tree as a possible set of locations and showed that the max-min
dispersion problem and $(k-1)$-center problem are dual. Sheir also established
an equivalence between the max-min dispersion problem and $(k-1)$-center
problem. In 1981, Chandrasekaran and Daughety [8] studied the max-min
dispersion problem on a tree network and proposed a polynomial time algorithm.
In 1982, Chandrasekaran and Tamir [9] also studied the max-min dispersion
problem and k-center problem on a tree network. They showed that if the set of
locations is a finite subset of the continuum set of points on the rectifiable
edges, then there exists an equivalence between the max-min dispersion problem
and $(k-1)$-center problem on a tree network. So, using $k$-center algorithm
on a tree (proposed in [12]), a linear time algorithm for the max-min
dispersion problem on a tree can be devised. In [10], Erkut proved that the
max-min dispersion problem is NP-hard even if the distance function satisfies
triangular inequality. White [21] studied the max-min dispersion problem and
proposed a $3$-factor approximation result. In 1991, Tamir [18] studied the
max-min dispersion problem on a graph, where continuum set of points on the
rectifiable edges are considered as locations. Tamir showed that for a
continuum set of locations on a graph, the max-min dispersion problem can not
be approximated within a factor of $3/2$ unless P=NP. In [18], a heuristic is
proposed that produces a $2$-factor approximation result for the max-min
dispersion problem on a graph. Later in 1994, Ravi et al. [16] studied the
max-min dispersion problem on a complete graph, where each edge is associated
with a non-negative weight (distance). They independently analyzed the same
heuristic proposed in [18] (for the max-min dispersion problem on a complete
graph), and showed that the same heuristic produces a $2$-approximation result
for the complete graph. Furthermore, they also demonstrated that unless P=NP,
the max-min dispersion problem on complete graph cannot be approximated within
a factor of $2$ even if the distance function satisfies the triangular
inequality. In 1991, Megiddo and Tamir [15] designed an $O(k^{2}\log^{2}n)$
algorithm for the $k$-center problem on a line when points are sorted in an
order. Note that the same algorithm can be adapted to solve max-min dispersion
problem on a line (points are not necessarily ordered) in polynomial time. In
2007, Bhattacharya and Shi [5] proposed a linear time algorithm for the
$k$-center problem on a line, where points are not necessarily ordered. It is
to be noted that this algorithm can be adapted to solve max-min dispersion
problem on a line (points are not necessarily ordered) in polynomial time. In
the geometric settings, the max-min dispersion problem was first introduced by
Wang and Kuo [20]. They consider the problem in a $d$-dimensional space with
Euclidean distance function between two points. They proposed a dynamic
programming algorithm that solves the problem in $O(kn)$ time for $d=1$. They
also proved that for $d=2$, the problem is NP-hard. Recently, in [1], the
exact algorithm for the max-min dispersion problem was shown by establishing a
relationship with the maximum independent set problem. They proposed an
$O(n^{wk/3}\log n)$ time algorithm, where $w<2.373$. In [1], Akagi et al. also
studied two special cases of the max-min dispersion problem where set of
points (i) lies on a line, and (ii) lies on a circle. They proposed a
polynomial time exact algorithm for both the cases.

The _max-sum $k$-dispersion problem_ is another popular variant of the
dispersion problem. Here, the objective is to maximize the sum of distances
between $k$ facilities. Tamir [18] shown that the problem on a line has a
trivial solution in $O(n)$ time. He also proved that the problem is solvable
in $O(kn)$ time if the points are on a tree. Later, Ravi et al. [16] also
studied the problem on a line independently and gave a $O(\max(kn,n\log n))$
time algorithm. They also proposed a $4$-factor approximation algorithm if the
distance function satisfies triangular inequality. In [16], they also proposed
a $(1.571+\epsilon)$-factor approximation algorithm for $2$-dimensional
Euclidean space, where $\epsilon>0$. In [6] and [13], the approximation factor
of $4$ was improved to $2$. One can see [4, 7, 14] for other variations of the
dispersion problems.

In comparison with the max-min dispersion ($1$-dispersion) problem, a handful
amount of research has been done in $c$-dispersion problem in a metric space
$(X,d)$. Recently, in 2018, Amano and Nakano [2] proposed a greedy algorithm
for the Euclidean $2$-dispersion problem in $\mathbb{R}^{2}$, where the
distance function between two points is the Euclidean distance. They have
shown that the proposed greedy algorithm produces an $8$-factor approximation
result for the Euclidean $2$-dispersion problem in $\mathbb{R}^{2}$. In 2020,
[3] they analyzed the same greedy algorithm proposed in [2], and shown that
the greedy algorithm produces a $4\sqrt{3}(\approx 6.92)$-factor approximation
result for the Euclidean $2$-dispersion problem. In [2], they also proposed a
$2c^{2}$ approximation result for the Euclidean $c$-dispersion problem in
$\mathbb{R}^{2}$.

###  2.1 Our Contribution

In this article, we consider the $c$-dispersion problem in a metric space and
propose a simple polynomial time $2c$-factor approximation algorithm for a
fixed $c$. We also proved that the $c$-dispersion problem in a metric space is
$W[1]$-hard.

###  2.2 Organization of the Paper

The remainder of the paper is organized as follows. In Section 3, we propose a
$2c$-factor approximation algorithm for the $c$-dispersion problem in a metric
space. In Section 4, we prove that the $c$-dispersion problem in a metric
space is $W[1]$-hard. We conclude the paper in Section 5.

##  3 $2c$-Factor Approximation Algorithm for the $c$-Dispersion Problem in
Metric Space

In this section, we propose a greedy algorithm for the $c$-dispersion problem
in a metric space $(X,d)$. We will show that this algorithm guarantees
$2c$-factor approximation result for the $c$-dispersion problem in a metric
space. Now, we discuss the greedy algorithm as follows. Let $I=(P,k)$ be an
arbitrary instance of the $c$-dispersion problem in a metric space $(X,d)$,
where $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ is the set of $n$ points and
$k\in[c+1,n]$ is a positive integer. It is an iterative algorithm. Initially,
we choose a subset $S_{c+1}\subseteq S$ of size $c+1$ such that
$cost_{c}(S_{c+1})$ is maximized. Next, we add one point $p\in P$ into
$S_{c+1}$ to construct $S_{c+2}$, i.e., $S_{c+2}=S_{c+1}\cup\\{p\\}$, such
that $cost_{c}(S_{c+2})$ is maximized and continues this process up to the
construction of $S_{k}$. The pseudo code of the algorithm is described in
Algorithm 1.

Algorithm 1 GreedyDispersionAlgorithm$(P,k)$

Input:  A set $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ of $n$ points, and a positive
integer $k(c+1\leq k\leq n)$, along with distance function $d$.

Output: A subset $S_{k}\subseteq P$ of size $k$.

1:Compute
$S_{c+1}=\\{p_{i_{1}},p_{i_{2}},\ldots,p_{i_{c}},p_{i_{c+1}}\\}\subseteq P$
such that $cost_{c}(S_{c+1})$ is maximized.

2:for ($j=c+2,c+3,\ldots,k$) do

3: Let $p\in P\setminus S_{j-1}$ such that $cost_{c}(S_{j-1}\cup\\{p\\})$ is
maximized.

4: $S_{j}\leftarrow S_{j-1}\cup\\{p\\}$

5:end for

6:return $(S_{k})$

Let $S^{*}=\\{p_{1}^{*},p_{2}^{*},\ldots,p_{k}^{*}\\}\subseteq P$ be an
optimum solution for the $c$-dispersion problem, i.e.,
$cost_{c}(S^{*})=\max\limits_{{\begin{subarray}{c}S\subseteq P\\\
|S|=k\end{subarray}}}\\{cost_{c}(S)\\}$. We define a ball $B(p)$ at each point
$p\in X$ as follows: $B(p)=\\{q\in X|d(p,q)\leq\frac{cost_{c}(S^{*})}{2c}\\}$.
Let $B^{*}=\\{B(p)\mid p\in S^{*}\\}$. A point $q$ is _properly contained_ in
$B(p)$, if $d(p,q)<\frac{cost_{c}(S^{*})}{2c}$, whereas if
$d(p,q)\leq\frac{cost_{c}(S^{*})}{2c}$, then we say that point $q$ is
_contained_ in $B(p)$.

######  Lemma 3.1.

For any point $p\in P$, $B(p)$ can properly contains at most $c$ points from
the optimal set $S^{*}$.

###### Proof.

On the contrary assume that $B(p)$ properly contains $c+1$ points. Without
loss of generality assume that $p_{1}^{*},p_{2}^{*},\ldots,p_{c+1}^{*}(\in
S^{*})$ are properly contained in $B(p)$. This implies that each of
$d(p,p_{1}^{*}),d(p,p_{2}^{*}),\ldots,d(p,p_{c+1}^{*})$ is less than
$\frac{cost_{c}(S^{*})}{2c}$. Since distance function $d(.,.)$ satisfies
triangular inequality, $d(p_{1}^{*},p_{j}^{*})\leq
d(p_{1}^{*},p)+d(p,p_{j}^{*})$, for $j=2,3,\ldots,c+1$. This implies
$\sum_{j=2}^{c+1}d(p_{1}^{*},p_{j}^{*})\leq\sum_{j=2}^{c+1}d(p_{1}^{*},p)+\sum_{j=2}^{c+1}d(p,p_{j}^{*})<2c\times\frac{cost_{c}(S^{*})}{2c}=cost_{c}(S^{*})$.
This leads to a contradiction that $p_{1}^{*},p_{2}^{*},\ldots,p_{c+1}^{*}\in
S^{*}$. Thus, the lemma. ∎

######  Lemma 3.2.

For any point $s\in P$, if $B^{\prime}\subseteq B^{*}$ is the set of balls
that properly contains $s$, then $|B^{\prime}|\leq c$.

###### Proof.

On the contrary assume that $|B^{\prime}|>c$. Without loss of generality
assume that
$\\{B(p_{1}^{*}),B(p_{2}^{*}),\ldots,B(p_{c}^{*}),B(p_{c+1}^{*})\\}\subseteq
B^{\prime}$ are $c+1$ balls that properly contains $s$. Here,
$\\{p_{1}^{*},p_{2}^{*},\ldots,p_{c}^{*},p_{c+1}^{*}\\}\subseteq S^{*}$. Since
$s$ is properly contained in
$B(p_{1}^{*}),B(p_{2}^{*}),\ldots,B(p_{c}^{*}),B(p_{c+1}^{*})$, therefore each
$d(p_{1}^{*},s),d(p_{2}^{*},s),\ldots,d(p_{c}^{*},s),d(p_{c+1}^{*},s)$ is less
than $\frac{cost_{c}(S^{*})}{2c}$. So, the ball $B(s)=\\{q\mid
d(s,q)\leq\frac{cost_{c}(S^{*})}{2c}\\}$ properly contains $c+1$ points
$p_{1}^{*},p_{2}^{*},\ldots,p_{c}^{*},p_{c+1}^{*}$ of the optimal set $S^{*}$,
which is a contradiction to Lemma 3.1. Thus, the lemma. ∎

######  Lemma 3.3.

Let $M\subseteq P$ be a set of points such that $|M|<k$. If
$cost_{c}(M)\geq\frac{cost_{c}(S^{*})}{2c}$, then there exists at least one
ball $B(p_{j}^{*})\in
B^{*}=\\{B(p_{1}^{*}),B(p_{2}^{*}),\ldots,B(p_{k}^{*})\\}$ that properly
contains less than $c$ number of points in $M$.

###### Proof.

On the contrary assume that there does not exist any $j\in[1,k]$ such that
$B(p_{j}^{*})$ properly contains less than $c$ number of points in $M$.
Construct a bipartite graph $G(M\cup{B^{*}},{\cal E})$ as follows: (i) $M$ and
$B^{*}$ are two partite vertex sets, and (ii) for $u\in M$,
$(u,B(p_{j}^{*}))\in{\cal E}$ if and only if $u$ is properly contained in
$B(p_{j}^{*})$.

According to assumption, each ball $B(p_{j}^{*})$ properly contains at least
$c$ points in $M$. Therefore, the total degree of the vertices in $B^{*}$ in
$G$ is at least $kc$. Note that $|B^{*}|=k$. On the other hand, the total
degree of the vertices in $M$ in $G$ is at most $c\times|M|$ (see Lemma 3.2).
Since $|M|<k$, the total degree of the vertices in $M$ in $G$ is less than
$ck$, which leads to a contradiction that the total degree of the vertices in
$B^{*}$ in $G$ is at least $ck$. Thus, there exists at least one $p_{j}^{*}\in
S^{*}$ such that ball $B(p_{j}^{*})\in B^{*}$ properly contains at most $c-1$
points in $M$. ∎

######  Lemma 3.4.

The running time of Algorithm 1 is $O(n^{c+1})$.

###### Proof.

In line number 1, algorithm computes $S_{c+1}$ such that $cost_{c}(S_{c+1})$
is maximized. To compute it, algorithm calculates $cost_{c}(S_{c+1})$ for each
distinct subset $S_{c+1}\subseteq P$ independently. So, algorithm invests
$O{n\choose c+1}=O(n^{c+1})$ time to compute $S_{c+1}$ such that
$cost_{c}(S_{c+1})$ is maximized. Note that the value of $c$ is fixed. Now,
for choosing a point in each iteration, algorithm takes $O(n^{2})$ time. Here,
the number of iteration is bounded by $k\leq n$. So, to construct a set
$S_{k}$ of size $k$ from $S_{c+1}$, algorithm takes $O(n^{3})$ time. Since
line number 1 of Algorithm 1 takes a substantial amount of time compared to
other steps of the algorithm, therefore the overall time complexity is
$O(n^{c+1})$. ∎

######  Theorem 3.5.

Algorithm 1 produces $2c$-factor approximation result in polynomial time for
the $c$-dispersion problem.

###### Proof.

Let $I=(P,k)$ be an arbitrary input instance of the $c$-dispersion problem in
a metric space $(X,d)$, where $P=\\{p_{1},p_{2},\ldots,p_{n}\\}$ is the set of
$n$ points and $k$ is a positive integer. Let $S_{k}$ and $S^{*}$ be an output
of Algorithm 1 and an optimum solution, respectively, for the instance $I$. To
prove the theorem, we show that $\frac{cost_{c}(S^{*})}{cost_{c}(S_{k})}\leq
2c$ . Here we use induction to show that
$cost_{c}(S_{i})\geq\frac{cost_{c}(S^{*})}{2c}$ for each $i=c+1,c+2,\ldots,k$.

Since $S_{c+1}$ is an optimum solution for $c+1$ points (see line number 1 of
Algorithm 1), therefore $cost_{c}(S_{c+1})\geq
cost_{c}(S^{*})\geq\frac{cost_{c}(S^{*})}{2c}$ holds. Now, assume that the
condition holds for each $i$ such that $c+1\leq i<k$. We will prove that the
condition holds for $(i+1)$ too.

Let $B^{*}$ be the set of balls corresponding to points in $S^{*}$. Since
$i<k$ and $S_{i}\subseteq P$ with condition
$cost_{c}(S_{i})\geq\frac{cost_{c}(S^{*})}{2c}$, then there exists at least
one ball $B(p_{j}^{*})\in B^{*}$ that properly contains at most $c-1$ points
in $S_{i}$ (see Lemma 3.3). Now, if $B(p_{j}^{*})$ properly contains $c-1$
points of the set $S_{i}$, then the distance of $p_{j}^{*}$ to the $c$-th
closest point in $S_{i}$ is greater than or equal to
$\frac{cost_{c}(S^{*})}{2c}$. Now, if we choose a point $p_{j}^{*}\in S^{*}$
to the set $S_{i}$ to construct set $S_{i+1}$ (line number 3 of the
algorithm), then $cost_{c}(p_{j}^{*},S_{i+1})\geq\frac{cost_{c}(S^{*})}{2c}$.
Let $p\in S_{i+1}$ be an arbitrary point. Now, to prove
$cost_{c}(p,S_{i+1})\geq\frac{cost_{c}(S^{*})}{2c}$, we consider following
cases: (1) $p_{j}^{*}$ is not in the $c$-th nearest point of $p$ in $S_{i+1}$,
and (2) $p_{j}^{*}$ is one of the $c$ nearest points of $p$ in $S_{i+1}$. In
case (1), $cost_{c}(p,S_{i+1})\geq\frac{cost_{c}(S^{*})}{2c}$ by the
definition of the set $S_{i}$, and in case (2) there exists at least one point
$q\in S_{i+1}$ such that $d(q,p_{j}^{*})\geq\frac{cost_{c}(S^{*})}{2c}$, and
$q$ is one of the $c$ nearest points of $p$ (see Lemma 3.2). Therefore, sum of
the distances of $p$ from $c$ nearest point in $S_{i+1}$ is greater than
$d(p,p_{j}^{*})+d(p,q)\geq d(p_{j}^{*},q)\geq\frac{cost_{c}(S^{*})}{2c}$.
Therefore, we can conclude that if we consider the set
$S_{i+1}=S_{i}\cup\\{p_{j}^{*}\\}$, then
$cost_{c}(S_{i+1})\geq\frac{cost_{c}(S^{*})}{2c}$.

Since our algorithm chooses a point (see line number 3 of Algorithm 1) that
maximizes $cost_{c}(S_{i+1})$, therefore it will always choose a point in the
iteration $i+1$ such that $cost_{c}(S_{i+1})\geq\frac{cost_{c}(S^{*})}{2c}$.

By the help of Lemma 3.1, Lemma 3.2 and Lemma 3.3, we have
$cost_{c}(S_{i+1})\geq\frac{cost_{c}(S^{*})}{2c}$ and thus condition holds for
$(i+1)$ too. Also, Lemma 3.4 says that Algorithm 1 computes $S_{k}$ in
polynomial time. Therefore, Algorithm 1 produces $2c$-factor approximation
result in polynomial time for the $c$-dispersion problem.

∎

##  4  $c$-Dispersion Problem is W[1]-hard

In this section, we discuss the hardness of the $c$-dispersion problem in a
metric spaces $(X,d)$ in the realm of parameterized complexity. We prove that
the $c$-dispersion problem in a metric spaces $(X,d)$ is $W[1]$-hard. We show
a parameterized reduction from $k$-independent set problem (known to be
$W[1]$-hard [11]) to the $c$-dispersion problem in $(X,d)$.

We define parameterized version of both the problems as follows.

_k-Independent Set Problem_
_Instance:_ A graph $G=(V,E)$ and a positive integer $k$.
_Parameter:_ $k$
_Problem:_ Does there exist an independent set of size $k$ in $G$ ?

_$c$ -Dispersion Problem _
_Instance:_ A set $P$ of $n$ locations and a positive integer $k$.
_Parameter:_ $k$
_Problem:_ Given a bound $2c$, does there exist a subset $S_{k}\subseteq P$ of
size $k$ such that $cost_{c}(S_{k})$ is $2c$ ?

######  Theorem 4.1.

$c$-dispersion problem in a metric space $(X,d)$ is $W[1]$-hard.

###### Proof.

We prove this by giving a parameterized reduction from the $k$-independent set
problem in simple undirected graphs to the $c$-dispersion problem in $(X,d)$.
Now, we present a method to construct an instance of $c$-dispersion problem
from any instance of the $k$-independent set problem in polynomial time.

Let $G=(V,E)$ be an arbitrary instance of the $k$-independent set problem.
Here, $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$. We construct an instance of the
$c$-dispersion problem from the given instance of the $k$-independent set
problem. We use set $V$ of vertices of $G$ as a set of locations $P$, i.e.,
$P=\\{p_{i}\mid v_{i}\in V\\}$ of $n$ points. We define distance between
points $p_{i},p_{j}\in P$ as follows: $d(p_{i},p_{j})=1$ if $(v_{i},v_{j})\in
E$, and $d(p_{i},p_{j})=2$, otherwise. Note that this distance function
satisfies triangle inequality. So, the entire process of constructing an
instance of the $c$-dispersion problem takes polynomial time.

Claim. $G$ has independent set of size $k$ if and only if there exists a
subset $S_{k}\subseteq P$ of size $k$, such that $cost_{c}(S_{k})=2c$.

Necessity: Let $I\subseteq V$ be an independent set of $G$ such that $|I|=k$.
We construct a set $S_{k}\subseteq P$ by selecting $k$ points in $P$
corresponding to vertices in $I$, i.e., $S_{k}=\\{p_{i}|v_{i}\in I\\}$. Since,
$I$ is an independent set, therefore by construction of an instance of the
$c$-dispersion problem from $G$, distance between any two points in $S_{k}$ is
$2$. This implies that for each $p\in S_{k}$, $cost_{c}(p,S_{k})=2c$.
Therefore, $cost_{c}(S_{k})=2c$.

Sufficiency: Suppose there exists a subset $S_{k}\subseteq P$, such that
$cost_{c}(S_{k})=2c$. Since $cost_{c}(S_{k})=2c$, this implies that there
exists a point $p\in S_{k}$ such that $cost_{c}(p,S_{k})=2c$ and for all $q\in
S_{k}$, $cost_{c}(q,S_{k})\geq cost_{c}(p,S_{k})$. Now if for a point $q\in
S_{k}$, $cost_{c}(q,S_{k})>2c$, then by pigeon hole principle, distance of $q$
to one of the $c$ nearest points in $S_{k}$ is greater than 2, which is not
possible as per our construction of an instance of the $c$-dispersion problem.
So, for all points $q\in S_{k}$, $cost_{c}(q,S_{k})=2c$. Now, we can create a
set $I\subseteq V$ by selecting vertices corresponding to each point in
$S_{k}$, i.e., $I=\\{v_{i}\mid p_{i}\in S_{k}\\}$. Since distance between each
pair of points is $2$, therefore there does not exist any edge in $I$.
Therefore, $I\subseteq V$ is an independent set of size $k$.

Since $k$-independent set problem is $W[1]$-hard for a parameter $k$ [11], and
therefore using the above reduction we conclude that the $c$-dispersion
problem in a metric space $(X,d)$ is also $W[1]$-hard for the same parameter
$k$. Thus, the theorem. ∎

##  5 Conclusion

In this article, we studied the $c$-dispersion problem in a metric space. We
presented a polynomial time $2c$-factor approximation algorithm for the
$c$-dispersion problem in a metric space. The best known approximation factor
available for the Euclidean $c$-dispersion problem in $\mathbb{R}^{2}$ is
$2c^{2}$ [2]. For $c=1$, the proposed algorithm will produce a 2-factor
approximation result, which is the same as the result in [16, 18]. Therefore,
our proposed algorithm is a generalized version and provides a better
approximation result for the problem. We also proved that the $c$-dispersion
problem in a metric space is W[1]-hard.

## Acknowledgement

We thank Prof. Arie Tamir (Tel Aviv University, Tel Aviv, Israel) for his
useful suggestions on the literature of the problem.

## References

  * [1] Akagi, Toshihiro and Araki, Tetsuya and Horiyama, Takashi and Nakano, Shin-ichi and Okamoto, Yoshio and Otachi, Yota and Saitoh, Toshiki and Uehara, Ryuhei and Uno, Takeaki and Wasa, Kunihiro.  Exact algorithms for the max-min dispersion problem.  International Workshop on Frontiers in Algorithmics, pp. 263–272, 2018.
  * [2] Amano, Kazuyuki and Nakano, Shin-Ichi.  Away from Rivals.  CCCG, pp. 68–71, 2018.
  * [3] Amano, Kazuyuki and Nakano, Shin-Ichi.  An Approximation Algorithm for the 2-Dispersion Problem.  IEICE Transactions on Information and Systems, 103(3): 506–508, 2020.
  * [4] Baur, Christoph and Fekete, Sándor P.  Approximation of geometric dispersion problems.  Algorithmica, 30(3):451–470, 2001.
  * [5] Bhattacharya, Binay and Shi, Qiaosheng.  Optimal algorithms for the weighted p-center problems on the real line for small p,  Workshop on Algorithms and Data Structures, 529–540, 2007.
  * [6] Birnbaum, Benjamin and Goldman, Kenneth J.  An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs.  Algorithmica, 55(1):42–59, 2009.
  * [7] Chandra, Barun and Halldórsson, Magnús M.  Approximation algorithms for dispersion problems.  Journal of algorithms, 38(2):438–465, 2001.
  * [8] Chandrasekaran, R and Daughety, Andrew.  Location on tree networks: p-centre and n-dispersion problems.  Mathematics of Operations Research, 6(1):50–57, 1981.
  * [9] Chandrasekaran, R and Tamir, Arie.  Polynomially bounded algorithms for locating p-centers on a tree.  Mathematical Programming, 22(1): 304–315, 1982
  * [10] Erkut, Erhan.  The discrete p-dispersion problem.  European Journal of Operational Research, 46(1):48–60, 1990.
  * [11] Flum, Jörg and Grohe, Martin.  Parameterized complexity theory.  Springer Science & Business Media, 2006.
  * [12] Frederickson, Greg N.  Optimal algorithms for tree partitioning.  Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, 168–177, 1991.
  * [13] Hassin, Refael and Rubinstein, Shlomi and Tamir, Arie.  Approximation algorithms for maximum dispersion.  Operations research letters, 21(3):133–137, 1997.
  * [14] Kortsarz, Guy and Peleg, David.  On Choosing a Dense Subgraph.  Procedings of the 34th Annual Symposium on Foundations of Computer Science, 692–701, 1993.
  * [15] Megiddo, Nimrod and Tamir, Arie.  An $O(p^{2}log^{2}n)$ algorithm for the unweighted p-center problem on the line.
  * [16] Ravi, Sekharipuram S and Rosenkrantz, Daniel J and Tayi, Giri Kumar.  Heuristic and special case algorithms for dispersion problems.  Operations Research, 42(2):299–310, 1994.
  * [17] Shier, Douglas R.  A min-max theorem for p-center problems on a tree.  Transportation Science, 11(3):243–252, 1977.
  * [18] Tamir, Arie.  Obnoxious facility location on graphs.  SIAM Journal on Discrete Mathematics, 4(4): 550-567, 1991.
  * [19] Tamir, Arie.  Comments on the paper:‘Heuristic and special case algorithms for dispersion problems’ by SS Ravi, DJ Rosenkrantz, and GK Tayi.  Operations Research, 46(1): 157–158, 1998
  * [20] Wang, DW and Kuo, Yue-Sun.  A study on two geometric location problems.  Information processing letters, 28(6):281–286, 1988.
  * [21] White, Douglas J.  The maximal-dispersion problem.  IMA Journal of Mathematics Applied in Business and Industry, 3(2):131–140, 1991.


# A New Solution for MU-MISO Symbol-Level Precoding: Extrapolation and Deep
Unfolding

Mu Liang, Ang Li, ,
Xiaoyan Hu, , and Christos Masouros,

###### Abstract

Constructive interference (CI) precoding, which converts the harmful multi-
user interference into beneficial signals, is a promising and efficient
interference management scheme in multi-antenna communication systems.
However, CI-based symbol-level precoding (SLP) experiences high computational
complexity as the number of symbol slots increases within a transmission
block, rendering it unaffordable in practical communication systems. In this
paper, we propose a symbol-level extrapolation (SLE) strategy to extrapolate
the precoding matrix by leveraging the relationship between different symbol
slots within in a transmission block, during which the channel state
information (CSI) remains constant, where we design a closed-form iterative
algorithm based on SLE for both PSK and QAM modulation. In order to further
reduce the computational complexity, a sub-optimal closed-form solution based
on SLE is further developed for PSK and QAM, respectively. Moreover, we design
an unsupervised SLE-based neural network (SLE-Net) to unfold the proposed
iterative algorithm, which helps enhance the interpretability of the neural
network. By carefully designing the loss function of the SLE-Net, the time-
complexity of the network can be reduced effectively. Extensive simulation
results illustrate that the proposed algorithms can dramatically reduce the
computational complexity and time complexity with only marginal performance
loss, compared with the conventional SLP design methods.

###### Index Terms:

MIMO, symbol-level precoding, extrapolation, model-driven, deep unfolding.

##  I Introduction

Multi-antenna communication has the potential to offer significant
multiplexing and array gains, which can meet the spectral efficiency and
energy efficiency requirements for current and future wireless communication
systems[1]. Due to the existence of inter-stream and inter-user interference,
careful management of interference is crucial for realizing the benefits of
multi-antenna communication systems[2]. In the downlink transmission,
precoding, which is an effective technique for managing interference, has
attracted extensive attention[3].

Among various precoding approaches, the capacity-achieving dirty-paper coding
(DPC) scheme is proposed in[4] by pre-subtracting the interference prior to
transmission. However, DPC is difficult to implement in practical systems due
to the assumption of infinite codebook length. Tomlinson-Harashima precoding
(THP) [5] imposes an integer offset at the transmitter, while a modulo
operation is required for the received signal. In [6], vector perturbation
(VP) precoding is propopsed, which selects an appropriate perturbation vector
to perturb the data symbols via the sphere encoding algorithm and a modulo
operation is also required at the receiver side. However, all of the above
precoding methods demand significant computational resources due to their
nonlinear design nature, and are too complicated to implement. In order to
find a balance between performance and complexity, linear precoding methods
are proposed and have received more attention[7, 8, 9]. Maximum-ratio
transmission (MRT) precoding is the simplest strategy that maximizes the
received signal-to-noise ratio (SNR) [7], while the capability of MRT to
handle inter-user interference is limited. In [8], zero-forcing (ZF) precoding
that employs the channel inversion to fully eliminate mutual interference is
proposed. Additionally, a regularized ZF (RZF) scheme is proposed in [9] to
alleviate the noise amplification effect of ZF precoding to further improve
the communication performance.

On the other hand, precoding algorithms assisted by optimization theory have
received increasing attention. The well-known power minimization problem (PM)
aims to minimize the total transmit power subject to the signal-to-
interference-plus-noise ratio (SINR) target for each user. This problem can be
solved using various approaches, including the uplink-downlink duality[10],
conic programming[11], semidefinite relaxation method (SDR)[12], iteartive
algorithm, etc. Another popular form of optimization-based schemes is known as
SINR balancing (SB) problem, which aims to maximize the minimum SINR of the
users subject to a total power constraint. The SINR balancing problem (SB) is
proved to be the inverse problem of the power minimization problem. Several
schemes have been proposed to address the SB precoding problem, including
bisection search [11] and the iterative algorithm [13]. In addition to the
sum-power constraint, the consideration of a per-antenna power constraint may
be more practical, because antenna has its dedicated power amplifier. In [14],
the authors employ the primal-dual interior-point method (IPM) to solve the SB
problem under the per-antenna power constraint (PAPC). In [15], the authors
consider signal-to-leakage-plus-noise ratio (SLNR) maximization for multi-
antenna downlink under the PAPC based on the gradient projection method.

It is important to note that, all of the above precoding design methods view
interference as harmful and attempt to eliminate the interference, while the
interference can in fact be beneficial and further exploited on a symbol level
via the concept of symbol-level precoding [16]. The idea of exploiting
interference was first introduced in [17], where instantaneous interference
was classified into constructive and destructive. Some early approaches to
exploit constructive interference (CI) were first proposed in [18]. In[19],
the authors proposed a correlation rotation linear precoding scheme to
translate destructive interference into constructive. Subsequently,
optimization-based interference exploitation methods have been proposed in
[20] and [21] to expand the region of CI by relaxing the strict phase-rotation
requirement to achieve a better performance.

For SLP, the precoding matrix is dependent on both the channel state
information (CSI) and data symbols, which means that the SLP methods must
solve a constrained optimization problem at each symbol slot to fully exploit
the benefits of CI. Within a transmission block, when the CSI remains constant
while the data symbols change per slot, recalculating the precoding matrix
becomes inevitable, which results in huge computational burden for SLP
compared to traditional precoding approaches. Therefore, the primary challenge
to implement SLP in practical communication systems is to reduce the
substantial computational complexity. In recent years, low-complexity SLP
methods have attracted increasing attention. In [22], the authors proposed an
iterative closed-form scheme to calculate the optimal precoding for SLP.
Compared to directly solving optimization problems, the proposed iterative
algorithm offers substantially reduced computational complexity. In [23], the
authors reformulated the CI-based PM problem and showed that the optimization
problem was able to be decomposed into several parallel sub-problems, leading
to a substantial reduction in computational complexity. In [24], the authors
divided the users into groups according to their channel correlation, and then
designed the precoding matrix where the interference is exploited within each
user group while eliminate between different groups to reduce the complexity,
which however results in a sub-optimal performance. In [25], a CI-based block-
level precoding (BLP) was proposed, in which a same precoding matrix is
applied to a block of symbol slots within one transmission block to reduce the
calculation complexity. BLP offers some additional performance benefits when
the length of the considered block is short, while its performance will
deteriorate as the block length increases. Therefore, it requires further
explorations of low-complexity SLP designs.

Recently, many studies have developed learning-based algorithms to solve the
computationally intensive and time sensitive signal processing tasks in
communication systems. In [26], the authors introduced a model-driven neural
network for PSK-based SLP design, reducing the complexity of obtaining the
precoding matrix. Nevertheless, it didn’t adequately consider the network’s
generalizability, thus constraining its practical applicability in practical
environments. In [27], the authors proposed a learning-based framework for
low-complexity multi-user MIMO precoding design, employing a neural network to
fit the mapping function between channel coefficients and the precoding
matrix. However, it remains fundamentally a data-driven neural network, and
the interpretability of the neural network requires further enhancement. Deep
unfolding has become an increasingly popular method that transforms iterative
algorithms into a layer-wise structure, resembling a neural network [28]. The
deep unfolding enhances the network’s interpretability by transforming the
network from data-driven to model-driven. This method has a wide range of
applications in communications, such as detection and coding [29, 30, 31]. For
example, in [32], the authors unfolded a power minimization SLP formulation
based on the IPM proximal barrier function and proposed a robust precoding
matrix design method. In [33], the author proposed a deep-unfolding framework
to solve the sum-rate maximization problem for precoding design in MU-MIMO
system and reduced the complexity compared to the conventional method.

On the other hand, extrapolation is a method to estimate or predict unknown
data by utilizing information from known data and their correlation, which
finds extensive applications in channel estimation and prediction in recent
years [34, 35]. In [34], channel extrapolation is proposed for obtaining the
CSI of different antenna patterns in the pattern reconfigurable communication
system, where reducing the pilot overheads is the main challenge. In [35],
channel extrapolation is proposed for obtaining the downlink channel
coefficients from the uplink channel coefficients in a FDD MIMO system, where
the pilot overheads are greatly reduced.

Essentially, the reason why SLP is computationally expensive is that SLP
methods must solve a constrained optimization problem for each data symbol
slot. Motivated by the extrapolation method, in this paper, we propose an
iterative symbol-level extrapolation (SLE) method to extrapolate the SLP
precoding matrix for different data symbol slots to reduce the complexity of
CI-based SLP design. Furthermore, based on the SLE, we unfold the iteration
algorithm into a unique layer-wise structure and derive a SLE-Net. For
clarity, we summarize the contributions of this paper as:

  1. 1.

We propose a novel low-complexity SLE-based SLP solution. Within a
transmission block, we exploit the relationships between different symbol
slots to extrapolate the symbol-scaling factors of data symbols used in SLP to
reduce the complexity.

  2. 2.

By describing the CI-SLP problem using symbol-scaling metric, we simplify
optimization problem into a convex problem. Based on the simplified problem,
the efficient SLE-based iterative algorithm is developed to solve the SLP
problem for PSK modulation and QAM modulation, respectively. Moreover, we also
derive a sub-optimal closed-form algorithm, to further reduce the
computational complexity.

  3. 3.

We utilize the unfolding approach and design an unsupervised SLE-Net by
expanding the SLE-based iterative algorithm. Based on the simplified
formulation of the optimization problem for SLP, we design a unique loss
function for the SLE-Net.

  4. 4.

We study the computational costs of the proposed schemes in terms of the
required number of multiplications.

Numerical results show that the proposed algorithm can reduce complexity.
Compared to traditional SLP algorithms, the proposed SLE-based method can
reduce computational complexity without significant performance losses for
both PSK modulation and QAM modulation. At the same time, the proposed SLP-
Net, with comparable time complexity to the proposed SLE-based sub-optimal
closed-form algorithm, exhibits marginal performance loss to the optimal
solution, exhibiting the superiority of the SLP-Net..

_Notations:_ $\alpha$, $\bm{\alpha}$, $\bf{A}$ denote scalar, vector and
matrix, respectively. $vec\left(\cdot\right)$ denotes the vector form of a
matrix, $\Re(\cdot)$ and $\Im(\cdot)$ extract the real and imaginary parts of
the argument, respectively. $\left\|\bf{\cdot}\right\|_{2}$ denotes the
Euclidean norm. $(\cdot)^{H}$ and $(\cdot)^{T}$ denotes the conjugate
transposition and transposition. $diag(\cdot)$ is the transformation of a
column vector into a diagonal matrix. $card\left|\cdot\right|$ denotes the
cardinality of a set, $\otimes$ represents the Kronecker product, and $\odot$
represents the Hadamard product operation. $\mathbb{R}$ and $\mathbb{C}$
denote the set of the real numbers and complex numbers, respectively. ${\bf
I}_{K}$ denotes the $K\times K$ identity matrix.

##  II System Model And Constructive Inference

###  II-A System Model

We consider a multi-user MISO system in the downlink equipped with
$M_{\mathrm{t}}$ transmit antennas serving $K$ single-antenna users. We
consider the scenario of a limited number of scattering clusters between the
transmitter and each receiver [36], and therefore channel coefficients for the
$k$-th user, denoted as ${\bf h}_{k}\in\mathbb{C}^{M_{\mathrm{t}}\times 1}$,
can be modeled as 111The proposed extrapolation method is channel independent,
and applies to other channel models as well.

${\bf
h}_{k}=\sum_{l=1}^{L_{k}}\alpha_{k,l}{\mathbf{a}}_{\mathrm{t}}(\theta_{k,l}),$
(1)

where $L_{k}$ is the total number of the propagation paths between the
transmitter and the $k$-th receiver, $\alpha_{k,l}$ is the complex gain of the
$k$-th user’s $l$-th path following the complex Gaussian distribution.
${\mathbf{a}}_{\mathrm{t}}(\theta_{k,l})\in\mathbb{C}^{M_{\mathrm{t}}\times
1}$ is referred to the antenna array steering vector. When uniform linear
array (ULA) is used, ${\mathbf{a}}_{\mathrm{t}}(\theta_{k,l})$ can be
expressed as

${\mathbf{a}}_{\mathrm{t}}(\theta_{k,l})=\frac{1}{\sqrt{M_{\mathrm{t}}}}\left[1,e^{j\theta_{k,l}},\cdots,e^{j(M_{\mathrm{t}}-1)\theta_{k,l}}\right]^{T}.$
(2)

In (2), $\theta_{k,l}$ denotes the normalized angle of departure (AoD) of the
$k$-th user’s $l$-th path, and the relationship with the physical AoD
$\phi_{k,l}$ can be expressed as

$\theta_{k,l}=\frac{2\pi d\sin(\phi_{k,l})}{\lambda},$ (3)

where $d$ is the spacing between two adjacent antenna elements at the
transmitter and $\lambda$ is the wavelength. Moreover, by assuming that
$\phi_{k,l}\in[0,2\pi)$ and $d=\frac{\lambda}{2}$, we have
$\theta_{k,l}\in[-\pi,\pi)$. To better describe the channel in a time-varying
environment, we divide the normalized AoD into $N$ grids, as shown in the
following formula:

$\bar{\theta}_{n}=\frac{2\pi(n-1)}{N}+\frac{\pi}{N},\forall n=1,\cdots,N.$ (4)

In this work, we consider the dynamic channel model of the time-varying AoDs
and the complex path gains, where normalized AoD follows the discrete state
Markov processing. Thus, the angle from the $(c-1)$-th transmission block to
the $c$-th transmission block is determined by the transition probability
function in [36]. The complex path gain $\alpha_{k,l}$ is assumed to follow an
auto-regressive process, given by

$\alpha_{k,l}^{c}=p_{k}\alpha_{k,l}^{c-1}+\eta_{k,l}^{c},$ (5)

where $p_{k}\in[0,1]$ is the correlation coefficient, $\eta_{k,l}^{c}$ is a
random variable used to simulate an auto-regressive process, $\eta_{k,l}^{c}$
and $\alpha_{k,l}$ are assumed to follow the distribution of
$\mathcal{CN}(0,(1-p_{k}^{2})\sigma^{2})$ and $\mathcal{CN}(0,\sigma^{2})$,
$\sigma^{2}$ denotes the variance of the distribution.

Within a transmission block, the data symbol vector in the $n$-th slot ${\bf
s}^{(n)}=\left[s_{1}^{(n)},s_{2}^{(n)},\cdots,s_{K}^{(n)}\right]^{T}\in\mathbb{C}^{K\times
1}$ is drawn from a normalized constellation, and the received signal at the
$k$-th user in a downlink MU-MISO system can be expressed as

$y_{k}^{(n)}={\bf h}_{k}^{T}{\bf W}^{(n)}{\bf s}^{(n)}+z_{k}^{(n)},$ (6)

where ${\bf W}^{(n)}\in\mathbb{C}^{M_{\mathrm{t}}\times K}$ is the precoding
matrix for the $n$-th symbol slot, and $z_{k}^{(n)}$ is the additive Gaussian
noise at the receiver following the standard complex Gaussian distribution.

###  II-B Constructive Interference for PSK Modulation

CI refers to the interference that pushes the received signals away from all
of their detection thresholds, leading to higher probability for correct
signal detection [37]. Therefore, based on this definition, the constructive
region is the complex plane within which the interference is able to push the
received signal, making it farther away from the decision boundaries. In this
paper, we choose the symbol-scaling metric in [38] to describe the CI
constrains, which is applicable to both PSK and QAM modulations. The symbol-
scaling CI metric decomposes the given constellation point along the
directions of the vectors that define the detection thresholds.

Figure 1: CI regions for generic $\mathcal{M}$-PSK

As an example, we discuss the CI region of QPSK modulation, and the CI
constraints are illustrated in Fig. 1. Without loss of generality, we denote
$\vec{OS}=s_{k}^{(n)}$ as a nominal constellation point that is the intended
data symbol for user $k$ in the $n$-th slot. We further denote $\vec{OB}={\bf
h}_{k}^{T}{\bf W}^{(n)}{\bf s}^{(n)}$ as the received signal for user $k$ in
the $n$-th slot excluding noise. Based on the geometry in Fig. 1, we are able
to decompose the constellation symbol along the detection thresholds as:

$\vec{OS}=\vec{OF}+\vec{OG}\Rightarrow
s_{k}^{(n)}=s_{k,\mathcal{A}}^{(n)}+s_{k,\mathcal{B}}^{(n)}.$ (7)

For generic $\mathcal{M}$-PSK constellations, each data symbol can be
expressed as

$s_{\mathrm{c}}=e^{j\left[\frac{2\pi}{\mathcal{M}}(c-1)+\frac{\pi}{4}\right]},c\in\\{1,2,\cdots,\mathcal{M}\\},$
(8)

where $s_{{c}}$ denotes the $c$-th constellation point. For the $k$-th data
symbol in the $n$-th symbol slot in one transmission block, the detection
thresholds $s_{k,\mathcal{A}}^{(n)}$ and $s_{k,\mathcal{B}}^{(n)}$ of
constellation point $s_{{k}}^{(n)}$ can be expressed as

$s_{k,\mathcal{A}}^{(n)}=\frac{s_{{k}}^{(n)}e^{j\frac{\pi}{\mathcal{M}}}}{2\cos(\frac{\pi}{\mathcal{M}})},$
(9)
$s_{k,\mathcal{B}}^{(n)}=\frac{s_{{k}}^{(n)}e^{-j\frac{\pi}{\mathcal{M}}}}{2\cos(\frac{\pi}{\mathcal{M}})}.$
(10)

Following a similar approach to (7), we decompose the noiseless received
signal for user $k$ along the detection thresholds, which is shown as

$\vec{OB}=\vec{OD}+\vec{OE}\Rightarrow{\bf h}_{k}^{T}{\bf W}^{(n)}{\bf
s}^{(n)}=\alpha_{k,\mathcal{A}}^{(n)}s_{k,\mathcal{A}}^{(n)}+\alpha_{k,\mathcal{B}}^{(n)}s_{k,\mathcal{B}}^{(n)},$
(11)

where $\alpha_{k,\mathcal{A}}^{(n)}>0$ and $\alpha_{k,\mathcal{B}}^{(n)}>0$
represent the symbol-scaling factors along the detection thresholds for the
$k$-th constellation of the $n$-th symbol slot. The set $\mathcal{O}^{(n)}$
and $\mathcal{I}^{(n)}$ consists of the symbol-scaling factors for the $n$-th
symbol slot that can be exploited interference and cannot be exploited
interference, respectively. For PSK modulation, all constellation points of
PSK modulation can fully leverage the advantages of CI. Therefore,
$\mathcal{O}^{(n)}$ and $\mathcal{I}^{(n)}$ can be expressed as

$\mathcal{I}^{(n)}=\emptyset,$ (12) $\mathcal{O}^{(n)}=\left\\{{\alpha_{1,\cal
A}^{(n)},{\alpha_{1,\cal B}^{(n)}},{\alpha_{2,\cal A}^{(n)}},{\alpha_{2,\cal
B}^{(n)}},\cdots,{\alpha_{K,\cal A}^{(n)}},{\alpha_{K,\cal
B}^{(n)}}}\right\\}.$ (13)

###  II-C Constructive Interference for QAM Modulation

Figure 2: CI regions for 16QAM

For generic $\mathcal{M}$-QAM modulation, we use 16QAM as an example to
explain the impact of CI, as illustrated in Fig. 2. There are four types of
constellation points for QAM modulation, denoted as ‘A’, ‘B’, ‘C’, and ‘D’.
The interference on the inner constellation points of type ‘A’ is only
destructive, and CI exists for the real part of the constellation points type
‘B’ and imaginary parts of type ‘C’, while both the real and imaginary part of
the constellation points type ‘D’ can be exploited. To be more specific, we
decompose the constellation symbol along the detection thresholds, as follows

$\vec{OS}=\vec{OF}+\vec{OG}\Rightarrow
s_{k}^{(n)}=s_{k,\mathcal{A}}^{(n)}+s_{k,\mathcal{B}}^{(n)},$ (14)

For the $k$-th data symbol of the $n$-th symbol slot in one transmission
block, $s_{k,\mathcal{A}}^{(n)}$ and $s_{k,\mathcal{B}}^{(n)}$ can be
expressed as

$s_{k,\mathcal{A}}^{(n)}=\Re\left({s_{k}^{(n)}}\right),s_{k,\mathcal{B}}^{(n)}=j\cdot\Im\left(s_{k}^{(n)}\right).$
(15)

For QAM modulation, only the outer constellation points can exploit CI, thus
their symbol-scaling factors belong to $\mathcal{O}^{(n)}$, while the inner
constellation points cannot exploit CI, and their symbol-scaling factors
belong to $\mathcal{I}^{(n)}$. Therefore, $\mathcal{O}^{(n)}$ and
$\mathcal{I}^{(n)}$ for the $n$-th symbol slot can be expressed as

${\cal O}^{(n)}\cup{\cal I}^{(n)}=\left\\{{\alpha_{1,\cal
A}^{(n)},{\alpha_{1,\cal B}^{(n)}},{\alpha_{2,\cal A}^{(n)}},{\alpha_{2,\cal
B}^{(n)}},\cdots,{\alpha_{K,\cal A}^{(n)}},{\alpha_{K,\cal
B}^{(n)}}}\right\\},$ (16)

and

$card\left|{\cal O}^{(n)}\right|+card\left|{\cal I}^{(n)}\right|=2K.$ (17)

##  III Proposed Symbol-Level Extrapolation Precoding Design

For $\mathcal{M}$-PSK and $\mathcal{M}$-QAM modulation, by leveraging the
relationships of data symbols in different symbol slots within one
transmission block, we propose an iterative SLE algorithm and a sub-optimal
algorithm to reduce the computational complexity of conventional SLP. Within
one transmission block, the CSI is constant, while the precoding matrix for
SLP is different between symbol slots, resulting in significant computational
complexity in SLP design. To address this issue of SLP, we leverage the
relationships between different symbol slots, and without loss of generality
we describe the extrapolation of the precoding matrix from the $n$-th symbol
slot to the $m$-th symbol slot.

The data symbols for the $m$-th symbol slot and the $n$-th symbol slot are
denoted as ${\bf s}^{(m)}\in\mathbb{C}^{K\times 1}$ and ${\bf
s}^{(n)}\in\mathbb{C}^{K\times 1}$, respectively. The relationship between
${\bf s}^{(m)}$ and ${\bf s}^{(n)}$ can be defined as:

${\bf s}^{(m)}={\bf A}{\bf s}^{(n)},$ (18)

where ${\bf
A}=diag(\\{\beta_{1}e^{j\cdot\varphi_{1}},\beta_{2}e^{j\cdot\varphi_{2}},\cdots,\beta_{K}e^{j\cdot\varphi_{K}}\\})\in\mathbb{C}^{K\times
K}$ represents the diagonal transform matrix, $\varphi_{k}$ and $\beta_{k}$
denote the phase and amplitude difference between the $k$-th symbol in the
$n$-th symbol slot and in the $m$-th symbol slot, respectively.

###  III-A The case of $\mathcal{M}$-PSK

Based on the symbol-scaling metric in [38], the original optimization problem
that maximizes the CI effect for the $n$-th symbol slot is give by

$\displaystyle\mathcal{P}_{1}:{\kern
3.0pt}\mathop{\max}\limits_{{{\bf{W}}^{(n)}},{\kern 1.0pt}t}{\kern 3.0pt}t$
(19) $\displaystyle{\kern 0.0pt}s.t.{\kern 10.0pt}{{\bf{h}}_{k}^{T}}{{\bf
W}^{(n)}{\bf
s}^{(n)}}=\alpha_{k,\mathcal{A}}^{(n)}s_{k,\mathcal{A}}^{(n)}+\alpha_{k,\mathcal{B}}^{(n)}s_{k,\mathcal{B}}^{(n)},{\kern
3.0pt}\forall k\in{\cal K},$ $\displaystyle{\kern 24.0pt}t\leq\alpha_{i}^{\cal
O},{\kern 3.0pt}\forall\alpha_{i}^{\cal O}\in{\cal O}^{(n)},$
$\displaystyle{\kern 22.0pt}\left\|{{\bf{W}}^{(n)}{\bf
s}^{(n)}}\right\|_{2}^{2}\leq{p_{0}},$

where $\mathcal{K}=\left\\{{1,2,\cdots,K}\right\\}$, $\alpha_{i}^{\cal O}$
represents the $i$-th element in set ${\cal O}^{(n)}$, $p_{0}$ is the total
power at the transmitter.

$\mathcal{P}_{1}$ is convex and can be directly solved via convex optimization
tools. In [38], the authors derive the optimal solution structure of the
precoding matrix. For the $n$-th symbol slot, the precoding matrix can be
expressed as

$\displaystyle{\bf W}^{(n)}$ $\displaystyle=$ (20)
$\displaystyle\frac{1}{K}\cdot{{\bf{H}}^{H}}{\left({{\bf{H}}{{\bf{H}}^{H}}}\right)^{-1}}{\bf{U}}diag\left({\bf\Omega}^{(n)}\right){\bf
s}_{\bf E}^{(n)}\left({{{\bf{\hat{s}}}}^{(n)}}\right)^{T},$

where
${\bf\Omega}^{(n)}=\left[\alpha_{1,\mathcal{A}}^{(n)},\alpha_{1,\mathcal{B}}^{(n)},\cdots,\alpha_{K,\mathcal{A}}^{(n)},\alpha_{K,\mathcal{B}}^{(n)}\right]^{T}\in\mathbb{R}^{2K\times
1}$ is the symbol-scaling factors for the $n$-th symbol slot, ${\bf
H}\in\mathbb{C}^{K\times M_{\mathrm{t}}}$ is the channel matrix,
${\bf{\hat{s}}}^{(n)}\in\mathbb{C}^{K\times 1}$, ${\bf
U}\in\mathbb{R}^{K\times 2K}$ and ${\bf s}_{\bf
E}^{(n)}\in\mathbb{C}^{2K\times 1}$ are given by

${\bf{\hat{s}}}^{(n)}=\left[\frac{1}{{\bf s}_{1}^{(n)}},\frac{1}{{\bf
s}_{2}^{(n)}},\cdots,\frac{1}{{\bf
s}_{K}^{(n)}}\right]^{T}\in\mathbb{C}^{K\times 1},$ (21) ${\bf U}={\bf
I}_{K}\otimes[1,1],$ (22) ${\bf s}_{\bf E}^{(n)}={\left[s_{1,\cal
A}^{(n)},s_{1,\cal B}^{(n)},s_{2,\cal A}^{(n)},s_{2,\cal
B}^{(n)},\cdots,s_{K,\cal A}^{(n)},s_{K,\cal B}^{(n)}\right]^{T}}.$ (23)

When we obtain ${\bf\Omega}^{(n)}$, the optimal precoding matrix can be
directly obtained by using the (20). Therefore, the key issue is how to
efficiently compute the symbol-scaling factors with low complexity. In [38],
the authors utilize the Lagrangian dual and Karush-Kuhn-Tucker (KKT)
conditions to transform the original problem $\mathcal{P}_{1}$ into simpler
forms. More specifically, the original optimization problem can be simplified
into

$\displaystyle\mathcal{P}_{2}:{\kern
3.0pt}\mathop{\min}\limits_{{{\bf\Omega}^{(n)}},{\kern 1.0pt}t}{\kern
3.0pt}-t$ (24) $\displaystyle{\kern 0.0pt}s.t.{\kern
10.0pt}{({\bf\Omega}^{(n)})}^{T}{\bf V}_{n}{\bf\Omega}^{(n)}-p_{0}=0,$
$\displaystyle{\kern 24.0pt}t-\alpha_{i}^{\cal O}\leq 0,{\kern
3.0pt}\forall\alpha_{i}^{\cal O}\in{\cal O}^{(n)},$

where ${\bf V}_{n}\in\mathbb{R}^{2K\times 2K}$ is dependent on both CSI and
data symbols and can be expressed as

${\bf V}_{n}=\Re\left({\bf T}_{n}\right),$ (25) ${\bf T}_{n}={diag\left(({\bf
s}_{\bf E}^{(n)})^{H}\right){\bf Q}_{n}diag\left({{\bf s}_{\bf
E}^{(n)}}\right)},$ (26) ${\bf
Q}_{n}={{\bf{U}}^{H}}{{\left({{\bf{H}}{{\bf{H}}^{H}}}\right)}^{-1}}{\bf{U}},$
(27)

where the details can be found in [38]. The optimization $\mathcal{P}_{3}$ on
${\bf\Omega}^{(m)}$ for the $m$-th symbol slot is in the same form as
$\mathcal{P}_{2}$ above.

Within one transmission block, we exploit the relationships between the $n$-th
symbol slot and the $m$-th symbol slot to connect $\mathcal{P}_{2}$ and
$\mathcal{P}_{3}$. Based on the diagonal transformation matrix ${\bf A}$
between the $n$-th symbol slot and $m$-th symbol slot in (18), we employ ${\bf
A}$ to extrapolate ${\bf V}_{m}$ from the matrix ${\bf V}_{n}$, thereby
establishing the connection of the precoding matrix between the two symbol
slots to reduce the complexity. The relationship between ${\bf V}_{n}$ and
${\bf V}_{m}$ can be expressed as

${\bf s}_{\bf E}^{(m)}=\left({{\bf A}\otimes{\bf I}_{2}}\right){\bf s}_{\bf
E}^{(n)},$ (28)

${\bf T}_{m}=\left({{\bf A}\otimes{\bf I}_{2}}\right)^{H}{\bf
T}_{n}\left({{\bf A}\otimes{\bf I}_{2}}\right),$ (29)

${\bf V}_{m}=\Re\left({\bf T}_{m}\right).$ (30)

Based on the above derivations and the specific solution structure of the
precoding matrix in (20), we get an optimal solution structure based on
symbol-level extrapolation from the $n$-th symbol slot to $m$-th symbol slot,
given by

$\displaystyle{\bf W}^{(m)}=$ (31)
$\displaystyle\frac{1}{K}\cdot{{\bf{H}}^{H}}{\left({{\bf{H}}{{\bf{H}}^{H}}}\right)^{-1}}{\bf{U}}diag\left(\mathcal{F}_{1}\left(\
{\bf V}_{n}\right)\right)({{\bf A}\otimes{\bf I}_{2}}){\bf s}_{\bf
E}^{(n)}\left({{{\bf{\hat{s}}}}^{(m)}}\right)^{T},$

where the $\mathcal{F}_{1}\left(\ {\bf V}_{n}\right)\in\mathbb{R}^{2K\times
1}$ represent the mapping function between ${\bf V}_{n}$ and
${{\bf\Omega}^{(m)}}$.

Next, we will discuss how to calculate the symbol-scaling factors
${\bf\Omega}^{m}$ for the $m$-th symbol slot using the extrapolated matrix
${\bf V}_{m}$. When the problem $\mathcal{P}_{3}$ achieves the optimal
solution for the $m$-th symbol slot, the BS transmits at its maximum power and
we can obtain

$({{\bf\Omega}^{(m)}})^{T}{\bf V}_{m}{\bf\Omega}^{(m)}-p_{0}=0.$ (32)

Based on this formula, we define a power normalization factor described as

$f^{m}_{\mathrm{nor}}=\sqrt{({{\bf\Omega}^{(m)}})^{T}{\bf
V}_{m}{\bf\Omega}^{(m)}}.$ (33)

We further introduce ${\bf\Omega}^{(m)}_{\mathrm{fin}}\in\mathbb{R}^{2K\times
1}$ to represent the symbol-scaling factors that satisfy the power constraint
for the optimization problem. The relationship between
${\bf\Omega}^{(m)}_{\mathrm{fin}}$ and ${\bf\Omega}^{(m)}$ can be given by

${\bf\Omega}^{(m)}_{\mathrm{fin}}=\sqrt{p_{0}}\frac{{\bf\Omega}^{(m)}}{f^{m}_{\mathrm{nor}}}.$
(34)

Then we can expand (32) for the $m$-th symbol slot as

$\displaystyle({\bf\Omega}^{(m)})^{T}{\bf V}_{m}{\bf\Omega}^{(m)}=$ (35)
$\displaystyle\sum_{j=1}^{2K}\sum_{i=1,i\neq j}^{2K}({{\bf
V}_{m,i,i}({\bf\Omega}^{(m)}_{i})^{2}}+{\bf
V}_{m,i,j}{{\bf\Omega}^{(m)}_{i}}{{\bf\Omega}^{(m)}_{j}})+{p}_{0},$

where ${\bf\Omega}^{(m)}_{i}$ represents the $i$-th element in
${\bf\Omega}^{(m)}$. (35) is a series of equations presented in a matrix form,
which can be observed as the sum of $2K$ one-variable quadratic equations.
Based on this observation, a closed-form iterative algorithm is proposed.

Algorithm 1 SLE-CF-PSK Algorithm

${\bf input:}$ ${\bf H}$, ${\mathcal{M}}$, ${\bf s}^{(n)}$, ${\bf s}^{(i)}$,
${M_{\mathrm{t}}}$, ${K}$, $R$, $N_{\mathrm{s}}$

${\bf output:}$ ${\bf W}_{i},i=1,2,\cdots,N_{\mathrm{s}}$

${\bf U}={\bf I}_{M_{t}}\otimes[1,1]$;

Calculate ${\bf s}_{\bf E}^{(n)}$ using the (9), (10) and (23);

Calculate ${\bf V}_{n}$ using (25);

for $i=1:N_{\mathrm{s}}$ do

Initial ${\bf\Omega}^{(i)}={\bf 1}$, $n=0$;

Obtain the ${\bf A}$ between the ${\bf s}^{(i)}$ and ${\bf s}^{(n)}$;

Obtain the ${\bf T}_{i}$ and ${\bf V}_{i}$ using the (29) and (30);

while $n<R$ do

${\bf q}^{(i)}={\bf V}_{i}{\bf\Omega}^{(i)}$;

$a=min({\bf q}^{(i)})$;

if $a<0$ then

Find the $index$ of $a$ in the ${\bf q}^{(i)}$;

Update the ${\bf\Omega}_{index}^{(i)}$ using (37);

$n=n+1$;

else

break

end if

end while

Update ${\bf\Omega}_{\mathrm{fin}}^{(i)}$ using the (33) and (34);

Obtain ${\bf W}^{(i)}$ using the (31);

end for

To be more specific, we initialize the symbol-scaling factors
${\bf\Omega}^{(m)}={\bf 1}\in\mathbb{R}^{2K\times 1}$. In order to approach
the optimal solution as closely as possible, we update only one symbol-scaling
factor in each iteration. According to the (29) and (30), We introduce ${\bf
q}^{(m)}\in\mathbb{R}^{2K\times 1}$ that can be expressed as

${\bf q}^{(m)}=\Re\left(\left({{\bf A}\otimes{\bf I}_{2}}\right)^{H}{\bf
T}_{n}\left({{\bf A}\otimes{\bf I}_{2}}\right)\right){\bf\Omega}^{(m)}.$ (36)

The index of the symbol-scaling factor is determined by the index of $min({\bf
q})$. In an iteration where we assume that the $k$-th symbol-scaling factor
for the $m$-th symbol slot is updated, the update formula is expressed as

${\bf\Omega}^{(m)}_{k}=-\frac{\sum_{j\neq k,j=1}^{2K}{\bf
V}_{m,k,j}{\bf\Omega}^{(m)}_{j}}{{\bf V}_{m,k,k}}.$ (37)

When the algorithm reaches its specified iteration number or $min({\bf
q}^{(m)})>0$, the iteration process terminates. It is important to note that
the ${\bf q}^{(m)}$ will also be updated in each iteration. Finally, we
normalize ${\bf\Omega}^{(m)}$ to satisfy the power constraint by using the
(33) and (34) to obtain
${\bf\Omega}^{(m)}_{\mathrm{fin}}\in\mathbb{R}^{2K\times 1}$.

Within one transmission block, we assume that the maximum number of symbol
slots is $N_{\mathrm{s}}$, the number of iterations is $R$, ${\bf
s}^{(i)}\in\mathbb{C}^{K\times 1}$ represents the data symbol vector for
$i$-th symbol slot. The ${\bf\Omega}_{index}^{(i)}$ denotes that the
$index$-th symbol-scaling factor is selected to update in the $i$-th symbol
slot. From the $n$-th symbol slot, we extrapolate the precoding matrices for
all symbol slots. The closed-form iterative algorithm, based on symbol-level
extrapolation, is presented in Algorithm 1.

The proposed ‘SLE-CF-PSK’ iterative algorithm updates only one symbol-scaling
factor at each iteration, and is able to extrapolate a near-optimal
performance, which will be shown numerically in Section VI. To further reduce
the complexity, we design a sub-optimal closed-form solution based on SLE to
update all symbol-scaling factors simultaneously. The sub-optimal algorithm
begins by initializing the symbol-scaling factors ${\bf\Omega}^{(m)}={\bf
1}\in\mathbb{R}^{2K\times 1}$. Then the symbol-scaling factors
${\bf\Omega}^{(m)}_{\mathrm{sub}}\in\mathbb{R}^{2K\times 1}$ for the $m$-th
symbol slot are updated based on the following principle:

${\bf\Omega}^{(m)}_{\mathrm{sub}}=max\left(-\frac{{\bf
V}_{m}{\bf\Omega}^{(m)}-diag({\bf V}_{m})}{2diag({\bf V}_{m})},1\right)$ (38)

Then, we get the final magnitude of the symbol-scaling factor
${\bf\Omega}^{(m)}_{\mathrm{sub,fin}}\in\mathbb{R}^{2K\times 1}$ by
substituting ${\bf\Omega}^{(m)}_{\mathrm{sub}}$ into the (28) and (29). The
closed-form sub-optimal algorithm is presented in Algorithm 2.

Algorithm 2 SLE-Sub-PSK Algorithm

${\bf input:}$ ${\bf H}$, ${\mathcal{M}}$, ${\bf s}^{(n)}$, ${\bf s}^{(i)}$,
${M_{\mathrm{t}}}$, ${K}$, $R$, $N_{\mathrm{s}}$

${\bf output:}$ ${\bf W}_{i},i=1,2,\cdots,N_{\mathrm{s}}$

${\bf U}={\bf I}_{M_{t}}\otimes[1,1]$;

Calculate ${\bf s}_{\bf E}^{(n)}$ using the (9), (10) and (23);

Calculate ${\bf V}_{n}$ using (25);

for $i=1:N_{\mathrm{s}}$ do

Initial ${\bf\Omega}^{(i)}={\bf 1}$;

Obtain the ${\bf A}$ between the ${\bf s}^{(i)}$ and ${\bf s}^{(n)}$;

Obtain the ${\bf T}_{i}$ and ${\bf V}_{i}$ using the (29) and (30);

Obtain the ${\bf\Omega}^{(i)}_{\mathrm{sub}}$

Update ${\bf\Omega}^{(i)}_{\mathrm{sub,fin}}$ using the (33) and (34);

Obtain ${\bf W}^{(i)}$ using the (31);

end for

###  III-B The case of $\mathcal{M}$-QAM

Based on the symbol-scaling metric in [38], the optimization problem that
maximizes the CI effect using QAM modulation for the $n$-th symbol slot is
give by

$\displaystyle\mathcal{P}_{4}:{\kern
3.0pt}\mathop{\max}\limits_{{{\bf{W}}_{n}},{\kern 1.0pt}t}{\kern 3.0pt}t$ (39)
$\displaystyle{\kern 0.0pt}s.t.{\kern 10.0pt}{{\bf{h}}_{k}^{T}}{{\bf
W}_{n}{\bf
s}^{(n)}}=\alpha_{k,\mathcal{A}}^{(n)}s_{k,\mathcal{A}}^{(n)}+\alpha_{k,\mathcal{B}}^{(n)}s_{k,\mathcal{B}}^{(n)},{\kern
3.0pt}\forall k\in{\cal K},$ $\displaystyle{\kern 24.0pt}t\leq\alpha_{i}^{\cal
O},{\kern 3.0pt}\forall\alpha_{i}^{\cal O}\in{\cal O}^{(n)},$
$\displaystyle{\kern 24.0pt}t=\alpha_{j}^{\cal I},{\kern
3.0pt}\forall\alpha_{j}^{\cal I}\in{\cal I}^{(n)},$ $\displaystyle{\kern
22.0pt}\left\|{{\bf{W}}_{n}{\bf s}^{(n)}}\right\|_{2}^{2}\leq{p_{0}},$

where $\mathcal{K}=\left\\{{1,2,\cdots,K}\right\\}$, $\alpha_{i}^{\cal O}$
represents the $i$-th element in set ${\cal O}^{(n)}$, $\alpha_{j}^{\cal I}$
represents the $j$-th element in set ${\cal I}^{(n)}$, $p_{0}$ is the total
power at the transmitter. It is easy to verify that $\mathcal{P}_{4}$ is
convex and can be directly solved via convex optimization tools. In [38], the
authors derive the optimal solution structure of the precoding matrix. For the
$n$-th symbol slot, the precoding matrix can be expressed as

$\displaystyle{\bf W}^{(n)}$ $\displaystyle=$ (40)
$\displaystyle\frac{1}{K}\cdot{{\bf{H}}^{H}}{\left({{\bf{H}}{{\bf{H}}^{H}}}\right)^{-1}}{\bf{U}}diag\left({\bf\Omega}^{(n)}\right){\bf
s}_{\bf E}^{(n)}\left({{{\bf{\hat{s}}}}^{(n)}}\right)^{T}.$

where ${{\bf{\hat{s}}}^{(n)}}$, ${\bf U}$ and ${\bf s}_{\bf E}^{(n)}$ can be
obtained by using the (21), (22) and (23). Therefore, how to efficiently
compute the symbol-scaling factors with low complexity is important for CI-SLP
design.

When we obtain ${\bf\Omega}^{(n)}$, the optimal precoding matrix can be
directly obtained by using the (40). Therefore, the key issue is how to
efficiently compute the symbol-scaling factors with low complexity. In [38],
the authors utilize the Lagrangian dual and KKT conditions to transform the
original problem $\mathcal{P}_{3}$ into simpler forms. More specifically, the
original optimization problem can be simplified into

$\displaystyle\mathcal{P}_{5}:{\kern
3.0pt}\mathop{\min}\limits_{{{\bf\Omega}^{(n)}},{\kern 1.0pt}t}{\kern
3.0pt}-t$ (41) $\displaystyle{\kern 0.0pt}s.t.{\kern
10.0pt}({{\bf\Omega}^{(n)}})^{T}{\bf V}_{n}{\bf\Omega}^{(n)}-p_{0}=0,$
$\displaystyle{\kern 24.0pt}t-{\bf\Omega}_{i}^{(n)}\leq 0,{\kern 3.0pt}\forall
i\in{\cal K},$ $\displaystyle{\kern 24.0pt}t-\alpha_{i}^{\cal O}\leq 0,{\kern
3.0pt}\forall\alpha_{i}^{\cal O}\in{\cal O}^{(n)},$ $\displaystyle{\kern
24.0pt}t-\alpha_{j}^{\cal I}=0,{\kern 3.0pt}\forall\alpha_{j}^{\cal I}\in{\cal
I}^{(n)},$

where the ${\bf V}_{n}$ can be obtained by using the (25). The optimization
$\mathcal{P}_{6}$ on ${\bf\Omega}^{(m)}$ for the $m$-th symbol slot is in the
same form as $\mathcal{P}_{5}$ above.

Within one transmission block, we exploit the relationships between the $n$-th
symbol slot and the $m$-th symbol slot to connect $\mathcal{P}_{5}$ and
$\mathcal{P}_{6}$. We employ ${\bf Q}_{n}$ from the $n$-th symbol slot to
extrapolate ${\bf V}_{m}$, thereby establishing the connection of the
precoding matrix between the two symbol slots to reduce the complexity. The
relationship between ${\bf Q}_{n}$ and ${\bf V}_{m}$ can be expressed as

${\bf V}_{m}=\Re\left({\bf T}_{m}\right),$ (42) ${\bf T}_{m}={diag\left(({\bf
s}_{\bf E}^{(m)})^{H}\right){\bf Q}_{n}diag\left({{\bf s}_{\bf
E}^{(m)}}\right)}.$ (43)

Based on the above derivations and the specific solution structure of
precoding matrix in (40), we get an optimal solution structure based on
symbol-level extrapolation from the $n$-th symbol slot to $m$-th symbol slot,
given by

$\displaystyle{\bf W}^{(m)}$ $\displaystyle=$ (44)
$\displaystyle\frac{1}{K}\cdot{{\bf{H}}^{H}}{\left({{\bf{H}}{{\bf{H}}^{H}}}\right)^{-1}}{\bf{U}}diag\left(\mathcal{F}_{2}\left(\
{\bf Q}_{n}\right)\right){\bf s}_{\bf
E}^{(m)}\left({{{\bf{\hat{s}}}}^{(m)}}\right)^{T},$

where the $\mathcal{F}_{2}\left(\ {\bf Q}_{n}\right)\in\mathbb{R}^{2K\times
1}$ represent the mapping function between ${\bf Q}_{n}$ and
${{\bf\Omega}^{(m)}}$.

Next, we will describe how to utilize the matrix ${\bf V}_{m}$ to determine
the symbol-scaling factors ${\bf\Omega}^{(m)}$. QAM modulation can be
considered as an extension in terms of the PSK modulation. Therefore, we can
extend the SLE-CF-PSK algorithm to QAM modulation considering the case where
the set ${\cal I}^{(m)}$ is not empty. We assume that the ${\cal
D}^{(m)}\in\mathbb{R}^{card\left|{\cal I}^{(m)}\right|\times 1}$ is the index
set corresponds to the set ${\cal I}^{(m)}$, and the ${\cal
L}^{(m)}\in\mathbb{R}^{card\left|{\cal O}^{(m)}\right|\times 1}$ is the index
set corresponds to the set ${\cal O}^{(m)}$.

To be more specific, we initialize the symbol-scaling factors
${\bf\Omega}^{(m)}={\bf 1}\in\mathbb{R}^{2K\times 1}$. In order to approach
the optimal solution as closely as possible, we update only one symbol-scaling
factor in each iteration. According to the (42) and (43), We introduce ${\bf
q}^{(m)}\in\mathbb{R}^{2K\times 1}$ and ${\bf q}^{(m)}_{\cal
L}\in\mathbb{R}^{card\left|{\cal O}^{(m)}\right|\times 1}$ that can be
expressed as

${\bf q}^{(m)}=\Re\left\\{{diag\left(({\bf s}_{\bf E}^{(m)})^{H}\right){\bf
Q}_{n}diag\left({{\bf s}_{\bf E}^{(m)}}\right)}\right\\}{\bf\Omega}^{(m)},$
(45)

and

${\bf q}^{(m)}_{\cal L}={\bf q}^{(m)}\left({\cal
L}^{(m)}\right)\in\mathbb{R}^{card\left|{\cal O}^{(m)}\right|\times 1}.$ (46)

The index of the symbol-scaling factor is determined by the index of $min({\bf
q}^{(m)}_{\cal L})$. In an iteration where we assume that the $k$-th symbol-
scaling factor for the $m$-th symbol slot is updated, the update formula is
expressed as

${\bf\Omega}^{(m)}_{k}=-\frac{\sum_{j\neq k,j=1}^{2K}{\bf
V}_{m,k,j}{\bf\Omega}^{(m)}_{j}}{{\bf V}_{m,k,k}}.$ (47)

When the iteration reaches its iteration number or $min({\bf q}_{\cal
L}^{(m)})>0$, the iteration process terminates. Finally, we normalize
${\bf\Omega}^{(m)}$ to satisfy the power constraint by using the (33) and (34)
to obtain the ${\bf\Omega}^{(m)}_{\mathrm{fin}}\in\mathbb{R}^{2K\times 1}$.

Within one transmission block, we assume that the maximum number of symbol
slots is $N_{\mathrm{s}}$, the number of iterations is $R$, ${\bf
s}^{(i)}\in\mathbb{C}^{K\times 1}$ represents the data symbol vector for
$i$-th symbol slot. The ${\bf\Omega}_{index}^{(i)}$ denotes that the
$index$-th symbol-scaling factor is selected to update in the $i$-th symbol
slot. From the $n$-th symbol slot, we extrapolate the precoding matrices for
all symbol slots. The closed-form iterative algorithm, based on symbol-level
extrapolation, is presented in Algorithm 3.

Algorithm 3 SLE-CF-QAM Algorithm

${\bf input:}$ ${\bf H}$, ${\bf s}^{(n)}$, ${\bf s}^{(i)}$,
${M_{\mathrm{t}}}$, ${K}$, $R$, $N_{\mathrm{s}}$

${\bf output:}$ ${\bf W}_{i},i=1,2,\cdots,N_{\mathrm{s}}$

${\bf U}={\bf I}_{M_{t}}\otimes[1,1]$;

Calculate ${\bf s}_{\bf E}^{(n)}$ using the (15) and (23);

Calculate ${\bf V}_{n}$ using the (25);

for $i=1:N_{\mathrm{s}}$ do

Initial ${\bf\Omega}^{(i)}={\bf 1}$, $n=0$;

Obtain the ${\bf A}$ between the ${\bf s}^{(i)}$ and ${\bf s}^{(n)}$;

Obtain the ${\bf T}_{i}$ and ${\bf V}_{i}$ using (42) and (43);

if ${\bf{q}}^{(m)}_{\mathcal{L}}\neq\emptyset$ then

while $n<R$ do

${\bf q}^{(m)}={\bf V}_{i}{\bf\Omega}^{(i)}$;

Obtain ${\bf{q}}^{(i)}_{\mathcal{L}}$ using (46)

$a=min({\bf{q}}^{(i)}_{\mathcal{L}})$;

if $a<0$ then

Find the $index$ of $a$ in the ${\bf{q}}^{(m)}_{\mathcal{L}}$;

Update the ${\bf\Omega}_{index}^{(i)}$ using (47);

$n=n+1$;

else

break

end if

end while

end if

Update ${\bf\Omega}^{(i)}_{\mathrm{fin}}$ using the (33) and (34);

Obtain ${\bf W}^{(i)}$ using the (44);

end for

The proposed ‘SLE-CF-QAM’ iterative algorithm updates only one symbol-scaling
factor at each iteration, and is able to extrapolate a near-optimal
performance, which will be shown numerically in Section VI. To further reduce
the complexity, we design a sub-optimal closed-form solution based on SLE to
update all symbol-scaling factors simultaneously. The sub-optimal algorithm
begins by initializing the symbol-scaling factors ${\bf\Omega}^{(m)}={\bf
1}\in\mathbb{R}^{2K\times 1}$. Then the symbol-scaling factors
${\bf\Omega}^{(m)}_{\mathrm{sub}}\in\mathbb{R}^{2K\times 1}$ for the $m$-th
symbol slot are updated based on the following principle:

${\bf\Omega}^{(m)}_{\mathrm{sub}}=max\left(-\frac{{\bf
V}_{m}{\bf\Omega}^{(m)}-diag({\bf V}_{m})}{2diag({\bf V}_{m})},1\right),$ (48)

and

${\bf\Omega}^{(m)}_{\mathrm{sub}}\left(\mathcal{D}^{(m)}\right)={\bf 1}.$ (49)

Then, we get the final magnitude of the symbol-scaling factors
${\bf\Omega}^{(m)}_{\mathrm{sub},\mathrm{fin}}\in\mathbb{R}^{2K\times 1}$ by
substituting ${\bf\Omega}^{(m)}_{\mathrm{sub}}$ into the (33) and (34). The
closed-form sub-optimal algorithm is presented in Algorithm 4.

Algorithm 4 SLE-Sub-QAM Algorithm

${\bf input:}$ ${\bf H}$, ${\bf s}^{(n)}$, ${\bf s}^{(i)}$,
${M_{\mathrm{t}}}$, ${K}$, $R$, $N_{\mathrm{s}}$

${\bf output:}$ ${\bf W}_{i},i=1,2,\cdots,N_{\mathrm{s}}$

${\bf U}={\bf I}_{M_{t}}\otimes[1,1]$;

Calculate ${\bf s}_{\bf E}^{(n)}$ using the (15) and (23);

Calculate ${\bf V}_{n}$ using the (25);

for $i=1:N_{\mathrm{s}}$ do

Initial ${\bf\Omega}^{(i)}={\bf 1}$;

Obtain the ${\bf A}$ between the ${\bf s}^{(i)}$ and ${\bf s}^{(n)}$;

Obtain the ${\bf T}_{i}$ and ${\bf V}_{i}$ using (42) and (43);

Obtain the ${\bf\Omega}^{(i)}_{\mathrm{sub}}$ using the (48) and (49);

Update ${\bf\Omega}^{(i)}_{\mathrm{sub,fin}}$ using the (33) and (34);

Obtain ${\bf W}^{(i)}$ using the (44);

end for

##  IV Deep Unfolding for SLE-based Iterative algorithm

To reduce complexity while maintaining the performance, we employ the deep
unfolding to expand the iterative algorithm and construct the SLE-Net. This
approach leverages the parallel processing capability of GPUs to decrease time
complexity. We introduce a deep unfolding framework which can be applicable to
both PSK and QAM modulation. Essentially, QAM modulation can be considered as
an extension of PSK modulation for the network. Therefore, below we choose the
QAM modulation as the example to describe our network.

Figure 3: the diagram of the SLE-Net

###  IV-A Network Architecture

The overall framework of the network is illustrated in Fig. 3 and can be
divided into three parts. In the first part, data initialization is performed.
Given the CSI and the data symbol vectors, we aim to extrapolate the matrices
${\bf V}$ and get the matrix ${\bf O}\in\mathbb{R}^{2K\times N_{\mathrm{s}}}$,
which is an indicator matrix that shows whether symbol-scaling factors can be
scaled for all the symbol slots. For convenience of description, we illustrate
the extrapolation process for the $m$-th symbol slot as an example.
${\bf\Omega}^{(m),0}={\bf 1}\in\mathbb{R}^{2K\times 1}$ represent the initial
symbol-scaling factors. Based on the definition, ${\bf
O}^{(m)}\in\mathbb{R}^{2K\times 1}$ represents $m$-th vector in matrix ${\bf
O}$ to indicate whether symbol-scaling factors can be scaled for the $m$-th
symbol slot, whose the expression is given by

${\bf O}_{i}^{(m)}=\left\\{\begin{array}[]{ll}1,i\in\mathcal{O}^{(m)},\\\
0,i\in\mathcal{I}^{(m)}.\end{array}\right.$ (50)

The second part consists of iterative unfolding layers, where the number of
layers in the network corresponds to the iteration numbers of the SLE-CF-QAM
algorithm. Specifically, the following updates are used for $r=1,2,\cdots,R$:

${\bf\Omega}^{(m),r}={\bf g}(-{\bf V}{\bf\Omega}^{(m),r-1})\odot{\bf
O}^{(m)}\odot{\mathbf{\tau}}_{r-1}+b_{r-1}{\bf\Omega}^{(m),r-1},$ (51)

where ${\bf\Omega}^{(m),r}\in\mathbb{R}^{2K\times 1}$ represents the symbol-
scaling factors after the $r$-th iteration, $b_{r}\in\mathbb{R}$ and
${\mathbf{\tau}}_{r}\in\mathbb{R}^{2K\times 1}$ represents the learning
parameters in the $r$-th iterative unfolding layer, ${\bf g}$ is the
activation function and can be expressed as

${\bf g}({\bf x})=max({\bf x},{\bf 0}).$ (52)

The third part involves normalizing the symbol-scaling factors to meet the
power constraint at the BS, and then substituting the symbol-scaling factors
into the closed-form solution to obtain the final precoding matrix.

###  IV-B Training the Network

Training deep networks is a difficult task due to the issues of vanishing
gradients, saturation of the activation functions, sensitivity to
initialization[39]. Based on the simplified original optimization problem
$\mathcal{P}_{6}$, we design an unsupervised loss function to maximize the CI
effects by staying away from the detection threshold, transforming the network
from data-driven to model-driven, which helps enhance the interpretability of
the network. We assume that the output of the network is
${\bf\hat{y}}_{n}\in\mathbb{R}^{2K\times 1}$ for the $n$-th sample, the loss
function can be expressed as

$loss=-\frac{1}{N}\sum_{n=1}^{N}min({\bf\hat{y}}_{n}),$ (53)

where $N$ is the batchsize, ${\bf\hat{y}}_{n}$ denotes the output of the
$n$-th training sample. The loss function is minimized by the adaptive moment
estimation (ADAM) algorithm in [40] until the network converges. The SLE-Net
algorithm is presented in Algorithm 5.

Algorithm 5 SLE-Net Algorithm

${\bf input:}$ ${\bf H}$, ${\bf s}^{(n)}$, ${\bf s}^{(i)}$,
${M_{\mathrm{t}}}$, ${K}$, $R$, $N_{\mathrm{s}}$, epoch numbers $E$, learning
rate $\gamma$, batchsize $N$

${\bf output:}$ ${\bf W}_{i},i=1,2,\cdots,N_{\mathrm{s}}$

for $e=1:E$ do

Update the parameters (learning rate $\gamma$) by using the ADAM algorithm to
minimize the loss;

end for

${\bf U}={\bf I}_{M_{t}}\otimes[1,1]$;

if $\mathcal{M}$-QAM then

Calculate ${\bf s}_{\bf E}^{(n)}$ using the (15) and (23);

else

Calculate ${\bf s}_{\bf E}^{(n)}$ using the (9), (10) and (23);

end if

Calculate ${\bf V}_{n}$ using the (25);

for $i=1:N_{\mathrm{s}}$ do

Initial ${\bf\Omega}^{(i)}={\bf 1}$, $n=0$;

Obtain the ${\bf O}^{(i)}$ using the (50);

Obtain the ${\bf A}$ between the ${\bf s}^{(i)}$ and ${\bf s}^{(n)}$;

if $\mathcal{M}$-QAM then

Obtain the ${\bf T}_{i}$ and ${\bf V}_{i}$ using (42) and (43);

else

Obtain the ${\bf T}_{i}$ and ${\bf V}_{i}$ using (29) and (30);

end if

Obtain the ${\bf\Omega}^{(i)}_{\mathrm{net}}$;

if $\mathcal{M}$-QAM then

Obtain ${\bf W}^{(i)}$ by using (44);

else

Obtain ${\bf W}^{(i)}$ by using (31);

end if

end for

##  V Complexity Analysis

In this section, we evaluate the complexity of the proposed algorithm in terms
of the required number of multiplications and additions. For the purpose of
simplifying the analysis, we evaluate the complexity in terms of the required
complex number multiplication and addition operations. In the application
scenario of this paper, we assume that the number of antennas $M_{\mathrm{t}}$
at the transmitter is equal to the number of users $K$. Within one
transmission block, we assume that the number of symbol slots for transmission
is $N_{\mathrm{s}}$, and the number of iterations is $R$. We have proposed
algorithms for both PSK and QAM modulation schemes. Therefore, we first
analyze the complexity of the PSK algorithm and subsequently extend the
results to QAM algorithm.

Based on the rules of matrix inversion and multiplication operations, the
complexity of ${\bf H}^{H}{({\bf H}{\bf H}^{H})}^{-1}$ is
$\mathcal{O}(5K^{3}-K^{2}+K)$. The complexity of ZF precoding for
$N_{\mathrm{s}}$ symbol slots is given by

$\mathcal{O}_{\mathrm{ZF}}=(5K^{3}+2K^{2})N_{\mathrm{s}}.$ (54)

###  V-A Complexity of SLE-Sub-PSK and SLE-CF-PSK

Whether it is an iterative algorithm or a sub-optimal closed-form algorithm
for PSK modulation in this paper, the overall complexity of the algorithm can
be divided into three parts within a transmission block. The first part
involves the extrapolation of the matrix ${\bf V}$ and the vector ${\bf
s}_{\bf E}$ for all symbol slots. The second part is to calculate the symbol-
scaling factors based on the matrix ${\bf V}$. The third part is the
normalization of the obtained symbol-scaling factors, substituting symbol-
scaling factors into the (31) to get the precoding matrix.

According to the formula (28), (29) and (30), the complexity to extrapolate
the matrix ${\bf V}$ and the vector ${\bf s}_{\bf E}$ for $N_{\mathrm{s}}$
symbol slots is given by

$\mathcal{O}_{\mathrm{e}}=3K^{3}+(8N_{\mathrm{s}}+4)K^{2}+(5N_{\mathrm{s}}+3)K.$
(55)

For the sub-optimal SLE-Sub-PSK algorithm, the complexity of the formula (38)
to calculate the symbol-scaling factors for $N_{\mathrm{s}}$ symbol slots is
given by

$\mathcal{O}_{\mathrm{sub}}=(8K^{2}+4K)N_{\mathrm{s}}.$ (56)

For the SLE-CF-PSK algorithm, the complexity to calculate the symbol-scaling
factors through $R$ iterations for $N_{\mathrm{s}}$ symbol slots is given by

$\mathcal{O}_{\mathrm{i}}=(8K^{2}+5K+1)RN_{\mathrm{s}}.$ (57)

Next, the complexity of the third part to normalize the symbol-scaling factors
and substitute them into the formula (31) to calculate the precoding matrix
for $N_{\mathrm{s}}$ symbol slots is given by

$\mathcal{O}_{\mathrm{n}}=(9K^{3}+13K^{2}+7K-1)N_{\mathrm{s}}.$ (58)

Based on the above analysis, we can obtain the overall complexity of the SLE-
Sub-PSK and SLE-CF-PSK within one transmission block as follows

$\displaystyle\mathcal{O}_{\mathrm{sub}}^{\mathrm{psk}}$
$\displaystyle=\mathcal{O}_{\mathrm{e}}+\mathcal{O}_{\mathrm{sub}}+\mathcal{O}_{\mathrm{n}}$
(59)
$\displaystyle=(9N_{\mathrm{s}}+3)K^{3}+(29N_{\mathrm{s}}+4)K^{2}+(16N_{\mathrm{s}}+3)K-N_{\mathrm{s}},$

$\displaystyle\mathcal{O}_{\mathrm{ite}}^{\mathrm{psk}}$
$\displaystyle=\mathcal{O}_{\mathrm{e}}+\mathcal{O}_{\mathrm{i}}+\mathcal{O}_{\mathrm{n}}$
(60)
$\displaystyle=(9N_{\mathrm{s}}+3)K^{3}+(21N_{\mathrm{s}}+8RN_{\mathrm{s}}+4)K^{2}$
$\displaystyle+(12N_{\mathrm{s}}+5RN_{\mathrm{s}}+3)K+(R-1)N_{\mathrm{s}}.$

The complexity of optimization problems $\mathcal{P}_{1}$ when using interior-
point methods to solve is influenced by the requirement of the accuracy
$\varepsilon$ and the number of constraints. According to [22], The complexity
of the $\mathcal{P}_{1}$ can be approximately expressed as

$\displaystyle\mathcal{O}_{\mathrm{opt}}$ $\displaystyle=[28K^{3}+49K^{2}+4K$
(61)
$\displaystyle+\ln(\frac{2K^{2}+12K+2}{\varepsilon})(K+2)^{0.5}(2K^{3}+3K^{3}+2K)]N_{\mathrm{s}}.$

The complexity of the conventional algorithm in [22], denoted as the CI-CF-
PSK, can be given by

$\mathcal{O}_{\mathrm{ci}}=(28K^{3}+49K^{2}+4K+\sum_{r=0}^{R}(2r^{2}+3r+1))N_{\mathrm{s}}.$
(62)

###  V-B Complexity of SLE-Net

We assume that the number of iteration unfolding layers is equal to the number
of iterations $R$. As described earlier, it is known that the network consists
of three parts. For the SLE-Net algorithm, the complexity of the first part
and the third part are approximately equal to the $\mathcal{O}_{\mathrm{e}}$
and $\mathcal{O}_{\mathrm{n}}$. The complexity of the iteration unfolding
layers for $N_{\mathrm{s}}$ symbol slots is given by

$\mathcal{O}_{\mathrm{d}}=(8K^{2}+6K)RN_{\mathrm{s}}.$ (63)

Therefore, for the PSK modulation, the complexity of the SLE-Net can be given
by

$\displaystyle\mathcal{O}_{\mathrm{net}}$
$\displaystyle=\mathcal{O}_{\mathrm{e}}+\mathcal{O}_{\mathrm{d}}+\mathcal{O}_{\mathrm{n}}$
(64)
$\displaystyle=(9N_{\mathrm{s}}+3)K^{3}+(21N_{\mathrm{s}}+8RN_{\mathrm{s}}+4)K^{2}$
$\displaystyle+(12N_{\mathrm{s}}+6RN_{\mathrm{s}}+3)K-N_{\mathrm{s}}.$

Compared to the proposed algorithm for PSK modulation, the algorithm for QAM
modulation only increase the complexity of determining the set $\mathcal{O}$
and $\mathcal{I}$ for all the symbol slots. The complexity of this calculation
can be negligible in comparison to the entire algorithm. Therefore, the
complexities of the proposed algorithm for PSK modulation and QAM modulation
is nearly identical. We assume that the $M_{\mathrm{t}}=K=8$, $R=5$,
$N_{\mathrm{s}}=8000$, $\varepsilon=0.001$, and provide the number of the
floating operations of different precoding schemes for PSK modulation in TABLE
I.

TABLE I: The number of FLOPS | $4\times 4$ | $8\times 8$ | $12\times 12$ | $16\times 16$ | $20\times 20$
---|---|---|---|---|---
ZF | $2.816\times 10^{6}$ | $2.1504\times 10^{7}$ | $7.1424\times 10^{7}$ | $1.67936\times 10^{8}$ | $3.264\times 10^{8}$
CI-OPT | $1.082591\times 10^{8}$ | $1.0935\times 10^{9}$ | $4.407524\times 10^{9}$ | $1.199742\times 10^{10}$ | $2.622763\times 10^{10}$
CI-CF-PSK | $2.2024\times 10^{7}$ | $1.4132\times 10^{8}$ | $4.45192\times 10^{8}$ | $1.019656\times 10^{9}$ | $1.950728\times 10^{9}$
SLE-CF-PSK | $1.3568268\times 10^{7}$ | $7.043382\times 10^{7}$ | $1.982138\times 10^{8}$ | $4.245574\times 10^{8}$ | $7.771137\times 10^{8}$
SLE-Sub-PSK | $8.824268\times 10^{6}$ | $5.272982\times 10^{7}$ | $1.593578\times 10^{8}$ | $3.563574\times 10^{8}$ | $6.713777\times 10^{8}$
SLE-Net | $1.375227\times 10^{7}$ | $7.077782\times 10^{7}$ | $1.987178\times 10^{8}$ | $4.252214\times 10^{8}$ | $7.779377\times 10^{8}$

##  VI Simulation Results

In this section, the numerical results of the proposed schemes are presented
and compared with traditional CI precoding. We assume that there are $100$
channel transmission blocks. In each channel transmission block, the number of
symbol slots for transmission is $N_{s}=8000$. In each plot, we assume the
total transmit power is $p_{0}=1$, the number of the antenna at the
transmitter $M_{\mathrm{t}}$ is equal to the number of the users $K$. Both PSK
modulation and QAM modulation are considered in the numerical results. Our
simulation environment utilizes PyTorch version 1.13.1, and it is configured
to leverage the computational power of a GeForce GTX 3090 GPU. The
computational tasks on the CPU are handled by an Intel(R) Core(TM) i9-10900K
CPU @ 3.70 GHz, supported by 64 GB of RAM. Additionally, MATLAB is employed
for CPU-intensive operations. The following abbreviations are used throughout
this section:

  1. 1.

ZF: traditional ZF scheme with symbol-level power normalization, where the
precoding matrix of ZF is given by

${\bf W}_{\mathrm{ZF}}=\frac{\sqrt{p_{0}}}{f_{\mathrm{ZF}}}{\bf H}^{H}({\bf
H}{\bf H}^{H})^{-1},$ (65)

where $f_{\mathrm{ZF}}=\left\|{\bf H}^{H}({\bf H}{\bf H}^{H})^{-1}{\bf
s}\right\|_{2}$.

  2. 2.

CI-OPT: traditional optimization-based CI precoding based on ${\cal P}_{1}$
and ${\cal P}_{4}$ for PSK modulation and QAM modulation. By simplifying the
problem to a quadratic optimization problem in [22] and [38], it can
significantly reduce run-time without performance loss.

  3. 3.

CI-CF-PSK: iterative CI precoding scheme in [22].

  4. 4.

CI-CF-QAM: iterative CI precoding scheme in [38].

  5. 5.

SLE-CF-PSK: the iterative algorithm based on SLE for PSK modulation,
introduced in Section III-A.

  6. 6.

SLE-Sub-PSK: the sub-optimal closed-form algorithm based on SLE for PSK
modulation, introduced in Section III-A.

  7. 7.

SLE-CF-QAM: the iterative algorithm based on SLE for QAM modulation,
introduced in Section III-B.

  8. 8.

SLE-Sub-QAM: the sub-optimal closed-form algorithm based on SLE for QAM
modulation, introduced in Section III-B.

  9. 9.

SLE-Net: deep unfolding method based on SLE for the PSK modulation and QAM
modulation in Section VI.

Figure 4: BER v.s. SNR, QPSK, $M_{\mathrm{t}}=K=8$, $R=5$.

For QPSK modulation, we compared the bit error rate (BER) performance among
different methods. As observed in Fig. 4, the proposed SLE-Sub-PSK, SLE-CF-PSK
and SLE-Net algorithms exhibit superior performance compared to the ZF when
$M_{\mathrm{t}}=K=8$ and $R=5$. Both the SLE-CF-PSK and SLE-Net show a little
performance loss compared to the optimal solution. the SLE-CF-PSK slightly
outperforms the SLE-Net in terms of BER. Compared to the SLE-CF-PSK, the
performance of SLE-Sub-PSK exhibits a significant gap. The CI-CF-PSK has a
better performance than the proposed algorithms. The simulation results
validate the effectiveness of the proposed SLE-based algorithm for the QPSK
modulation.

Figure 5: BER v.s. SNR, 8PSK, $M_{\mathrm{t}}=K=8$, $R=5$.

In Fig. 5, we show the BER performance with respect to the increasing SNR when
8PSK modulation is employed, where $M_{\mathrm{t}}=K=8$ and $R=5$. Similarly,
the proposed SLE-Sub-PSK, SLE-CF-PSK and SLE-Net algorithms exhibit superior
performance compared to the ZF. The simulation result validate the
effectiveness of the algorithms for the 8PSK modulation scheme.

Figure 6: BER v.s. SNR, 8PSK, $M_{\mathrm{t}}=K=12$, $R=5$.

In Fig. 6, we consider the case of $M_{\mathrm{t}}=K=12$ and $R=5$ when 8PSK
modulation is employed. The relationship of BER performance for the algorithms
is not changed, and the curves exhibit the same trend compared to the case of
$M_{\mathrm{t}}=K=8$.

Figure 7: BER v.s. Maximum number iterations, 8PSK, $M_{\mathrm{t}}=K=8$,
SNR$=25$ dB.

In Fig. 7, we illustrate the relationship between BER performance and the
number of iterations. When $M_{\mathrm{t}}=K=8$ and SNR$=25$ dB, we observe
that the SLE iterative algorithm gradually stabilizes its BER performance as
the iteration number increasing for 8PSK, demonstrating a favorable
convergence speed. At the same time, we can conclude that the SLE iterative
algorithm cannot reach the optimal performance for PSK modulation.

Figure 8: Execution time required for different schemes, 8PSK,
$M_{\mathrm{t}}=K$, $R=5$.

In Fig. 8, we analyze the average execution time of all algorithms within a
symbol slot when using the 8PSK modulation. It is observed that with an
increasing the number of users, the execution time of all algorithms
increases. Simultaneously, we conclude that the ZF has the lowest complexity.
The CI-OPT has the maximized execution time. The execution time of SLE-CF-PSK
is less than CI-CF-PSK, proving the effectiveness of the SLE. The time
complexity of SLE-Net is lower than SLE-CF-PSK. This is attributed to the
parallel processing capability of GPUs.

Figure 9: BER v.s. SNR, 16QAM, $M_{\mathrm{t}}=K=12$, $R=5$.

In Fig. 9, we show the BER performance with respect to the increasing SNR when
16QAM modulation is employed, where $M_{\mathrm{t}}=K=12$ and $R=5$. All SLE-
based algorithms consistently outperform ZF. Furthermore, the performance of
SLE-CF-QAM and SLE-Net has only slight degradation compared to the optimal
solution.

Figure 10: BER v.s. Maximum number iterations, 16QAM, $M_{\mathrm{t}}=K=12$,
SNR$=25$ dB.

In Fig. 10, we show the BER performance with respect to the increasing
iteration counts when 16QAM modulation is employed, where
$M_{\mathrm{t}}=K=12$ and SNR $=25$ dB. The SLE-CF-QAM alse has a favorable
convergence rate. The results validate the effectiveness of the proposed
algorithms for the 16QAM modulation. At the same time, we can conclude that
the SLE iterative algorithm cannot reach the optimal performance for QAM
modulation.

##  VII Conclusion

In this paper, we propose a SLE algorithm for both the PSK modulation and QAM
modulation. Within a transmission block, we exploit the relationships between
the different symbol slots to extrapolate the symbol-scaling factors. By
leveraging the existing solution structure of CI-SLP design, we finally obtain
the precoding matrix. We further use the deep unfolding to unfold the
iteration algorithm into the layer-wise structure and propose the SLE-Net. The
SLE-Net is able to adapt both PSK modulation and QAM modulation without
changing its network structure and loss function. The SLE-Net leverages the
parallel processing capability of GPUs, which can further reduce the time
complexity of algorithm. Extensive simulation results verified that the
proposed algorithms have superiority in complexity reduction with an
acceptable performance loss compared with the traditional SLP schemes, which
ensures that SLP can be used in practical communication systems.

## References

  * [1] F. Rusek, D. Persson, B. K. Lau, E. G. Larsson, T. L. Marzetta, O. Edfors, and F. Tufvesson, “Scaling up MIMO: Opportunities and Challenges with Very Large Arrays,” _IEEE Signal Processing Magazine_ , vol. 30, no. 1, pp. 40–60, 2012.
  * [2] T. L. Marzetta, “Noncooperative Cellular Wireless with Unlimited Numbers of Base Station Antennas,” _IEEE Transactions on Wireless Communications_ , vol. 9, no. 11, pp. 3590–3600, 2010.
  * [3] L. Zheng and D. N. C. Tse, “Diversity and Multiplexing: A Fundamental Tradeoff in Multiple-antenna Channels,” _IEEE Transactions on Information Theory_ , vol. 49, no. 5, pp. 1073–1096, 2003.
  * [4] M. Costa, “Writing on Dirty Paper (corresp.),” _IEEE Transactions on Information Theory_ , vol. 29, no. 3, pp. 439–441, 1983.
  * [5] L. Sun and M. Lei, “Quantized CSI-based Tomlinson-Harashima Precoding in Multiuser MIMO Systems,” _IEEE Transactions on Wireless Communications_ , vol. 12, no. 3, pp. 1118–1126, 2013.
  * [6] B. M. Hochwald, C. B. Peel, and A. L. Swindlehurst, “A Vector-perturbation Technique for Near-capacity Multiantenna Multiuser Communication-part ii: Perturbation,” _IEEE Transactions on Communications_ , vol. 53, no. 3, pp. 537–544, 2005.
  * [7] T. K. Lo, “Maximum Ratio Transmission,” in _1999 IEEE International Conference on Communications (Cat. No. 99CH36311)_ , vol. 2. IEEE, 1999, pp. 1310–1314.
  * [8] T. Haustein, C. Von Helmolt, E. Jorswieck, V. Jungnickel, and V. Pohl, “Performance of MIMO Systems with Channel Inversion,” in _Vehicular Technology Conference. IEEE 55th Vehicular Technology Conference. VTC Spring 2002 (Cat. No. 02CH37367)_ , vol. 1. IEEE, 2002, pp. 35–39.
  * [9] C. B. Peel, B. M. Hochwald, and A. L. Swindlehurst, “A Vector-perturbation Technique For Near-capacity Multiantenna Multiuser Communication-part i: Channel Inversion and Regularization,” _IEEE Transactions on Communications_ , vol. 53, no. 1, pp. 195–202, 2005\.
  * [10] E. Visotsky and U. Madhow, “Optimum Beamforming Using Transmit Antenna Arrays,” in _1999 IEEE 49th Vehicular Technology Conference (Cat. No. 99CH36363)_ , vol. 1. IEEE, 1999, pp. 851–856.
  * [11] A. Wiesel, Y. C. Eldar, and S. Shamai, “Linear Precoding via Conic Optimization for Fixed MIMO Receivers,” _IEEE Transactions on Signal Processing_ , vol. 54, no. 1, pp. 161–176, 2005.
  * [12] M. Bengtsson and B. Ottersten, “Optimal Downlink Beamformingusing Semidefinite Optimization,” in _37th Annual Allerton Conference on Communication, Control, and Computing_ , 1999, pp. 987–996.
  * [13] M. Schubert and H. Boche, “Solution of The Multiuser Downlink Beamforming Problem with Individual SINR Constraints,” _IEEE Transactions on Vehicular Technology_ , vol. 53, no. 1, pp. 18–28, 2004.
  * [14] Y. Wen, H. Wang, A. Li, X. Liao, and C. Masouros, “Interference Exploitation MU-MISO Precoding under Per-antenna Power Constraint,” in _2023 IEEE 24th International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. IEEE, 2023, pp. 111–115.
  * [15] H. Shen, W. Xu, A. Lee Swindlehurst, and C. Zhao, “Transmitter Optimization for Per-antenna Power Constrained Multi-antenna Downlinks: An SLNR Maximization Methodology,” _IEEE Transactions on Signal Processing_ , vol. 64, no. 10, pp. 2712–2725, 2016.
  * [16] C. Masouros, T. Ratnarajah, M. Sellathurai, C. B. Papadias, and A. K. Shukla, “Known Interference in The Cellular Downlink: A Performance Limiting Factor or A Source of Green Signal Power?” _IEEE Communications Magazine_ , vol. 51, no. 10, pp. 162–171, 2013.
  * [17] C. Masouros and E. Alsusa, “A Novel Transmitter-based Selective-precoding Technique for DS/CDMA Systems,” in _2007 IEEE International Conference on Communications_ , 2007, pp. 2829–2834.
  * [18] C. Masouros and E. Alsusa, “Dynamic Linear Precoding for The Exploitation of Known Interference in MIMO Broadcast Systems,” _IEEE Transactions on Wireless Communications_ , vol. 8, no. 3, pp. 1396–1404, 2009.
  * [19] C. Masouros, “Correlation Rotation Linear Precoding for MIMO Broadcast Communications,” _IEEE Transactions on Signal Processing_ , vol. 59, no. 1, pp. 252–262, 2010.
  * [20] C. Masouros and G. Zheng, “Exploiting Known Interference as Green Signal Power for Downlink Beamforming Optimization,” _IEEE Transactions on Signal processing_ , vol. 63, no. 14, pp. 3628–3640, 2015.
  * [21] M. Alodeh, S. Chatzinotas, and B. Ottersten, “Constructive Multiuser Interference in Symbol Level Precoding for The MISO Downlink Channel,” _IEEE Transactions on Signal processing_ , vol. 63, no. 9, pp. 2239–2252, 2015.
  * [22] A. Li and C. Masouros, “Interference Exploitation Precoding Made Practical: Optimal Closed-form Solutions for PSK Modulations,” _IEEE Transactions on Wireless Communications_ , vol. 17, no. 11, pp. 7661–7676, 2018.
  * [23] J. Yang, A. Li, X. Liao, and C. Masouros, “Low Complexity SLP: An Inversion-free, Parallelizable ADMM Approach,” _arXiv preprint arXiv:2209.12369_ , 2022.
  * [24] Z. Xiao, R. Liu, M. Li, Y. Liu, and Q. Liu, “Low-complexity Designs of Symbol-level Precoding for MU-MISO Systems,” _IEEE Transactions on Communications_ , vol. 70, no. 7, pp. 4624–4639, 2022.
  * [25] A. Li, C. Shen, X. Liao, C. Masouros, and A. L. Swindlehurst, “Practical Interference Exploitation Precoding without Symbol-by-symbol Optimization: A Block-level Approach,” _IEEE Transactions on Wireless Communications_ , 2022.
  * [26] Z. Lei, X. Liao, Z. Gao, and A. Li, “CI-NN: A Model-driven Deep Learning-based Constructive Interference Precoding Scheme,” _IEEE Communications Letters_ , vol. 25, no. 6, pp. 1896–1900, 2021.
  * [27] M. Zhang, J. Gao, and C. Zhong, “A Deep Learning-based Framework for Low Complexity Multiuser MIMO Precoding Design,” _IEEE Transactions on Wireless Communications_ , vol. 21, no. 12, pp. 11 193–11 206, 2022.
  * [28] A. Balatsoukas-Stimming and C. Studer, “Deep Unfolding for Communications Systems: A Survey and Some New Directions,” in _2019 IEEE International Workshop on Signal Processing Systems (SIPS)_. IEEE, 2019, pp. 266–271.
  * [29] S. Cammerer, T. Gruber, J. Hoydis, and S. Ten Brink, “Scaling Deep Learning-based Decoding of Polar Codes via Partitioning,” in _GLOBECOM 2017-2017 IEEE Global Communications Conference_. IEEE, 2017, pp. 1–6.
  * [30] N. Samuel, T. Diskin, and A. Wiesel, “Learning To Detect,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 10, pp. 2554–2564, 2019.
  * [31] H. He, C.-K. Wen, S. Jin, and G. Y. Li, “A Model-driven Deep Learning Network for MIMO Detection,” in _2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP)_. IEEE, 2018, pp. 584–588.
  * [32] A. Mohammad, C. Masouros, and Y. Andreopoulos, “An Unsupervised Deep Unfolding Framework for Robust Symbol Level Precoding,” _IEEE Open Journal of the Communications Society_ , 2023.
  * [33] Q. Hu, Y. Cai, Q. Shi, K. Xu, G. Yu, and Z. Ding, “Iterative Algorithm Induced Deep-unfolding Neural Networks: Precoding Design for Multiuser MIMO systems,” _IEEE Transactions on Wireless Communications_ , vol. 20, no. 2, pp. 1394–1410, 2020.
  * [34] M. Liang and A. Li, “Deep Learning-based Channel Extrapolation for Pattern Reconfigurable Massive MIMO,” _IEEE Transactions on Vehicular Technology_ , pp. 1–6, 2023.
  * [35] M. Alrabeiah and A. Alkhateeb, “Deep Learning for TDD and FDD Massive MIMO: Mapping Channels in Space and Frequency,” in _2019 53rd Asilomar Conference on Signals, Systems, and Computers_. IEEE, 2019, pp. 1465–1470.
  * [36] D. Zhang, A. Li, C. Pradhan, J. Li, B. Vucetic, and Y. Li, “Training Beam Sequence Design for Multiuser Millimeter Wave Tracking Systems,” _IEEE Transactions on Communications_ , vol. 69, no. 10, pp. 6939–6955, 2021.
  * [37] A. Li, D. Spano, J. Krivochiza, S. Domouchtsidis, C. G. Tsinos, C. Masouros, S. Chatzinotas, Y. Li, B. Vucetic, and B. Ottersten, “A Tutorial on Interference Exploitation via Symbol-level Precoding: Overview, State-of-the-art and Future Directions,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 2, pp. 796–839, 2020.
  * [38] A. Li, C. Masouros, B. Vucetic, Y. Li, and A. L. Swindlehurst, “Interference Exploitation Precoding for Multi-level Modulations: Closed-form Solutions,” _IEEE Transactions on Communications_ , vol. 69, no. 1, pp. 291–308, 2020.
  * [39] M. Roodschild, J. Gotay Sardiñas, and A. Will, “A New Approach for the Vanishing Gradient Problem on Sigmoid Activation,” _Progress in Artificial Intelligence_ , vol. 9, no. 4, pp. 351–360, 2020.
  * [40] D. P. Kingma and J. Ba, “Adam: A Method for Stochastic Optimization,” _ArXiv Preprint ArXiv:1412.6980_ , 2014.