# MIMO Detection for High Order QAM by Canonical Dual Approach

Authors: Ye Tian; Jr-Fong Dang
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

We develop a canonical dual approach for solving the MIMO problem. First, a special linear transformation is introduced to reformulate the original problem into a{
−
1
,
1
} constrained quadratic programming problem. Then, we derive a canonical dual problem which is piecewise continuous problem with no duality gap. Under certain conditions, the canonical problem becomes a concave maximization dual problem over a convex feasible domain. By getting the stationary point of the canonical dual problem, we can find either an optimal or approximate solution of the original problem. A gradient decent algorithm is proposed to solve the MIMO problem and simulation results are provided to demonstrate the effectiveness of the method.


---

## Body

## 1. Introduction

In the recent decade, multiple antennae communication systems have developed very fast since it could provide substantial performance gain over their single antenna counterparts [1]. Therefore, how to efficiently detect the signal vector of transmitted symbols becomes an important issue. As a consequent result, the problem of multiple-input-multiple-output MIMO detection has been raised up and received considerable attention over several years.Note that, in the communication scenarios, the signal model is always written in the following form:(1)
y
=
H
x
+
v
,where y
∈
R
m is a received signal vector, x
∈
R
n is a transmitted symbol vector whose elements are drawn from a symbol constellation set, H is m
×
n real matrix that characterizes the input-output relation, and v
∈
R
m is an additive white Gaussian noise with unit variance. It is worth pointing out that the signal model is sometimes represented in a complex-valued form. But it is easy to reformulate the complex-valued model to a real-valued model (please see [2] for details). The MIMO problem aims to detect the transmitted vector x based on the observations y and H. And the optimal symbol vector which minimizes the error probability can be found by solving the maximum-likelihood (ML) detection problem [3]. It is a very fundamental problem in the communication area. The corresponding problem is as follows: MIMO
min
⁡
⁡
W
y
-
H
x
2
i
s
.
t
.
W
i
I
x
i
∈
±
1
,
±
3
,
…
,
±
u
,
i
=
1
,
…
,
n
,where · denotes the 2-norm and each symbol x
i is drawn from a (
u
+
1
)-QAM constellation set S
=
{
±
1
,
±
3
,
…
,
±
u
} (please see [4] for details). In this paper, we suppose u
≥
3. Unfortunately, the MIMO problem is NP-hard [5]. Therefore, researchers have developed a lot of approximation algorithms.Lattice decoding is an important research direction for the MIMO detection. It has received a lot of attention for its good tradeoff between detection accuracy and complexity [6–8]. Naive lattice decoding (NLD) method relaxes the symbol bound constraints and finds the closest lattice point to the received signal over the whole lattice generated by the channel [6]. In order to further improve the efficiency, some suboptimal lattice decoding methods, such as sampled decoding [9], embedded decoding [10], and lattice reduction-aided (LRA) methods [11], can be combined with lattice decoding method to accelerate the lattice point search. However, since the NLD method completely ignores the symbol bounds, it fails to achieve the optimal diversity-multiplexing tradeoff (DMT) under general MIMO system models [6, 8]. Then, in order to prevent the lattice points going too far away from the origin point, some researchers developed the regularized lattice decoding (RLD) method which adds a quadratic penalization term to the lattice decoding metric [12]. Though the RLD method has been empirically found to be computationally fast for small to moderate problems sizes, its complexity would be prohibitive for large n and higher order QAM [13].Another big family of MIMO detection algorithms is based on semidefinite relaxation (SDR). The SDR method relaxes the ML detection problem into a convex semidefinite programming (SDP) problem which leads to a polynomial-time complexity in the problem dimension. The SDR detector was first developed for the binary phase-shift keying (BPSK) constellation [14] and then extended to QPSK (4-QAM) constellation [15]. Researchers have verified that the SDR detector can provide a constant factor approximation to the optimal log-likelihood value in the low signal-to-noise ration (SNR) region almost surely [16]. Based on that, Wiesel et al. [17] proposed a polynomial-inspired SDR (PI-SDR) method for 16-QAM and proved that PI-SDR achieves an optimal Lagrangian dual lower bound of the ML. Sidiropoulos and Luo [18] designed a bound-constrained SDR (BC-SDR) method which has a special structure. Thus, compared to PI-SDR, BC-SDR makes fast implementations more favorable. Moreover, Mao et al. [19] developed a virtually antipodal SDR (VA-SDR) method for any 4
q-QAM (where q
>
1). For the relationship and comparisons between these SDR detectors, please see [2]. Though SDP problem has a theoretical low polynomial computational complexity, due to large problem size and slow SDP solvers, the actual computation time is very high in practice.Besides, there are some other algorithms for the MIMO problem. Sphere decoder method is a classical one [4, 20]. However, it exhibits exponential complexity with respect to the problem size. Moreover, Goldberger and Leshem [21] proposed a new detection algorithm based on an optimal tree approximation in an unconstrained linear system. They showed that this algorithm outperforms other methods for the loop-free factor graph situation. Recently, Pan et al. [22] proposed a Lagrangian dual relaxation (LDR) for the MIMO problem. This method finds the best diagonally regularized lattice decoder to approximate the ML detector. They proved that the LDR problem yields a duality gap no worse than that of the SDR method.In this paper, we present a canonical duality approach to the MIMO problem. The canonical duality theory is originally proposed for handling general nonconvex and/or nonsmooth systems [23]. Canonical dual transformation and associated triality theory play a key role in the implementation. It is worth pointing out that the canonical dual transformation may convert a nonconvex and/or nonsmooth primal problem into a piecewise smooth canonical dual problem. And this dual problem has no duality gap in each subregion. Therefore, this powerful tool has a big potential in some global optimization problems and nonconvex nonsmooth analysis [24–28]. Particularly, the canonical duality theory can be applied to the quadratic programming problem with integer constraints. Fang et al. [29] proposed a more general global optimization condition using the canonical duality approach. Wang et al. [30] developed a canonical duality approach for solving multi-integer quadratic programming problems. Thus, this paper adopts the canonical duality approach to study the MIMO problem.The paper is arranged as follows. In Section2, we introduce a special linear transformation to reformulate the original problem into a {
-
1,1
} constrained quadratic programming problem. In Section 3, we develop the canonical dual problem for the new reformulation. Then we show that it has no duality gap under certain conditions. Moreover, some global optimality conditions are presented. In Section 4, we propose a gradient decent method to find the stationary points. Comparisons by simulations are provided in Section 5. The last section summarizes the paper and points out some future research directions.


## 2. Linear Transformation

The MIMO problem can be written as follows:MIMO
1
min
⁡
⁡
W
x
T
H
T
H
x
-
2
y
T
H
x
+
y
2
i
s
.
t
.
W
I
x
i
∈
±
1
,
±
3
,
…
,
±
u
,
i
=
1
,
…
,
n
.Let Q
=
H
T
H and f
=
2
H
T
y. Note that Q is n
×
n real symmetric matrix and f is n-dimensional real vector. Since y
2 is a fixed scalar, problem MIMO
1 has the same optimal solutions with the following problem:MIMO
2
min
⁡
⁡
W
x
T
Q
x
-
f
T
x
i
s
.
t
.
W
I
x
i
∈
±
1
,
±
3
,
…
,
±
u
,
i
=
1
,
…
,
n
.We first reformulate problem MIMO
2 into a {
-
1,1
} constrained quadratic programming problem. Note that the set {
±
1
,
±
3
,
…
,
±
u
} forms an arithmetic series; that is, the adjacent two elements in the set have a constant gap 2. Therefore, we can take advantage of this special structure.Lety
i
=
x
i
+
u
/
2 for i
=
1
,
…
,
n; then y
i
∈
{
0,1
,
…
,
u
}. Let e denote the n-dimensional vector with all elements being 1. Then, it is easy to verify that problem MIMO
2 is equivalent to the following problem:MIMO
3
min
⁡
⁡
W
4
y
T
Q
y
-
4
u
e
T
Q
+
2
f
T
y
+
u
2
e
T
Q
e
+
u
f
T
e
i
s
.
t
.
W
I
y
i
∈
0,1
,
…
,
u
,
i
=
1
,
…
,
n
.Problem MIMO
2 and problem MIMO
3 have the same optimal value. Moreover, once we get an optimal solution of problem MIMO
3, we can use x
=
2
y
-
u
e to get the corresponding optimal solution of problem MIMO
2. Now, let Q
¯
=
4
Q and f
¯
=
4
u
Q
T
e
+
2
f. Since u
2
e
T
Q
e
+
u
f
T
e is also a fixed scalar, problem MIMO
3 has the same optimal solutions with the following problem:MIMO
4
min
⁡
⁡
W
y
T
Q
¯
y
-
f
¯
T
y
i
s
.
t
.
W
I
y
i
∈
{
0,1
,
…
,
u
}
,
i
=
1
,
…
,
n
.Let Y
=
y
∈
R
n
∣
y
i
is
an
integer
,
0
≤
y
i
≤
u denote the feasible domain of problem MIMO
4. Set t
=
log
⁡
(
u
+
1
); then t
≥
2 and u
+
1
≥
2
t. Now, we can define a new set Z as follows:(2)
Z
=
z
∈
R
t
+
1
n
∣
z
∈
-
1,1
t
+
1
n
.Note that each element in set Z is a (
t
+
1
)
n-dimensional vector with all elements being −1 or 1. Then, we have the following theorem to show the relationship between Y and Z.Theorem 1.
The transformationy
i
(
z
)
=
∑
j
=
1
t
‍
2
j
-
2
z
(
j
-
1
)
n
+
i
+
1
/
2
(
u
+
1
-
2
t
)
z
t
n
+
i
+
u
/
2 is a full mapping from Z to Y.Proof.
We first show that, for anyz
∈
Z, the corresponding y belongs to Y. Note that y
i
(
z
) can also be written as y
i
(
z
) = ∑
j
=
2
t
‍
2
j
-
2
z
(
j
-
1
)
n
+
i
-
2
t
-
1
z
t
n
+
i
+
1
/
2
z
i
+
u
+
1
/
2
z
t
n
+
i
+
u
/
2. The first part ∑
j
=
2
t
‍
2
j
-
2
z
(
j
-
1
)
n
+
i
-
2
t
-
1
z
t
n
+
i is always an integer; the possible fraction can only occur in the second part 1
/
2
z
i
+
u
+
1
/
2
z
t
n
+
i
+
u
/
2. However, it is easy to verify that this part is always an integer as z
i
,
z
t
n
+
i
∈
{
-
1,1
} for u
≥
3, t
≥
2. Moreover, for i
=
1
,
…
,
n, max
⁡
{
y
i
}
=
∑
j
=
1
t
‍
2
j
-
2
+
u
+
1
-
2
t
/
2
+
u
/
2
=
u and min{
y
i
}
=
-
∑
j
=
1
t
‍
2
j
-
2
-
u
+
1
-
2
t
/
2
+
u
/
2
=
0. Therefore, y
i is an integer between 0 and u and y belongs to Y.
Then, we show that, for an arbitrary integer0
≤
y
i
≤
u, there exist z
(
j
-
1
)
n
+
i
∈
-
1,1 for j
=
1
,
…
,
t
+
1 such that the transformation holds. If 0
≤
y
i
≤
2
t
-
1, then y
i can be written as y
i
=
2
t
-
1
a
t
-
1
+
2
t
-
2
a
t
-
2
+
⋯
+
2
a
1
+
1
a
0 for particular a
i
∈
0,1 and j
=
0
,
…
,
t
-
1. Then, let z
j
n
+
i
=
2
a
j
-
1 for j
=
0
,
…
,
t
-
1 and y
t
n
+
i
=
-
1. Thus, z
(
j
-
1
)
n
+
i
∈
{
-
1,1
} for j
=
1
,
…
,
t
+
1. It is easy to verify that ∑
j
=
1
t
‍
2
j
-
2
z
(
j
-
1
)
n
+
i
+
u
+
1
-
2
t
/
2
z
t
n
+
i
+
u
/
2
=
∑
j
=
0
t
-
1
‍
2
j
a
j
=
y
i. If 2
t
-
1
<
y
i
≤
u, since 2
t
≤
u
+
1
≤
2
t
+
1, we have -
2
t
≤
2
t
-
(
u
+
1
)
≤
0. Therefore, 0
≤
y
i
+
2
t
-
(
u
+
1
)
≤
2
t
-
1. Then following the similar way, we can write y
i
+
2
t
-
(
u
+
1
) as y
i
+
2
t
-
(
u
+
1
)
=
2
t
-
1
a
t
-
1
+
2
t
-
2
a
t
-
2
+
⋯
+
2
a
1
+
1
a
0 for particular a
i
∈
0,1, j
=
0
,
…
,
t
-
1. This time, let z
j
n
+
i
=
2
a
j
-
1 for j
=
0
,
…
,
t
-
1 and z
t
n
+
i
=
1. Thus, z
(
j
-
1
)
n
+
i
∈
{
-
1,1
} for j
=
1
,
…
,
t
+
1. Consequently, we have ∑
j
=
1
t
‍
2
j
-
2
z
(
j
-
1
)
n
+
i
+
u
+
1
-
2
t
/
2
z
t
n
+
i
+
u
/
2 = ∑
j
=
0
t
-
1
‍
2
j
a
j
+
(
u
+
1
)
-
2
t
=
x
i.
Therefore, the transformation is a full mapping fromZ to Y.It is worth pointing out that this transformation is a linear mapping. Moreover, since we use the advantage of the special structure of the original problem, the size of the reformulated problem is smaller than the problems derived by some traditional transformation methods [3].Now, replacingy by z in problem MIMO
4, we can get the following problem:MIMO
5
min
⁡
⁡
W
z
T
M
z
-
b
T
z
+
c
i
s
.
t
.
W
I
z
i
∈
-
1,1
,
i
=
1
,
…
,
t
+
1
n
,where(3)
M
=
1
4
Q
¯
1
2
Q
¯
⋯
2
t
-
3
Q
¯
1
4
u
+
1
-
2
t
Q
¯
1
2
Q
¯
Q
¯
⋯
2
t
-
2
Q
¯
1
2
u
+
1
-
2
t
Q
¯
⋮
⋮
⋱
⋮
⋮
2
t
-
3
Q
¯
2
t
-
2
Q
¯
⋯
2
2
t
-
4
Q
¯
2
t
-
3
u
+
1
-
2
t
Q
¯
1
4
u
+
1
-
2
t
Q
¯
1
2
u
+
1
-
2
t
Q
¯
⋯
2
t
-
3
u
+
1
-
2
t
Q
¯
1
4
u
+
1
-
2
t
2
Q
¯
,
b
=
1
4
[
2
f
¯
-
u
Q
¯
e
]
1
2
[
2
f
¯
-
u
Q
¯
e
]
⋮
2
t
-
3
[
2
f
¯
-
u
Q
¯
e
]
1
4
(
u
+
1
-
2
t
)
[
2
f
¯
-
u
Q
¯
e
]
,
c
=
1
8
u
2
e
T
Q
¯
e
-
u
2
f
¯
T
e
.Therefore, from Theorem 1, solving problem MIMO
5 is equivalent to solving problem MIMO
4.Letr
=
(
t
+
1
)
n and ignore the fixed scalar c; we focus on the following problem:MIMO
6
min
⁡
⁡
W
F
(
z
)
=
z
T
M
z
-
b
T
z
i
s
.
t
.
W
I
z
i
∈
-
1,1
,
i
=
1
,
…
,
r
.Note that problemMIMO
6 has no linear constraints and its feasible domain is merely defined by Z
=
z
∈
R
r
∣
z
∈
-
1,1
r.


## 3. Canonical Dual Problem and Global Optimality

Letρ
∈
R
r be a vector and let Diag
(
ρ
) denote an r
×
r diagonal matrix with ρ
i being the i
th diagonal element. Let(4)
M
ρ
=
M
+
Diag
(
ρ
)
,
P
(
ρ
)
=
-
1
4
b
T
M
ρ
-
1
b
-
e
T
ρ
.Moreover, we define a set as follows:(5)
D
M
=
ρ
∈
R
r
∣
ρ
≥
0
,
M
ρ
≠
0
,where M
ρ is the determinant of the matrix M
ρ.Then following the work of [30, 31], we can get the canonical dual problem of problem MIMO
6 as follows:CDP
sta
P
ρ
∣
ρ
∈
D
M
,where e is an r-dimensional vector with all elements being 1. sta
P
ρ
∣
ρ
∈
D
M represents finding all stationary points (critical points) of P
(
ρ
) over D
M.Moreover, for two vectorsa
,
b
∈
R
n, let a
∘
b denote the standard Hadamard product a
∘
b
≜
(
a
1
b
1
,
a
2
b
2
,
…
,
a
r
b
r
)
T. Then, for the relationship between the primal problem and the dual problem, we have the next two important theorems.Theorem 2.
Ifρ
∗
∈
D
M is a stationary point of the dual objective function P
(
ρ
), then z
(
ρ
∗
)
=
1
/
2
(
M
ρ
∗
)
-
1
b is an integer vector in {
-
1,1
}
r. Moreover, if M
ρ
∗ is positive definite, then the Hessian matrix of P
(
ρ
∗
) is negative definite.Proof.
Note that sincez
=
1
/
2
(
M
ρ
∗
)
-
1
b, we have M
ρ
∗
z
=
1
/
2
b. Thus, d
M
ρ
z
/
d
ρ
ρ
=
ρ
∗ = d
M
z
+
Diag
ρ
z
/
d
ρ
ρ
=
ρ
∗ = M
d
z
/
d
ρ
ρ
=
ρ
∗
+
Diag
(
z
)
+
Diag
ρ
∗
d
z
/
d
ρ
ρ
=
ρ
∗
=
0. Hence, we have d
z
/
d
ρ
ρ
=
ρ
∗
=
-
(
M
ρ
∗
)
-
1
Diag
(
z
). Therefore, d
P
ρ
/
d
ρ
ρ
=
ρ
∗ = -
1
/
2
d
[
(
b
T
(
M
ρ
)
-
1
M
ρ
z
)
+
2
e
T
ρ
]
/
d
ρ
ρ
=
ρ
∗ = -
1
/
2
d
b
T
z
/
d
ρ
ρ
=
ρ
∗
-
e = -
1
/
2
(
d
z
/
d
ρ
)
T
ρ
=
ρ
∗
b
-
e = 1
/
2
Diag
(
z
)
(
M
ρ
∗
)
-
1
b
-
e
=
Diag
(
z
)
z
-
e
=
z
∘
z
-
e. Therefore, if ρ
∗ is a stationary point of P
(
ρ
), then z
(
ρ
∗
)
∘
z
(
ρ
∗
)
-
e
=
0. This implies that the vector z
(
ρ
∗
)
=
1
/
2
(
M
ρ
∗
)
-
1
b
∈
{
-
1,1
}
r.
Moreover, the Hessian matrixd
2
P
ρ
/
d
(
ρ
)
2
ρ
=
ρ
∗ = d
z
∘
z
-
e
/
d
ρ
ρ
=
ρ
∗ = 2
Diag
z
d
z
/
d
ρ
ρ
=
ρ
∗ = -
2
Diag
(
z
)
(
M
ρ
∗
)
-
1
Diag
(
z
). Thus, if M
ρ
∗ is positive definite, then the Hessian matrix of P
(
ρ
∗
) is negative definite.Theorem2 indicates that a stationary point ρ
∗ of P
(
ρ
) over D
M is corresponding to a feasible solution of the primal problem MIMO
6.Theorem 3.
The canonical dual problemCDP is perfectly dual to the primal problem MIMO
6 in the sense that if ρ
¯
∈
D
M is a stationary point of P
(
ρ
), then z
¯
=
1
/
2
(
M
ρ
¯
)
-
1
b is a KKT point of problem MIMO
6 and F
(
z
¯
)
=
P
(
ρ
¯
).Proof.
Note that problemMIMO
6 can be written as follows:(6)
min
⁡
⁡
W
F
(
z
)
=
z
T
M
z
-
b
T
z
i
s
.
t
.
W
I
z
∘
z
-
e
=
0
,
W
W
W
W
W
W
W
W
i
z
∈
R
r
.Its corresponding Lagrangian function is(7)
L
(
z
,
ρ
)
=
z
T
M
z
-
b
T
z
+
ρ
T
(
z
∘
z
-
e
)
.Therefore, the KKT conditions are as follows:(8)
∂
L
∂
z
=
2
M
z
-
b
+
2
Diag
(
ρ
)
z
=
2
M
ρ
z
-
b
=
0
,
∂
L
∂
ρ
=
z
∘
z
-
e
=
0
.Thus, from Theorem 2 and the definition of z
¯
(
ρ
¯
), it is easy to verify that z
¯
(
ρ
¯
) is a KKT point if ρ
¯ is a stationary point of P
(
ρ
).
Moreover, we have(9)
z
¯
T
M
z
¯
-
b
T
z
¯
W
W
=
z
¯
T
(
M
+
Diag
(
ρ
¯
)
)
z
¯
-
b
T
z
¯
-
z
¯
T
Diag
(
ρ
¯
)
z
¯
W
W
=
1
2
z
¯
T
b
-
b
T
z
¯
-
z
¯
T
Diag
(
ρ
¯
)
z
¯
W
W
=
-
1
2
b
T
z
¯
-
z
¯
T
Diag
(
ρ
¯
)
z
¯
W
W
=
-
1
2
b
T
z
¯
-
e
T
ρ
¯
W
W
=
-
1
4
b
T
M
ρ
¯
-
1
b
-
e
T
ρ
¯
W
W
=
P
(
ρ
¯
)
.The result follows.KKT conditions provide necessary conditions for local minimizers in a nonconvex programming problem. Next, we show that the canonical dual problem is a concave maximization dual problem over a convex feasible domain under certain conditions. First, we define a subset of setD
M as follows:(10)
D
M
+
=
ρ
∈
R
r
∣
ρ
≥
0
,
M
ρ
≻
0
,where M
ρ
∗
≻
0 indicates that M
ρ
∗ is positive definite. Then, we present the sufficient global optimal conditions.Theorem 4.
Assume thatρ
¯
∗
∈
D
M is a stationary point of P
(
ρ
) and z
¯
(
ρ
¯
∗
)
=
1
/
2
(
M
ρ
¯
∗
)
-
1
b. If ρ
¯
∗
∈
D
M
+, then z
¯ is a unique global minimizer of F
(
z
) over Z and ρ
¯
∗ is a global maximizer of P
(
ρ
¯
∗
) over D
M
+ with(11)
z
¯
T
M
z
¯
-
b
T
z
¯
=
min
⁡
z
∈
Z
z
T
M
z
-
b
T
z
=
max
⁡
ρ
∗
∈
D
M
+
C
(
ρ
∗
)
=
C
(
ρ
¯
∗
)
.Proof.
Note that ifρ
∈
D
M
+, then M
ρ
≻
0. Thus, Theorem 2 indicates that the Hessian matrix of P
(
ρ
) is negative definite over D
M
+. Then we know that the canonical dual function P
(
ρ
) is strictly concave over D
M
+. Therefore, a stationary point of P
(
ρ
) must be a global maximizer of P
(
ρ
) over D
M
+. Since the stationary point ρ
¯
∗
∈
D
M
+, Theorem 3 indicates that F
(
z
¯
)
=
P
(
ρ
¯
∗
).
On the other hand, sincez
¯ is a KKT point assured by Theorem 3, we have z
¯
∘
z
¯
-
e
=
0. Therefore, F
(
z
¯
)
=
z
¯
T
M
z
¯
-
b
T
z
¯
+
(
ρ
¯
∗
)
T
(
z
¯
∘
z
¯
-
e
)
=
z
¯
T
(
Q
+
Diag
(
ρ
¯
∗
)
)
z
¯
-
b
T
z
¯
-
e
T
ρ
¯
∗. Note that Q
+
Diag
(
ρ
¯
∗
) is positive definite; therefore z
¯
=
1
/
2
(
M
ρ
¯
∗
)
-
1
b is a global minimizer. Therefore, z
¯
T
(
Q
+
Diag
(
ρ
¯
∗
)
)
z
¯
-
b
T
z
¯
-
e
T
ρ
¯
∗ = min
⁡
z
∈
R
r
{
z
T
(
Q
+
Diag
(
ρ
¯
∗
)
)
z
-
b
T
z
-
e
T
ρ
¯
∗
}
≤
min
⁡
{
z
∈
R
r
,
z
∘
z
=
e
}
z
T
Q
z
-
b
T
z. Therefore, z
¯ is a global minimizer of F
(
z
) over Z.Above all, we transform the original problem which is a multi-integer quadratic programming problem into a piecewise continuous canonical dual problem by using the canonical duality theory. It is worth pointing out that the original problem and the canonical dual problem have no duality gap overD
M. Moreover, if ρ
∗
∈
D
M
+, the canonical dual problem becomes a concave maximization problem over a convex feasible domain which can be solved very efficiently. To the best of our knowledge, among all the existing methods, strong duality only holds for the Lagrangian dual relaxation (LDR) in the special 2-PAM case [22]. However, the canonical dual problem holds for any order PAM problem over D
M. Therefore, in some sense, the canonical dual problem provides the best dual problem of all.


## 4. Algorithm

Note that ifρ
∗ is a stationary point of P
(
ρ
) over D
M, then z
(
ρ
∗
)
=
1
/
2
(
M
ρ
∗
)
-
1
b is a feasible solution of problem MIMO
6. Moreover, if ρ
∗
∈
D
M
+, the corresponding solution z
(
ρ
∗
) is the global optimal solution of problem MIMO
6. Therefore, the solution of the dual problem CDP is corresponding to an optimal or approximation solution of problem MIMO
6.The key issue for solving the problemCDP is to avoid the matrix M
ρ
∗ becoming a singular matrix. Since z
(
ρ
∗
)
=
1
/
2
(
M
ρ
∗
)
-
1
b, we have 2
(
M
+
Diag
(
ρ
∗
)
)
z
(
ρ
∗
)
=
b. Thus, 2
Diag
(
z
(
ρ
∗
)
)
ρ
∗
=
b
-
2
M
z
(
ρ
∗
). Note that (
Diag
(
z
)
)
-
1
=
Diag
(
z
) for z
∈
Z. Therefore, ρ
∗
=
1
/
2
(
Diag
(
z
(
ρ
∗
)
)
b
-
2
Diag
(
z
(
ρ
∗
)
)
M
z
(
ρ
∗
)
). Hence, ρ
∗
=
1
/
2
(
z
(
ρ
∗
)
∘
b
-
2
(
M
z
(
ρ
∗
)
)
∘
z
(
ρ
∗
)
). Therefore, if the matrix M
ρ
∗ is close to a singular matrix, we can perturb the vector b to change the value of ρ
∗ and avoid the situation.Letz
∞ denote the infinity norm of vector z. Then, we propose an algorithm based on the gradient methods to solve problem CDP.Canonical Dual AlgorithmStep 1 (initialization step).
LetT
=
max
⁡
i
=
1
n
∑
j
=
1
n
‍
M
i
j, ϵ
>
0 be a sufficiently small number. Let k
=
0, ρ
0
=
4
(
T
+
ϵ
)
e be the initial feasible solution of problem CDP.Step 2.
Letz
(
ρ
k
)
=
1
/
2
(
M
ρ
∗
)
-
1
b. If ∇
P
ρ
k
∞
≤
ϵ, go to Step 4. Otherwise, ρ
k
+
1
=
ρ
k
-
α
k
g
k, where α
k
=
∇
P
ρ
k
∞ is a nonnegative scalar and g
k
=
∇
P
(
ρ
k
); k
=
k
+
1.Step 3.
IfM
ρ
k
<
ϵ, then let b
=
(
1
+
1
/
b
∞
)
b and ρ
k
=
1
/
2
(
z
(
ρ
k
)
∘
b
-
2
(
M
z
(
ρ
k
)
)
∘
z
(
ρ
k
)
). Go back to Step 2.Step 4.
Returnz
(
ρ
k
) and use Theorem 1 to get the corresponding solution y
∗.


## 5. Comparisons by Simulations

In this section, we use simulations to compare the canonical dual method (CDM) with some other benchmarked approximating methods, such as inexact ML sphere decoding (ML-SD) [4], semidefinite relaxation (SDR) [18], and inexact MMSE lattice decoding (MMSE-LD) [11].The channel matrixH comprises i.i.d. elements drawn from a zero-mean normal distribution of unit variance. The symbol vector x is element-wise i.i.d. uniformly distributed with each element s
i drawn from the standard u
+
1
2-QAM constellation set. Moreover, v is the additive white Gaussian noise with zero mean and variance σ
v
2. Note that the signal-to-noise ratio (SNR) is defined as E
(
H
x
2
)
/
E
(
v
2
)
=
n
σ
x
2
/
σ
v
2, where σ
x
2 is the variance of the elements of x.We use two different problem sizes as(
m
1
,
n
1
)
=
(
8,8
) and (
m
2
,
n
2
)
=
(
16,16
). And for each case, we test every numerical example under two situations: 16-QAM and 64-QAM. All the simulations are implemented using MATLAB 7.9.0 on a computer with Intel Core 2 CPU 2.50 Ghz and 2 G memory. Moreover, the solvers of cvx [32] are incorporated in solving the SDP problems.Figures1 and 2 plot the SERs of the various methods versus SNR under different problem sizes for 16-QAM constellations and 64-QAM constellations, respectively.Figure 1
Symbol error rate comparison for different methods,(
m
,
n
)
=
(
8,8
).
(a)
16-QAM
(b)
64-QAMFigure 2
Symbol error rate comparison for different methods,(
m
,
n
)
=
(
16,16
).
(a)
16-QAM
(b)
64-QAMTable1 provides the average computational time in seconds for each method under different cases. Note that the notation “8 16-QAM” denotes the 16-QAM problem whose size is (
m
,
n
)
=
(
8,8
). The other notations follow the same way.Table 1
Average computational time for different methods under different cases.
Methods
Cases
8 16-QAM
16 16-QAM
8 64-QAM
16 64-QAM
ML-SD
8.04 s
31.2 s
15.39 s
38.44 s
SDR
6.21 s
28.17 s
10.32 s
36.45 s
MMSE-LD
10.42 s
35.76 s
18.47 s
54.53 s
CDM
7.27 s
36.89 s
14.23 s
45.17 sFrom the simulation results, we can see that the CDM method outperforms all other methods in all situations. And the SER gaps between the CDM method and other methods are significantly wide. Moreover, the computation time indicates that the CDM method is quite efficient compared with other methods. It is worth pointing out that the CDM method is much more effective for the high order QAM problem.


## 6. Conclusion

In this paper, we have developed a canonical dual method to solve the MIMO problem. By introducing a tricky linear transformation, the original problem can be reformulated as a{
-
1,1
} constrained quadratic programming problem with the smallest size. Then, a canonical dual problem has been developed. The stationary points of the canonical dual problem correspond to the KKT points of the original problem. And there is no duality gap between the primal problem and its canonical dual problem under some conditions. Solving the canonical dual problem can lead to either an exact or approximate solution of the original problem. The simulation results indicate that the canonical dual method performs quite well compared with other benchmark methods.The canonical dual approach offers a different angle to study the MIMO problem. It sheds some light on designing a new but more efficient algorithm. For the future study, some searching methods can be combined in the algorithm to improve the efficiency for finding the stationary points. And we aim to figure out which subclass of the MIMO problem can be exactly solved by the canonical duality theory.



---

*Source: 201369-2015-04-05.xml*