###### Abstract

As communication systems advance towards the future 6G era, the incorporation
of large-scale antenna arrays in base stations (BSs) presents challenges such
as increased hardware costs and energy consumption. To address these issues,
the use of one-bit analog-to-digital converters (ADCs)/digital-to-analog
converters (DACs) has gained significant attentions. This paper focuses on
one-bit multiple-input multiple-output (MIMO) detection in an uplink multiuser
transmission scenario where the BS employs one-bit ADCs. One-bit quantization
retains only the sign information and loses the amplitude information, which
poses a unique challenge in the corresponding detection problem. The maximum-
likelihood (ML) formulation of one-bit MIMO detection has a challenging
likelihood function that hinders the application of many high-performance
detectors developed for classic MIMO detection (under high-resolution ADCs).
While many approximate methods for the ML detection problem have been studied,
it lacks an efficient _global_ algorithm. This paper fills this gap by
proposing an efficient branch-and-bound algorithm, which is guaranteed to find
the global solution of the one-bit ML MIMO detection problem. Additionally, a
new amplitude retrieval (AR) detection approach is developed, incorporating
explicit amplitude variables into the problem formulation. The AR approach
yields simpler objective functions that enable the development of efficient
algorithms offering both global and approximate solutions. The paper also
contributes to the computational complexity analysis of both ML and AR
detection problems. Extensive simulations are conducted to demonstrate the
effectiveness and efficiency of the proposed formulations and algorithms.

###### Index Terms:

Amplitude retrieval, global algorithm, maximum-likelihood, one-bit MIMO
detection

One-Bit MIMO Detection: From Global Maximum-Likelihood Detector to Amplitude
Retrieval Approach

Mingjie Shao, Wei-Kun Chen, Cheng-Yang Yu, Ya-Feng Liu, and Wing-Kin Ma

00footnotetext:  Part of this work was presented at the IEEE SPAWC, 2023 [1].
This work was completed during a visit of M. Shao and W.-K. Chen to the State
Key Laboratory of Scientific and Engineering Computing (LSEC), Institute of
Computational Mathematics and Scientific/Engineering Computing (ICMSEC),
Academy of Mathematics and Systems Science (AMSS), Chinese Academy of Sciences
(CAS). The work by M. Shao was supported by the Natural Science Foundation of
Shandong Province under Grant ZR2023QF103. The work of W.-K. Chen was
supported by the National Natural Science Foundation of China (NSFC) under
Grant 12101048. The work of Y.-F. Liu was supported in part by the NSFC under
Grant 12371314 and Grant 12288201. The work by W.-K. Ma was supported by a
General Research Fund of Hong Kong Research Grant Council under Project ID
CUHK 14205421.00footnotetext:  M. Shao is with the School of Information
Science and Engineering, Shandong University, Qingdao 266237, China (e-mail:
mingjieshao@sdu.edu.cn).00footnotetext:  W.-K. Chen and C.-Y. Yu are with the
School of Mathematics and Statistics/Beijing Key Laboratory on MCAACI, Beijing
Institute of Technology, Beijing 100081, China (e-mail: chenweikun,
yuchengyang@bit.edu.cn).00footnotetext:  Y.-F. Liu is with the LSEC, ICMSEC,
AMSS, CAS, Beijing 100190, China (e-mail:
yafliu@lsec.cc.ac.cn).00footnotetext:  W.-K. Ma is with the Department of
Electronic Engineering, The Chinese University of Hong Kong, Hong Kong, China
(e-mail: wkma@ieee.org).

##  I Introduction

With the advancement of communication systems from 5G to future 6G, the base
stations (BSs) are incorporating an increasing number of antennas to fulfill
the demanding requirements of high spectrum efficiency and enhanced
robustness. However, the deployment of large-scale antenna arrays introduces
challenges such as a higher number of analog-to-digital converters
(ADCs)/digital-to-analog converters (DACs), and radio-frequency (RF) front
ends. This, in turn, leads to elevated hardware costs and increased energy
consumption at the BS. To address these challenges, one promising approach is
to replace high-resolution ADCs/DACs with low-resolution alternatives,
especially one-bit ADCs/DACs, at the BS. One-bit ADCs/DACs offer benefits such
as cost-effectiveness and power efficiency. Additionally, their output signals
possess a constant envelope, which is friendly in the sense of allowing better
energy efficiency of the accompanying RF chains.

In light of the aforementioned background, coarse quantized signal processing
has emerged as a topic of extensive investigation. In conventional multiple-
input multiple-output (MIMO) systems with high-resolution ADCs/DACs, the
quantization noise is usually small and hardly affects the system performance.
As a result, the quantization noise is typically considered negligible.
However, in MIMO systems with low-resolution ADCs/DACs, the quantization noise
can be significant, and its effect should be better taken care of. In the
context of downlink communication with one-bit DACs, a prominent objective is
to devise a methodology for designing coarsely quantized (discrete)
transmitted signals that can satisfy some quality-of-service (QoS)
requirements of multiple users. This task, commonly referred to as one-bit
precoding in the existing literature, typically manifests as a discrete
optimization problem, prompting numerous research endeavors for algorithmic
designs and performance analysis; see [2, 3, 4, 5, 6, 7] and the references
therein.

In the multiuser uplink scenario employing one-bit ADCs, an important task
pertains to MIMO detection in the presence of coarsely quantized observations,
which is the focus of this study. The received signals at the BS only retain
the sign information while losing the amplitude information. Consequently,
one-bit MIMO detection entails an inverse problem that involves detecting the
multiuser signals from the one-bit quantized received signal. Due to the
strong nonlinearity and the amplitude loss associated with one-bit
quantization, conventional MIMO detection methods developed for high-
resolution ADCs cannot be directly applied to one-bit MIMO detection, or their
performance may degrade [8, 9].

The goal of this paper is to propose new formulations and efficient algorithms
for the one-bit MIMO detection problem, which either is guaranteed to find the
global solution of the considered problem or is able to strike a good balance
between the detection performance and the computational cost.

###  I-A Related Works

In view of the difficulties in one-bit MIMO detection, researchers have been
exploring new methods to solve the problem. Among the existing approaches,
maximum-likelihood (ML) detection is perhaps the most widely studied one. It
is challenging to (globally) solve the ML detection problem because the
problem is a nonlinear integer programming (NLIP) problem and the likelihood
function involves integrals that do not admit an explicit form. To tackle the
ML problem efficiently, several approximate techniques have been proposed,
including proximal gradient algorithms [9, 10, 11, 12], expectation
maximization (EM) methods [13, 14], search-based algorithms [15], and deep
learning methods [11, 16, 17, 18]. Nonetheless, it should be noted that simple
convex relaxation [9, 12] or Gaussian approximation [13] of the constellation
symbols can significantly degrade the detection performance. Therefore,
researchers have explored various strategies to narrow the performance gap
with the ML solution, such as employing extreme point pursuit [11], refining
the solution through local search techniques [9, 16], and leveraging the
potential of deep learning [11, 16, 17, 14]. In addition, there are works that
try to approximate the thorny likelihood function. For instance, the works
[15] and [19] apply local quadratic approximations, while [16] considers to
use the sigmoid function to approximate the likelihood function in order to
simplify the deep network training. Despite these efforts, the development of
an efficient globally optimal method for the one-bit ML MIMO detection problem
remains a challenge; in particular, the highly nonlinear likelihood function
stands as an obstacle in the design of globally optimal algorithms.
Consequently, neither can classic MIMO detection techniques relying heavily on
the quadratic objective form, such as the sphere decoding algorithm [20], nor
off-the-shelf optimization solvers like CPLEX [21] be readily exploited in
this context.

In addition to ML detection, researchers have also explored alternative
possibilities for MIMO detection under one-bit quantization. Linear detectors,
known for their simplicity, have been extensively studied. The focus of this
line of research lies in analyzing the impact of quantization on linear
detectors such as maximum ratio combination (MRC) and zero-forcing (ZF) [22,
23]. Moreover, modified linear receivers leveraging the Bussgang theorem have
been proposed with the aim of improving the detection performance [16].
Additionally, the one-bit MIMO detection can be interpreted as a binary
classification task, which has been handled by a support vector machine
formulation [24]. Another closely related approach to ML detection is maximum
a posteriori (MAP) detection. Researchers have investigated various methods to
approximate MAP detection, including the approximate message passing technique
[25] and the variational inference method [26]. These approaches share
similarities with EM methods used in ML detection, in terms of both their key
steps and computational complexities. In addition, spatial sigma-delta
modulation applies the principles of antenna feedback and noise shaping to
mitigate the quantization noise, which provides a different way for receiver
design [27].

###  I-B Our Contributions

In this paper, we study one-bit MIMO detection in a single-cell multiuser
uplink scenario. We start with the development of a global algorithm, which is
an efficient branch-and-bound algorithm, for solving the ML detection problem.
In addition, in order to bypass sophisticated optimization techniques to
handle the highly nonlinear likelihood function of the ML detection problem,
we propose to incorporate the missing amplitude information into the one-bit
MIMO detection problem. This leads to a new one-bit MIMO detection formulation
that is much easier to handle than the one-bit ML MIMO detection formulation.
We provide extensive simulations to demonstrate the detection performance and
computational complexities of the proposed approaches.

The contributions of this work are summarized as follows.

  1. (i)

_First Global Algorithm for One-Bit ML MIMO Detection_. We first analyze the
complexity status of the one-bit ML MIMO detection problem. It is well-known
that the classic ML MIMO detection problem is NP-hard [28], but the complexity
status of the one-bit ML MIMO detection problem remains unknown. We fill this
theoretical gap by showing that the one-bit ML MIMO detection problem is NP-
hard. Then, we propose the _first_ global algorithm for one-bit ML MIMO
detection. Specifically, we first transform the one-bit ML MIMO detection
problem into an equivalent mixed integer linear programming (MILP) problem
with an exponential number of constraints (with respect to the number of
users). To solve the proposed MILP problem, we employ a delayed constraint
generation framework, which starts with a relaxed MILP problem with only a
selected small subset of constraints, and gradually adds the neglected
constraints (when needed) until an optimal solution of the original problem is
found. In order to develop a lightweight global algorithm, we solve each
relaxed MILP problem inexactly, which is achieved by embedding the delayed
constraint generation procedure into the branch-and-bound procedure. In this
way, the algorithm only needs to solve linear programming (LP) subproblems
with significantly smaller problem sizes (compared with the MILP reformulation
of the original problem), and thus is computationally efficient.

  2. (ii)

_New AR Formulation and Low-Complexity Algorithm_. To address the loss of the
amplitude information due to quantization, we propose an alternative
formulation to one-bit ML MIMO detection by introducing an explicit amplitude
variable into the problem. The key feature of the amplitude retrieval (AR)
formulation is that it has much simpler objective functions (quadratic or
linear) compared to ML detection, which significantly facilitates the design
of computationally efficient global and approximate algorithms. In particular,
we can directly apply the state-of-the-art optimization solvers to the AR
formulation to find an optimal solution. In addition, we leverage the
alternate Barzilai-Borwein (ABB) method [29], which is a first-order projected
gradient (PG) method with a modified step size, to obtain a computationally
efficient solution.

We provide extensive simulations to test the efficacy of the proposed
algorithms. The simulation results show that the proposed global algorithm for
the one-bit ML MIMO detection problem can obtain an optimal solution by a
considerably reduced runtime than the exhaustive search, which enables it to
be an important performance benchmark for various existing approximate
algorithms developed for the same problem. Moreover, we provide numerical
evidence to show that the AR formulation is a reasonable alternative to the ML
formulation. Compared to the ML formulation, the AR formulation, which is
tackled by our custom-built algorithm, can yield competitive bit-error rate
(BER) performance with a much lower computational complexity.

Part of this paper was presented in a conference [1]. It studied the global
algorithm design for one-bit ML MIMO detection, which corresponds to
Subsections III-B and III-C in this paper. Compared to its conference version
[1], this paper has many new contributions in complexity analysis, problem
formulation, and algorithmic design. First, this paper presents the complexity
analysis for one-bit ML MIMO detection, which was not considered in [1]. More
importantly, this paper develops new AR formulations and efficient algorithms,
which stands as a new core contribution of this paper.

###  I-C Organization and Notations

Our paper is organized as follows. Section II reviews the one-bit ML MIMO
detection problem. Section III studies the complexity analysis of one-bit ML
MIMO detection problem, and proposes a global algorithm for solving it.
Section IV describes the AR formulation, analyzes its complexity, and presents
a custom-built algorithm for solving it. Section V shows extensive simulation
results to illustrate the performance of the proposed algorithms. Section VI
draws the conclusion.

Our adopted notations are standard. We use $\mathbb{R}$ and $\mathbb{C}$ to
denote the real and complex space, respectively. The boldface lowercase
letters, e.g., ${\bm{x}}$, represent vectors; $x_{i}$ represents the $i$th
element of ${\bm{x}}$; the boldface uppercase letters, e.g., ${\bm{X}}$,
represent matrix; $|\mathcal{S}|$ denotes the cardinality of a set
$\mathcal{S}$; $\Re(x)$ and $\Im(x)$ denote the real and imaginary parts of
$x$, respectively; $\langle{\bm{x}},{\bm{y}}\rangle$ denotes the inner product
between ${\bm{x}}$ and ${\bm{y}}$; ${\bm{X}}^{\top}$ and
${\bm{X}}^{{\dagger}}$ denote the transpose and pseudo-inverse, respectively;
$\mbox{Diag}({\bm{x}})$ represents a diagonal matrix with ${\bm{x}}$ being the
diagonal elements; $\|{\bm{x}}\|_{n}$ denotes the $\ell_{n}$-norm of
${\bm{x}}$ for $n\geq 1$; ${\cal N}(\bm{\mu},\bm{C})$ represents the Gaussian
distribution with mean $\bm{\mu}$ and covariance $\bm{C}$.

##  II One-Bit ML MIMO Detection

This section presents the probit signal model and one-bit ML MIMO detection
problem, which paves the way to the global algorithmic design in Section III.

###  II-A Signal Model

The problem of interest can be posed as the following probit model

$\begin{split}{\bm{r}}=\mbox{sgn}({\bm{y}}),\quad{\bm{y}}={\bm{H}}{\bm{x}}+{\bm{v}}.\end{split}$
(1)

Here, ${\bm{r}}\in\mathbb{R}^{M}$ is the observation vector; the function sgn
takes the sign of its argument, thus the elements of ${\bm{r}}$ are binary,
i.e., $r_{i}\in\\{-1,1\\}$ for $i=1,2,\ldots,M$; ${\bm{y}}\in\mathbb{R}^{M}$
is the unquantized counterpart of ${\bm{r}}$, but is not observable;
${\bm{H}}\in\mathbb{R}^{M\times N}$ is a system matrix;
${\bm{x}}\in\mathbb{R}^{N}$ is an unknown binary variable, i.e.,
$x_{i}\in\\{-1,1\\}$ for $i=1,2,\ldots,N$; and ${\bm{v}}\in\mathbb{R}^{M}$ is
a white Gaussian noise vector with ${\bm{v}}\sim{\cal
N}(\bm{0},\sigma^{2}{\bm{I}})$. The problem is to infer the variable
${\bm{x}}$ from the binary observation ${\bm{r}}$, given the information of
${\bm{H}}$ and $\sigma$.

Let us delineate how the interested one-bit MIMO detection problem falls into
the above probit model. Consider a massive MIMO system where the BS employs a
pair of one-bit ADCs at each antenna out of the consideration of hardware cost
and power consumption. In the uplink transmission, a number of $\tilde{N}$
single-antenna users concurrently send their signals to the BS with
$\tilde{M}$ antennas. The received signal can be modeled by

$\begin{split}\tilde{{\bm{r}}}=\leavevmode\nobreak\ {\cal
Q}(\tilde{{\bm{y}}}),\leavevmode\nobreak\ \leavevmode\nobreak\
\tilde{{\bm{y}}}=\leavevmode\nobreak\
\tilde{{\bm{H}}}\tilde{{\bm{x}}}+\tilde{{\bm{v}}},\end{split}$ (2)

where $\tilde{{\bm{x}}}\in\mathbb{C}^{\tilde{N}}$ is the multiuser transmit
signal vector, whose elements are assumed to be drawn from the Quadrature
Phase Shift Keying (QPSK) constellation $\\{\pm 1\pm\mathfrak{j}\\}$;
$\tilde{{\bm{H}}}\in\mathbb{C}^{\tilde{M}\times\tilde{N}}$ is the multiuser
channel matrix; $\tilde{{\bm{v}}}\in\mathbb{C}^{\tilde{M}}$ is additive
complex Gaussian noise with mean $\bm{0}$ and covariance matrix
$\tilde{\sigma}^{2}{\bm{I}}$;

${\cal Q}(x):=\mbox{sgn}(\Re(x))+\mathfrak{j}\cdot\mbox{sgn}(\Im(x))$

is the one-bit quantizer associated with the one-bit ADCs for both the real
and imaginary parts of $x$; $\tilde{{\bm{r}}}\in\mathbb{C}^{\tilde{M}}$ is the
received one-bit signal at the BS. One-bit MIMO detection aims to detect the
multiuser signal $\tilde{{\bm{x}}}$ from the received one-bit signal
$\tilde{{\bm{r}}}$, given the information of $\tilde{{\bm{H}}}$ and
$\tilde{\sigma}^{2}$.

Define

$\begin{split}{\bm{y}}=\begin{bmatrix}\Re(\tilde{{\bm{y}}})\\\
\Im(\tilde{{\bm{y}}})\end{bmatrix}\in\mathbb{R}^{M},{\bm{H}}=\begin{bmatrix}\Re(\tilde{{\bm{H}}})&-\Im(\tilde{{\bm{H}}})\\\
\Im(\tilde{{\bm{H}}})&\Re(\tilde{{\bm{H}}})\end{bmatrix}\in\mathbb{R}^{M\times
N},\\\ {\bm{x}}=\begin{bmatrix}\Re(\tilde{{\bm{x}}})\\\
\Im(\tilde{{\bm{x}}})\end{bmatrix}\in\mathbb{R}^{N},{\bm{r}}=\begin{bmatrix}\Re(\tilde{{\bm{r}}})\\\
\Im(\tilde{{\bm{r}}})\end{bmatrix}\in\mathbb{R}^{M},{\bm{v}}=\begin{bmatrix}\Re(\tilde{{\bm{v}}})\\\
\Im(\tilde{{\bm{v}}})\end{bmatrix}\in\mathbb{R}^{M},\end{split}$

where $M=2\tilde{M}$, $N=2\tilde{N}$, and ${\bm{v}}\in\mathbb{R}^{M}$ follows
the standard Gaussian distribution with mean $\bm{0}$ and covariance
$\sigma^{2}{\bm{I}}$ with $\sigma^{2}=\tilde{\sigma}^{2}/2$. With this
transformation, the one-bit MIMO detection problem is a special case of the
probit model in (1).

###  II-B ML Detection

We consider the ML detection associated with the probit model (1). The ML
detection problem can be formulated as [9]

$\min_{{\bm{x}}\in\\{-1,1\\}^{N}}f({\bm{x}}):=-\sum_{i=1}^{M}\log\Phi\left(\frac{{\bm{b}}_{i}^{\top}{\bm{x}}}{\sigma}\right),$
(3)

where ${\bm{b}}_{i}^{\top}=r_{i}\cdot{\bm{h}}_{i}^{\top}$,
${\bm{h}}_{i}^{\top}$ denotes the $i$th row of ${\bm{H}}$,
$\Phi(z)=\int_{-\infty}^{z}\frac{1}{\sqrt{2\pi}}e^{-t^{2}}\ dt$ is the
cumulative distribution function of the standard Gaussian distribution, and
$f({\bm{x}})$ is the negative log-likelihood function.

The one-bit ML MIMO detection problem (3) is an NLIP problem. The difficulty
of solving problem (3) arises from two aspects: (i) the objective function
$f({\bm{x}})$ involves integrals that do not have closed-form expressions;
(ii) the decision variables ${\bm{x}}$ are binary, whose dimension could be
large. One could apply an exhaustive search to globally solve (3), which needs
to examine all feasible solutions with a complexity order of ${\cal O}(2^{N})$
—which is exponentially increasing with the number of users. The computational
complexity can be unaffordable in a massive MIMO system where the number of
users can be tens or more. Moreover, to the best of our knowledge, off-the-
shelf efficient mixed integer linear programming (MILP) solvers such as CPLEX
[21] cannot directly handle the integral $\Phi(\cdot)$.

One may wonder whether the rich results in classic MIMO detection [30, 20, 31,
32, 33, 34, 35], where high-resolution ADCs are employed at the BS and
${\bm{y}}$ is directly accessible, can be applied to the one-bit ML MIMO
detection problem. Unfortunately, the classic ML MIMO detection problem has a
different objective function form (it is quadratic), and many high-performance
classic MIMO detectors, including lattice reduction [32], sphere decoding [20]
and semidefinite relaxation [30, 31], were developed based on the latter. In
the literature, researchers have proposed many approximate algorithms for
solving the one-bit ML MIMO detection problem (3) that seek to strike a
balance between the detection performance and the computational complexity
[22, 9, 11, 12, 16, 17, 13, 13, 14]. Many of them apply convex relaxation
methods on the binary constraints to avoid solving a problem with integer
variables [9, 11, 12, 13]. Unfortunately, these algorithms do not have a
guarantee to retrieve the globally optimal solution to the one-bit ML MIMO
detection problem (3).

In this paper, we aim to overcome the above weaknesses by proposing an
efficient algorithm for globally solving problem (3) in Section III. Moreover,
we will explore new yet simple alternative formulations for one-bit MIMO
detection in Section IV.

##  III An Efficient Global Algorithm

This section presents the complexity analysis of the one-bit ML MIMO detection
problem (3) and an efficient dedicated global algorithm for solving it.

###  III-A Complexity Analysis

We first analyze the complexity status of problem (3). It is well-known that
the classic ML MIMO detection problem is NP-hard [28]. However, it is still
unknown whether there exists a polynomial time algorithm for solving problem
(3). We fill this theoretical gap by showing the following theorem.

###### Theorem 1

The one-bit ML MIMO detection problem (3) is NP-hard.

To prove Theorem 1, we need the following lemma.

###### Lemma 1

Let $\Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{t^{2}}{2}}\ dt$.
Then, it holds that

$\min_{x\in\mathbb{R}}-\log\Phi(x)-\log\Phi(-x)=-2\log\Phi(0),$ (4)

where the only minimum point is arrived at $x=0$.

Proof of Lemma 1: Observe that

$\displaystyle\leavevmode\nobreak\ \Phi(x)\cdot\Phi(-x)$ $\displaystyle=$
$\displaystyle\left(\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{t^{2}}{2}}\
dt\right)\left(\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{-x}e^{-\frac{t^{2}}{2}}\
dt\right)$ $\displaystyle=$
$\displaystyle\left[\Phi(0)+\frac{1}{\sqrt{2\pi}}\int_{0}^{x}e^{-\frac{t^{2}}{2}}\
dt\right]\left[\Phi(0)+\frac{1}{\sqrt{2\pi}}\int_{0}^{-x}e^{-\frac{t^{2}}{2}}\
dt\right]$ $\displaystyle=$
$\displaystyle\left[\Phi(0)+\frac{1}{\sqrt{2\pi}}\int_{0}^{x}e^{-\frac{t^{2}}{2}}\
dt\right]\left[\Phi(0)-\frac{1}{\sqrt{2\pi}}\int_{0}^{x}e^{-\frac{t^{2}}{2}}\
dt\right]$ $\displaystyle=$
$\displaystyle{[\Phi(0)]}^{2}-{\left(\frac{1}{\sqrt{2\pi}}\int_{0}^{x}e^{-\frac{t^{2}}{2}}\
dt\right)}^{2}$ $\displaystyle\leq$ $\displaystyle{[\Phi(0)]}^{2},$

where the inequality holds with equality if and only if $x=0$. This, together
with the fact that $-\log\Phi(x)-\log\Phi(-x)=-\log[\Phi(x)\cdot\Phi(-x)]$,
shows the desired result. $\blacksquare$

Proof of Theorem 1. We prove Theorem 1 by showing that there exists a special
instance of problem (3) which is as hard as an NP-complete partition problem
[36]: given a finite set $\mathcal{S}=\\{1,2,\ldots,n\\}$ and a size
$w_{i}\in\mathbb{Z}_{+}$ for the $i$-th element with
$\sum_{i\in\mathcal{S}}w_{i}=2W$, does there exist a partition
$\mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{2}$ with
$\mathcal{S}_{1}\cap\mathcal{S}_{2}=\emptyset$ such that
$\sum_{i\in\mathcal{S}_{1}}w_{i}=\sum_{i\in\mathcal{S}_{2}}w_{i}=W$?

Given any instance of the partition problem, we construct an instance of
problem (3) by setting $M=2$, $N=n$, $\sigma=1$, ${\bm{b}}_{1}={\bm{w}}$, and
${\bm{b}}_{2}=-{\bm{w}}$. By construction, problem (3) reduces to

${v^{\ast}}=\min_{{\bm{x}}\in\\{-1,1\\}^{n}}-\log\Phi({\bm{w}}^{\top}{\bm{x}})-\log\Phi(-{\bm{w}}^{\top}{\bm{x}}).$
(5)

From Lemma 1, ${v^{\ast}}=-2\log\Phi(0)$ if and only if
${\bm{w}}^{\top}{\bm{x}}=0$ holds for some ${\bm{x}}\in\\{-1,1\\}^{n}$, which
is further equivalent to the existence of the partition
$\mathcal{S}=\mathcal{S}_{1}\cup\mathcal{S}_{2}$ with
$\sum_{i\in\mathcal{S}_{1}}w_{i}=\sum_{i\in\mathcal{S}_{2}}w_{i}=W$, that is,
the answer to the partition problem is yes. The above transformation can be
done in polynomial time. Since the partition problem is NP-complete, we
conclude that problem (3) is NP-hard. $\blacksquare$

Theorem 1 reveals the intrinsic difficulty of (globally) solving problem (3).
In particular, there does not exist a polynomial time algorithm for solving
problem (3) unless $\text{P}=\text{NP}$. In the next subsection, we will
design an efficient algorithm for globally solving problem (3).

###  III-B An Efficient Global Algorithm

In this subsection, we present a global algorithm for solving problem (3). To
do this, we first equivalently reformulate the NLIP problem (3) as an MILP
problem with an exponential number of constraints. Then we apply the delayed
constraint generation procedure [37] to solve the formulated MILP problem in
which only a small subset of constraints is initially considered, and
additional constraints are gradually added (when needed) until an optimal
solution of the original problem is found. Finally, to speed up the solution
process, we integrate the delayed constraint generation procedure into the
branch-and-bound algorithm, resulting into a customized efficient global
algorithm for solving problem (3).

####  III-B1 An MILP Reformulation

We first equivalently reformulate problem (3) as

$\begin{split}\min_{{\bm{x}},{\bm{w}}}&\leavevmode\nobreak\
\sum_{i=1}^{M}w_{i}\\\ \mbox{s.t. }&\leavevmode\nobreak\ w_{i}\geq
g_{i}({\bm{x}}),\leavevmode\nobreak\ \forall\leavevmode\nobreak\
i=1,2,\ldots,M,\\\ &\leavevmode\nobreak\
{\bm{x}}\in\\{-1,1\\}^{N},\end{split}$ (6)

where ${\bm{w}}={[w_{1},w_{2},\ldots,w_{M}]^{\top}}$ and

$g_{i}({\bm{x}}):=-\log\Phi\left(\frac{{\bm{b}}_{i}^{\top}{\bm{x}}}{\sigma}\right).$

Note that $g_{i}$ is a convex function with respect to ${\bm{x}}$. Thus, by
Jensen’s inequality, we obtain the following linear inequality

$g_{i}({\bm{x}})\geq g_{i}(\hat{{\bm{x}}})+\langle\nabla
g_{i}(\hat{{\bm{x}}}),{\bm{x}}-\hat{{\bm{x}}}\rangle,\leavevmode\nobreak\
\forall\leavevmode\nobreak\ \hat{{\bm{x}}}\in\\{-1,1\\}^{N},$ (7)

where

$\nabla
g_{i}({\bm{x}})=-\frac{\phi({\bm{b}}_{i}^{\top}{\bm{x}}/\sigma)}{\Phi({\bm{b}}_{i}^{\top}{\bm{x}}/\sigma)}\frac{{\bm{b}}_{i}}{\sigma}$

is the gradient of $g_{i}$ at ${\bm{x}}$, and
$\phi(t)=\frac{1}{\sqrt{2\pi}}e^{-t^{2}/2}$ is the probability distribution
function of the standard Gaussian distribution. Then, with (7), we can
reformulate problem (6) as follows

$\displaystyle({\bm{x}}^{\star},{\bm{w}}^{\star})=\arg\min_{{\bm{x}},{\bm{w}}}$
$\displaystyle\leavevmode\nobreak\ \sum_{i=1}^{M}w_{i}$ s.t.
$\displaystyle\leavevmode\nobreak\ w_{i}\geq
g_{i}(\hat{{\bm{x}}})+\langle\nabla
g_{i}(\hat{{\bm{x}}}),{\bm{x}}-\hat{{\bm{x}}}\rangle,$ (8a)
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\forall\leavevmode\nobreak\ i=1,2,\ldots,M,\leavevmode\nobreak\
\forall\leavevmode\nobreak\ \hat{{\bm{x}}}\in\\{-1,1\\}^{N},$
$\displaystyle\leavevmode\nobreak\ {\bm{x}}\in\\{-1,1\\}^{N}.$ (8b)

###### Fact 1

Problems (3) and (8) are equivalent, in the sense that they have the same
optimal solution for ${\bm{x}}$.

Fact 1 can be obtained by noting that inequality (7) is tight when
$\hat{{\bm{x}}}={\bm{x}}$, which establishes the equivalence between problems
(6) and (8). This, together with the equivalence between (3) and (6), leads to
the desired result.

The upshot of problem (8) is that the inequalities (8a) are _linear_ in both
${\bm{x}}$ and ${\bm{w}}$. As a result, problem (8) is an MILP problem. In
principle, problem (8) can be solved by off-the-shelf MILP solvers such as
CPLEX [21]. However, the total number of inequality constraints in (8a) is
$M\cdot 2^{N}$, where both $M$ and $N$ can be large in massive MIMO systems,
which can lead to prohibitively high computational complexity.

####  III-B2 A Delayed Constraint Generation Framework

To address the computational challenge arising from the exponential number of
constraints in (8a), we employ the delayed constraint generation framework.
This framework solves problem (8) by initially considering a small subset of
constraints in (8a) and gradually adding the neglected constraints (when
needed) until an optimal solution of the problem is found. For more details of
the delayed constraint generation framework, we refer to [37]. In the
following, we detail the delayed constraint generation framework to solve
problem (8).

Define the index set

$\mathcal{C}=\\{(i,\hat{{\bm{x}}})\leavevmode\nobreak\ |\leavevmode\nobreak\
i=1,2,\ldots,M,\leavevmode\nobreak\ \hat{{\bm{x}}}\in\\{-1,1\\}^{N}\\}$

and select $\mathcal{S}\subseteq\mathcal{C}$ as a subset of $\mathcal{C}$. We
consider the following relaxation of problem (8):

$\begin{split}\min_{{\bm{x}},{\bm{w}}}&\leavevmode\nobreak\
\sum_{i=1}^{M}w_{i}\\\ \mbox{s.t. }&\leavevmode\nobreak\ w_{i}\geq
g_{i}(\hat{{\bm{x}}})+\langle\nabla
g_{i}(\hat{{\bm{x}}}),{\bm{x}}-\hat{{\bm{x}}}\rangle,\leavevmode\nobreak\
\forall\leavevmode\nobreak\ (i,\hat{{\bm{x}}})\in\mathcal{S},\\\
&\quad\quad{\bm{x}}\in\\{-1,1\\}^{N}.\end{split}$ (9)

Denote by $(\bar{{\bm{x}}},\bar{{\bm{w}}})$ the optimal solution to problem
(9). We have the following result.

###### Fact 2

Consider problems (8) and (9). The following statements hold.

  * (i)

$\sum_{i=1}^{M}\bar{w}_{i}\leq\sum_{i=1}^{M}w_{i}^{\star}$;

  * (ii)

if $\bar{w}_{i}\geq g_{i}(\bar{{\bm{x}}})$ holds for all $i$, then
$(\bar{{\bm{x}}},\bar{{\bm{w}}})$ is also optimal to problem (8).

Proof: Since problem (9) is a relaxed version of problem (8), it holds that
$\sum_{i=1}^{M}\bar{w}_{i}\leq\sum_{i=1}^{M}w_{i}^{\star}$. This proves a).

If $\bar{w}_{i}\geq g_{i}(\bar{{\bm{x}}})$ for all $i$, then
$(\bar{{\bm{x}}},\bar{{\bm{w}}})$ is a feasible solution to problem (6). Hence
we get $\sum_{i=1}^{M}\bar{w}_{i}\geq\sum_{i=1}^{M}w^{\star}_{i}$. This,
together with a), implies
$\sum_{i=1}^{M}\bar{w}_{i}=\sum_{i=1}^{M}w^{\star}_{i}$. Therefore,
$(\bar{{\bm{x}}},\bar{{\bm{w}}})$ is an optimal solution to problem (6), and
also problem (8). $\blacksquare$

Fact 2 offers a hint to the algorithmic design. Specifically, we start from
solving problem (9) with an $\mathcal{S}\subseteq\mathcal{C}$. If
$\bar{w}_{i}\geq g_{i}(\bar{{\bm{x}}})$ holds for all $i$, then
$(\bar{{\bm{x}}},\bar{{\bm{w}}})$ is already optimal to problem (8).
Otherwise, if $\bar{w}_{i}<g_{i}(\bar{{\bm{x}}})$ for some $i$, the constraint

$w_{i}\geq g_{i}(\bar{{\bm{x}}})+\langle\nabla
g_{i}(\bar{{\bm{x}}}),{\bm{x}}-\bar{{\bm{x}}}\rangle$ (10)

is added into problem (9), i.e., adding $(i,\bar{{\bm{x}}})$ into
$\mathcal{S}$. Then, we solve problem (9) again with the updated
$\mathcal{S}$. This process is repeated until $\bar{w}_{i}\geq
g_{i}(\bar{{\bm{x}}})$ holds for all $i$. This delayed constraint generation
framework is described in Algorithm 1.

Algorithm 1 A Delayed Constraint Generation Framework for Solving Problem (8)

1: input: Initialization $\mathcal{S}\subseteq\mathcal{C}$;

2: repeat // one iteration

3: Solve problem (9) to obtain its optimal solution
$(\bar{{\bm{x}}},\bar{{\bm{w}}})$;

4: if $\bar{w}_{i}<g_{i}(\bar{{\bm{x}}})$ for some $i$’s then

5:
$\mathcal{S}\leftarrow\mathcal{S}\cup\\{(i,\bar{{\bm{x}}})\mid\bar{w}_{i}<g_{i}(\bar{{\bm{x}}}),\leavevmode\nobreak\
i=1,2,\ldots,M\\}$;

6: else

7: break;

8: end if

9: until $\bar{w}_{i}\geq g_{i}(\bar{{\bm{x}}})$ holds for all $i$;

10: output
$({\bm{x}}^{\star},{\bm{w}}^{\star})=(\bar{{\bm{x}}},\bar{{\bm{w}}})$.

###  III-C An Efficient Branch-and-Bound Algorithm

Algorithm 1 requires (possibly) solving multiple MILP problems in the form of
(9) (e.g., by branch-and-bound algorithms [38]) and solving each MILP problem
can be time-consuming. Therefore, the complexity of Algorithm 1 can still be
high (especially when the number of iterations is large). To further reduce
the computational complexity of Algorithm 1, we propose to solve each MILP
problem (9) inexactly, which is done by embedding the delayed constraint
generation procedure (cf. lines 3-8 in Algorithm 1) into one branch-and-bound
algorithm. Branch-and-bound algorithms are tree search methods that
recursively partition the feasible region (i.e., a rooted tree) into small
subregions (i.e., branches). In particular, our proposed branch-and-bound
algorithm solves the LP relaxation in the form of (12) at each iteration and
gradually tightens the relaxation by adding appropriate $(i,{\hat{{\bm{x}}}})$
in the set $\mathcal{S}$ and fixing more elements of ${\bm{x}}$ to be
$\\{-1,1\\}.$ The resulting algorithm is still a _global_ algorithm to problem
(8). Note that the proposed algorithm only needs to solve an LP problem at
each iteration, which is in sharp contrast to solving the MILP problem (9) in
Algorithm 1. Below, we present the proposed algorithm in more details.

####  III-C1 Subproblems and Their LP Relaxations

Denote $\mathcal{F}_{+}$ and $\mathcal{F}_{-}$ as some subsets of
$\\{1,2,\ldots,N\\}$ such that ${x}_{j}=1$ for $j\in\mathcal{F}_{+}$ and
${x}_{j}=-1$ for $j\in\mathcal{F}_{-}$, and
$\mathcal{F}_{+}\cap\mathcal{F}_{-}=\varnothing$. The subproblem to explore at
the branch defined by $\mathcal{F}_{+}$ and $\mathcal{F}_{-}$ is given by

$\displaystyle\min_{{\bm{x}},{\bm{w}}}$ $\displaystyle\leavevmode\nobreak\
\sum_{i=1}^{M}w_{i}$ s.t. $\displaystyle\leavevmode\nobreak\ w_{i}\geq
g_{i}(\hat{{\bm{x}}})+\langle\nabla
g_{i}(\hat{{\bm{x}}}),{\bm{x}}-\hat{{\bm{x}}}\rangle,\leavevmode\nobreak\
\forall\leavevmode\nobreak\ (i,\hat{{\bm{x}}})\in\mathcal{C},$ (11a)
$\displaystyle\leavevmode\nobreak\ x_{j}=1,\leavevmode\nobreak\
\forall\leavevmode\nobreak\ j\in\mathcal{F}_{+},\leavevmode\nobreak\
x_{j}=-1,\leavevmode\nobreak\ \forall\leavevmode\nobreak\
j\in\mathcal{F}_{-},$ (11b) $\displaystyle\leavevmode\nobreak\
{\bm{x}}\in\\{-1,1\\}^{N}.$ (11c)

Also, consider the following LP relaxation of problem (11):

$\displaystyle\min_{{\bm{x}},{\bm{w}}}$ $\displaystyle\sum_{i=1}^{M}w_{i}$
s.t. $\displaystyle\leavevmode\nobreak\ w_{i}\geq
g_{i}(\hat{{\bm{x}}})+\langle\nabla
g_{i}(\hat{{\bm{x}}}),{\bm{x}}-\hat{{\bm{x}}}\rangle,\leavevmode\nobreak\
\forall\leavevmode\nobreak\ (i,\hat{{\bm{x}}})\in\mathcal{S},$ (12a)
$\displaystyle\leavevmode\nobreak\ x_{j}=1,\leavevmode\nobreak\
\forall\leavevmode\nobreak\ j\in\mathcal{F}_{+},\leavevmode\nobreak\
x_{j}=-1,\leavevmode\nobreak\ \forall\leavevmode\nobreak\
j\in\mathcal{F}_{-},$ (12b) $\displaystyle\leavevmode\nobreak\
{\bm{x}}\in[-1,1]^{N},$ (12c)

where $\mathcal{S}\subseteq\mathcal{C}$. Problem (12) is a relaxation of
problem (11) by replacing $\mathcal{C}$ with $\mathcal{S}$ and by relaxing
binary variables $x_{j}$’s with $j\notin\mathcal{F}_{+}\cup\mathcal{F}_{-}$ to
$[-1,1]$. Therefore, solving the LP problem (12) provides a lower bound for
the MILP problem (11).

####  III-C2 Proposed Algorithm

Now, we present the main steps of the proposed branch-and-bound algorithm
based on the LP relaxation in (12). We use
$(\check{{\bm{x}}},\check{{\bm{w}}})$ to denote the best-known feasible
solution that provides the smallest objective value at the current iteration
and use $U$ to denote its objective value (called the _upper bound_ of problem
(8)). In addition, we use $(\mathcal{F}_{+},\mathcal{F}_{-},\mathcal{S})$ to
denote subproblem (11) where $\mathcal{S}\subseteq\mathcal{C}$ corresponds to
its current LP relaxation (12), and $\mathcal{P}$ to denote the problem set of
the current unprocessed subproblems. At the beginning, we initialize
$\mathcal{P}\leftarrow\\{(\varnothing,\varnothing,\mathcal{S})\\}$ for some
$\mathcal{S}\subseteq\mathcal{C}$. At each iteration, we pick a subproblem
$(\mathcal{F}_{+},\mathcal{F}_{-},\mathcal{S})$ from $\mathcal{P}$, and solve
problem (12) to obtain its solution $({\bm{x}}_{\sf LP},{\bm{w}}_{\sf LP})$
and objective value $f_{\sf LP}=\sum_{i=1}^{N}[{\bm{w}}_{\sf LP}]_{i}$. Then,
one of the following cases must happen:

  * (i)

If $f_{\sf LP}\geq U$, then problem (11) cannot contain a feasible solution
that provides an objective value better than $U$ (and this subproblem does not
need to be explored).

  * (ii)

If $f_{\sf LP}<U$ and ${\bm{x}}_{\sf LP}\in\\{-1,1\\}^{N}$, there are two
subcases.

    * (ii.1)

If $[{\bm{w}}_{\sf LP}]_{i}\geq g_{i}({\bm{x}}_{\sf LP})$ for all
$i=1,2,\ldots,M$, then $({\bm{x}}_{\sf LP},{\bm{w}}_{\sf LP})$ must be an
optimal solution to problem (11). We update
$(\check{{\bm{x}}},\check{{\bm{w}}})\leftarrow({\bm{x}}_{\sf LP},{\bm{w}}_{\sf
LP})$ and $U\leftarrow f_{\sf LP}$.

    * (ii.2)

Otherwise, we apply the delayed constraint generation procedure by adding
$(i,{\bm{x}}_{\sf LP})$ with all $[{\bm{w}}_{\sf LP}]_{i}<g_{i}({\bm{x}}_{\sf
LP})$ into $\mathcal{S}$ to obtain a tightened problem (12).

  * (iii)

If $f_{\sf LP}<U$ and ${\bm{x}}_{\sf LP}\notin\\{-1,1\\}^{N}$, then we choose
an index $j$ with $-1<[{\bm{x}}_{\sf LP}]_{j}<1$ and branch on variable
$x_{j}$ by partitioning problem
$(\mathcal{F}_{+},\mathcal{F}_{-},\mathcal{S})$ into two new subproblems
$(\mathcal{F}_{+}\cup\\{j\\},\mathcal{F}_{-},\mathcal{S})$ and
$(\mathcal{F}_{+},\mathcal{F}_{-}\cup\\{j\\},\mathcal{S})$. We add the two
subproblems into the problem set $\mathcal{P}$.

The above process is repeated until $\mathcal{P}=\varnothing$. The whole
procedure is summarized as Algorithm 2.

Algorithm 2 A Global Algorithm for Solving Problem (8)

1: input: Initialize $\mathcal{P}=\\{(\varnothing,\varnothing,\mathcal{S})\\}$
for some $\mathcal{S}\subseteq\mathcal{C}$ and $U\leftarrow+\infty$.

2: while $\mathcal{P}\neq\varnothing$ do

3: Choose a subproblem
$(\mathcal{F}_{+},\mathcal{F}_{-},\mathcal{S})\in\mathcal{P}$ and set
$\mathcal{P}\leftarrow\mathcal{P}\backslash\\{(\mathcal{F}_{+},\mathcal{F}_{-},\mathcal{S})\\}$;

4: loop

5: Solve the LP problem (12) to obtain its optimal solution $({\bm{x}}_{\sf
LP},{\bm{w}}_{\sf LP})$ and objective value $f_{\sf
LP}=\sum_{i=1}^{N}[{\bm{w}}_{\sf LP}]_{i}$;

6: if ${f}_{\sf LP}\geq U$ then

7: break; // Corresponding to case (i)

8: else if ${\bm{x}}_{\sf LP}\in\\{-1,1\\}^{N}$ then

9: if $[{\bm{w}}_{\sf LP}]_{i}\geq g_{i}({\bm{x}}_{\sf LP})$ for all
$i=1,2,\ldots,M$ then

10: Update $(\check{{\bm{x}}},\check{{\bm{w}}})\leftarrow({\bm{x}}_{\sf
LP},{\bm{w}}_{\sf LP})$ and $U\leftarrow{f}_{\sf LP}$;

11: break; // Corresponding to case (ii.1)

12: else

13: $\mathcal{S}\leftarrow\mathcal{S}\cup\\{(i,{\bm{x}}_{\sf
LP})\mid[{\bm{w}}_{\sf LP}]_{i}<g_{i}({\bm{x}}_{\sf LP}),i=1,2,\ldots,M\\}$;
// Corresponding to case (ii.2)

14: end if

15: else

16: Choose an index $j$ such that $-1<[{\bm{x}}_{\sf LP}]_{j}<1$;

17: Add two new subproblems
$(\mathcal{F}_{+}\cup\\{j\\},\mathcal{F}_{-},\mathcal{S})$ and
$(\mathcal{F}_{+},\mathcal{F}_{-}\cup\\{j\\},\mathcal{S})$ into $\mathcal{P}$;
// Corresponding to case (iii)

18: break;

19: end if

20: end loop

21: end while

22: output
$({\bm{x}}^{\star},{\bm{w}}^{\star})\leftarrow(\check{{\bm{x}}},\check{{\bm{w}}})$.

In lines 3 and 16 of Algorithm 2, there exist different strategies to choose a
subproblem $(\mathcal{F}_{+},\mathcal{F}_{-},\mathcal{S})$ from set
$\mathcal{P}$ and to choose a branching variable index $j$ [38]. It is worth
remarking that Algorithm 2 can be embedded into state-of-the-art MILP solvers
like CPLEX through the so-called _callback routine_ [21], which uses the
(default) fine-tune subproblem selection and branching strategies of MILP
solvers.

##  IV An Amplitude Retrieval Approach

Due to the one-bit quantization, the received signal ${\bm{r}}$ in (1) loses
the amplitude information, which results in a more challenging likelihood
function of the one-bit ML MIMO detection problem (3) compared to that of the
classic MIMO detection problem. In this section, we go for a different
direction by proposing to introduce the amplitude information into the
detection formulation and present a new AR formulation as an alternative to
the one-bit ML MIMO detection (3). Compared with the ML formulation (3), the
proposed AR formulation has a much simpler objective function. This will bring
new opportunities to build efficient algorithms that do not require to
confront the complicated likelihood functions.

###  IV-A AR Formulation

Observe that the probit model (3) keeps the sign information of ${\bm{y}}$ and
thereby loses the amplitude information. We introduce a latent variable
${\bm{z}}\in\mathbb{R}_{+}^{M}$ to denote the missing amplitude information
associated with ${\bm{y}}$, i.e.,

${\bm{y}}={\bm{r}}\odot{\bm{z}},$

where $\odot$ is the elementwise product. With the aid of ${\bm{z}}$, a
natural choice is to minimize the distance between ${\bm{y}}$ and
${\bm{H}}{\bm{x}}$. Specifically, we consider the following problem
formulation which minimizes the $\ell_{1}$ residual $\sum_{i=1}^{M}|r_{i}\cdot
z_{i}-{\bm{h}}_{i}^{\top}{\bm{x}}|$:

$\begin{split}\min_{{\bm{x}},{\bm{z}}}&\leavevmode\nobreak\
\sum_{i=1}^{M}|r_{i}\cdot z_{i}-{\bm{h}}_{i}^{\top}{\bm{x}}|\\\ \mbox{s.t.
}&\leavevmode\nobreak\ {\bm{x}}\in\\{-1,1\\}^{N},\leavevmode\nobreak\
z_{i}\geq 0,\leavevmode\nobreak\ \forall\leavevmode\nobreak\
i=1,2,\ldots,M.\end{split}$ (13)

By noting that $r_{i}\in\\{-1,1\\}$ implies

$|r_{i}\cdot
z_{i}-{\bm{h}}_{i}^{\top}{\bm{x}}|=|z_{i}-r_{i}\cdot{\bm{h}}_{i}^{\top}{\bm{x}}|,$

we can equivalently express problem (13) into a compact form

$\begin{split}\min_{{\bm{x}},{\bm{z}}}&\leavevmode\nobreak\
\|{\bm{z}}-{\bm{B}}{\bm{x}}\|_{1}\\\ \mbox{s.t. }&\leavevmode\nobreak\
{\bm{x}}\in\\{-1,1\\}^{N},\leavevmode\nobreak\ z_{i}\geq
0,\leavevmode\nobreak\ \forall\leavevmode\nobreak\ i=1,2,\ldots,M,\end{split}$
(14)

where ${\bm{B}}=\mbox{Diag}({\bm{r}}){\bm{H}}$.

Problem (14) can be further simplified. Given any ${\bm{x}}$, the optimal
$z_{i}$ to problem (14) is given by

$z_{i}=\max({\bm{b}}_{i}^{\top}{\bm{x}},0),\quad\forall\leavevmode\nobreak\
i=1,2,\ldots,M.$ (15)

By substituting the solution (15) into problem (14), problem (14) can be cast
into

$\begin{split}\min_{{\bm{x}}}&\leavevmode\nobreak\
\sum_{i=1}^{M}\max(-{\bm{b}}_{i}^{\top}{\bm{x}},0)=\|\max(-{\bm{B}}{\bm{x}},\bm{0})\|_{1}\\\
\mbox{s.t. }&\leavevmode\nobreak\ {\bm{x}}\in\\{-1,1\\}^{N}.\end{split}$ (16)

The above AR formulation provides an alternative handle to the one-bit ML MIMO
detection formulation in (3). Below let us compare the two formulations and
reveal more insights.

First, we take a closer look at the term ${\bm{b}}_{i}^{\top}{\bm{x}}$ (or
$r_{i}\cdot{\bm{h}}_{i}^{\top}{\bm{x}}$). Suppose
${\bm{b}}_{i}^{\top}{\bm{x}}>0$, which means $y_{i}$ and the noiseless signal
${\bm{h}}_{i}^{\top}{\bm{x}}$ have the same sign. Intuitively, this is likely
to be true since the noise power $\sigma^{2}$ is usually small compared to the
power of signal ${\bm{H}}{\bm{x}}$. It is seen that the objective function in
(16) endeavors to encourage ${\bm{b}}_{i}^{\top}{\bm{x}}$ for all $i$ being
positive. In fact, the ML formulation (3) has a similar effect, i.e.,
minimizing the $-\log\Phi$ function also pushes ${\bm{b}}_{i}^{\top}{\bm{x}}$
for all $i$ to be positive. If one replaces $\max(-x,0)$ by $-\log\Phi(x)$ in
problem (16), it leads to

$\begin{split}\min_{{\bm{x}}}&\leavevmode\nobreak\
-\sum_{i=1}^{M}\log\Phi({\bm{b}}_{i}^{\top}{\bm{x}})\\\ \mbox{s.t.
}&{\bm{x}}\in\\{-1,1\\}^{N}.\end{split}$ (17)

We see that problem (17) is very similar to the one-bit ML MIMO detection
problem (3), except that problem (17) does not involve the noise standard
variance $\sigma$. This revelation connects the AR formulation with the ML
problem, albeit the former is originally developed from a different rationale
from ML.

Second, the design with the AR rationale can be flexible. Instead of
considering the formulation (13), one can also consider minimizing other
possible loss functions. For example, one can minimize the squared residue,
which is given by

$\begin{split}\min_{{\bm{x}},{\bm{z}}}&\leavevmode\nobreak\
\sum_{i=1}^{M}|r_{i}\cdot z_{i}-{\bm{h}}_{i}^{\top}{\bm{x}}|^{2}\\\ \mbox{s.t.
}&\leavevmode\nobreak\ {\bm{x}}\in\\{-1,1\\}^{N},\leavevmode\nobreak\
z_{i}\geq 0,\leavevmode\nobreak\ \forall\leavevmode\nobreak\
i=1,2,\ldots,M.\end{split}$ (18)

In the same vein of the development in (15)–(16), problem (18) can be cast
into

$\begin{split}\min_{{\bm{x}}}&\leavevmode\nobreak\
\|\max(-{\bm{B}}{\bm{x}},\bm{0})\|_{2}^{2}\\\ \mbox{s.t.}&\leavevmode\nobreak\
{\bm{x}}\in\\{-1,1\\}^{N}.\end{split}$ (19)

It is seen that the objective function in (19) is quadratic in ${\bm{x}}$, and
is simpler than that of one-bit ML MIMO detection problem (3). As discussed
before, the probability ${\bm{b}}_{i}^{\top}{\bm{x}}<0$ is likely to be low,
i.e., only for a small portion of the indices $\\{1,2,\ldots,M\\}$ the cases
${\bm{b}}_{i}^{\top}{\bm{x}}<0$ can happen. This can be understood from a
sparsity pursuit perspective. Motivated by this, we prefer the formulation
(16) to (19), because the $\ell_{1}$-norm has a better capability of pursuing
sparsity than the $\ell_{2}$-norm. We will provide simulations to verify this
in Section V.

We should mention related works. The AR idea was exploited under a different
context, namely, channel estimation for Frobenius norm minimization [39]. The
resulting formulation and algorithm there are different from those of this
paper. In addition, in the context of nonnegative matrix factorization, our
previous work [40] utilized $-\log\Phi(x)$, $\max(-x,0)$, and $\max(-x,0)^{2}$
as penalty functions for promoting nonnegativity. However, it was not derived
from the AR idea.

Third, the objective function of the AR problem (16) is piecewise linear and
convex. This simple form enables to design efficient algorithms that do not
require confronting the challenging likelihood function in the one-bit ML MIMO
detection problem. In particular, we rewrite problem (16) into the following
standard MILP problem

$\begin{split}\min_{{\bm{x}},{\bm{w}}}&\leavevmode\nobreak\
\sum_{i=1}^{M}w_{i}\\\ \mbox{s.t. }&\leavevmode\nobreak\
w_{i}\geq-{\bm{b}}_{i}^{\top}{\bm{x}},\leavevmode\nobreak\
\forall\leavevmode\nobreak\ i=1,2,\ldots,M,\\\ &\leavevmode\nobreak\
{\bm{x}}\in\\{-1,1\\}^{N},\leavevmode\nobreak\
{\bm{w}}\in\mathbb{R}_{+}^{M},\end{split}$ (20)

where we introduce a nonnegative variable ${\bm{w}}$ to play the role of
$\max(\cdot,0)$ in problem (16). In sharp contrast to the one-bit ML MIMO
detection problem (3), the AR problem (16) (or its equivalent MILP form (20))
can be directly solved to global optimality using off-the-shelf MILP solvers
such as CPLEX.

Finally, we present the complexity result of problem (16). Although the AR
problem (16) is much easier to handle than the one-bit ML MIMO detection
problem (3), it is also NP-hard, as detailed in the following theorem.

###### Theorem 2

The AR problem (16) is NP-hard.

Proof: The proof is similar to that of Theorem 1. In particular, we prove that
there exists a special instance of problem (16) which is as hard as the
partition problem.

Given any instance of the partition problem, we construct an instance of
problem (16) by setting $M=2$, $N=n$, $\sigma=1$, ${\bm{b}}_{1}={\bm{w}}$ and
${\bm{b}}_{2}=-{\bm{w}}$. By construction, problem (16) reduces to

${v^{\ast}}=\min_{{\bm{x}}\in\\{-1,1\\}^{n}}\left(\max\left\\{-{\bm{w}}^{\top}{\bm{x}},0\right\\}+\max\left\\{{\bm{w}}^{\top}{\bm{x}},0\right\\}\right)$
(21)

For any ${\bm{x}}\in\\{-1,1\\}^{n}$, we have
$\max\\{-{\bm{w}}^{\top}{\bm{x}},0\\}\geq 0$ and
$\max\\{{\bm{w}}^{\top}{\bm{x}},0\\}\geq 0$, implying that $v^{\ast}\geq 0$.
Moreover, $v^{\ast}=0$ if and only if ${\bm{w}}^{\top}{\bm{x}}=0$ holds for
some ${\bm{x}}\in\\{-1,1\\}^{n}$. Similarly, the latter is equivalent to that
the answer to the partition problem is yes, and hence problem (16) is NP-hard.
$\blacksquare$

In order to strike a better balance between the detection performance and the
computational complexity, we will propose an efficient first-order algorithm
to solve problem (16) in the next subsection.

###  IV-B Alternate Barzilai-Borwein Method for AR Problem (16)

The algorithmic development in this subsection is based on the penalty
technique and the projected gradient (PG) method. More specifically, we first
transform problem (16) into a convex box-constrained smooth problem by a
smoothing technique and a penalty method; then, we apply a modified PG method
to solve the transformed problem. The resulting algorithm has a low per-
iteration complexity.

We begin with a more generic optimization problem of the form:

$\begin{split}\min_{{\bm{x}}}&\leavevmode\nobreak\
\sum_{i=1}^{M}\max\\{{\bm{a}}_{i,1}^{\top}{\bm{x}},{\bm{a}}_{i,2}^{\top}{\bm{x}}\\}\\\
\mbox{s.t. }&\leavevmode\nobreak\ {\bm{x}}\in\\{-1,1\\}^{N},\end{split}$ (22)

where ${\bm{a}}_{i,k}\in\mathbb{R}^{N}$ for all $(i,k)$. The AR problem (16)
is a special case of problem (22) with ${\bm{a}}_{i,1}=-{\bm{b}}_{i}$ and
${\bm{a}}_{i,2}=\bm{0}$ for all $i$.

Problem (22) has two main challenges if we would like to apply first-order
algorithms such as the PG algorithm for solving it: (i) the objective function
is nonsmooth; (ii) the constraint is binary. We tackle the nonsmoothness by
applying the smoothing technique in [41]. To describe, we formulate problem
(22) as a min-max problem as follows:

$\begin{split}\min_{{\bm{x}}}&\leavevmode\nobreak\
\max_{\\{\bm{\theta}_{i}\\}_{i=1}^{M}}\sum_{i=1}^{M}\langle{\bm{A}}_{i}{\bm{x}},\bm{\theta}_{i}\rangle\\\
\mbox{s.t. }&\leavevmode\nobreak\
{\bm{x}}\in\\{-1,1\\}^{N},\leavevmode\nobreak\
\bm{\theta}_{i}\in\Delta_{2},\leavevmode\nobreak\ \forall\leavevmode\nobreak\
i=1,2,\ldots,M,\end{split}$ (23)

where ${\bm{A}}_{i}=[{\bm{a}}_{i,1},\leavevmode\nobreak\
{\bm{a}}_{i,2}]^{\top}$ and

$\Delta_{2}:=\\{\bm{\theta}\in\mathbb{R}^{2}\mid\theta_{1}+\theta_{2}=1,\theta_{1},\theta_{2}\geq
0\\}$

is the two-dimensional unit simplex. The smoothing approximation of problem
(23) is given by

$\begin{split}\min_{{\bm{x}}}&\leavevmode\nobreak\ \varphi({\bm{x}})\\\
\mbox{s.t. }&\leavevmode\nobreak\
{\bm{x}}\in\\{-1,1\\}^{N},\leavevmode\nobreak\ \quad\end{split}$ (24)

where

$\begin{split}\varphi({\bm{x}}):=&\max_{\\{\bm{\theta}_{i}\\}_{i=1}^{M}}{\sum_{i=1}^{M}\left(\langle{\bm{A}}_{i}{\bm{x}},\bm{\theta}_{i}\rangle-\frac{\rho}{2}\|\bm{\theta}_{i}\|_{2}^{2}\right)}\\\
&\leavevmode\nobreak\ \mbox{s.t.
}\bm{\theta}_{i}\in\Delta_{2},\leavevmode\nobreak\ i=1,2,\ldots,M,\\\
\end{split}$ (25)

for a given smoothing parameter $\rho>0$. Obviously, problem (25) reduces to
problem (23) when $\rho=0$. In problem (24), adding the term
$-\frac{\rho}{2}\|\bm{\theta}_{i}\|_{2}^{2}$ makes the function
$\varphi({\bm{x}})$ smooth [41]. As a consequence, the gradient of
$\varphi({\bm{x}})$ is given by

$\nabla\varphi({\bm{x}})=\sum_{i=1}^{M}\langle{\bm{A}}_{i}{\bm{x}},\bm{\theta}_{i}^{\ast}({\bm{x}})\rangle,$
(26)

where $\bm{\theta}_{i}^{\ast}({\bm{x}})$ is the unique optimal solution of the
inner problem within $\varphi({\bm{x}})$ at a fixed ${\bm{x}}$, which can be
obtained in a closed form, i.e.,

$\begin{split}\theta_{i,1}^{\star}({\bm{x}})=&\leavevmode\nobreak\
\left[\frac{\rho+({\bm{a}}_{i,1}-{\bm{a}}_{i,2})^{\top}{\bm{x}}}{2\rho}\right]_{0}^{1},\\\
\theta_{i,2}^{\star}({\bm{x}})=&\leavevmode\nobreak\
1-\theta_{i,1}^{\star}({\bm{x}}),\end{split}$

with $[x]_{a}^{b}:=\max\\{a,\min\\{x,b\\}\\}$ defined as the projection
operator for projecting $x$ onto the interval $[a,b]$. By [41, Theorem 1], the
gradient $\nabla\varphi({\bm{x}})$ is $L_{\varphi}$-Lipschitz continuous,
i.e.,

$\|\nabla\varphi({\bm{x}}_{1})-\nabla\varphi({\bm{x}}_{2})\|_{2}\leq
L_{\varphi}\|{\bm{x}}_{1}-{\bm{x}}_{2}\|_{2},$

for any ${\bm{x}}_{1},{\bm{x}}_{2}\in\mathbb{R}^{N}$, where

$L_{\varphi}=\frac{1}{\rho}\sum_{i=1}^{M}\sigma_{\max}({\bm{A}}_{i})^{2}$

with $\sigma_{\max}({\bm{A}})$ denoting the maximum singular value of
${\bm{A}}$.

Next, we tackle the binary constraint by the extreme-point pursuit penalty
method [5, 42]. Specifically, we further reformulate problem (24) as follows:

$\begin{split}\min_{{\bm{x}}}&\leavevmode\nobreak\
F_{\lambda}({\bm{x}}):=\varphi({\bm{x}})-\lambda\|{\bm{x}}\|_{2}^{2}\\\
\mbox{s.t. }&\leavevmode\nobreak\ {\bm{x}}\in[-1,1]^{N},\end{split}$ (27)

where $\lambda\geq 0$ is a penalty parameter. The crux is to relax the binary
constraint $\\{-1,1\\}^{N}$ as the box constraint $[-1,1]^{N}$, and to use the
negative square penalty $-\lambda\|{\bm{x}}\|_{2}^{2}$ to force the solution
to be an extreme point of $[-1,1]^{N}$, i.e., a point in $\\{-1,1\\}^{N}$.
Based on the result in [5, 42], as long as $\lambda>L_{\varphi}/2$, problems
(24) and (27) have the same optimal solutions. The above transformation turns
the discrete constraint into a continuous one, thereby allowing us to take
advantage of the rich continuous optimization techniques for the algorithmic
design.

Now we are ready to present the first-order algorithm for tackling problem
(27). We apply the ABB method [29]. The ABB method is a PG method with
modified step sizes, which is motivated by Newton’s method but does not
involve any Hessian. To be specific, the step size of the ABB method in the
$\ell$th iteration is given by

$\alpha_{\ell}=\begin{cases}\frac{\|{\bm{s}}_{\ell}\|_{2}^{2}}{|\langle{\bm{s}}_{\ell},\bm{\beta}_{\ell}\rangle|},&\mbox{if
}\ell\mbox{ is even};\\\ \leavevmode\nobreak\ \\\\[-5.69046pt]
\frac{|\langle{\bm{s}}_{\ell},\bm{\beta}_{\ell}\rangle|}{\|\bm{\beta}_{\ell}\|_{2}^{2}},&\mbox{if
}\ell\mbox{ is odd},\end{cases}$ (28)

where

$\begin{split}{\bm{s}}_{\ell}={\bm{x}}_{\ell}-{\bm{x}}_{\ell-1},\leavevmode\nobreak\
\bm{\beta}_{\ell}=\nabla F_{\lambda}({\bm{x}}_{\ell})-\nabla
F_{\lambda}({\bm{x}}_{\ell-1}).\end{split}$ (29)

With the above step size, the ABB method performs the following update

$\begin{split}\bar{{\bm{x}}}_{\ell+1}=&\leavevmode\nobreak\
[{\bm{x}}_{\ell}-\alpha_{\ell}\nabla
F_{\lambda}({\bm{x}}_{\ell})]_{-\bm{1}}^{\bm{1}}.\end{split}$

Then, the ABB method searches the next iterate along the direction

${\bm{d}}_{\ell}=\bar{{\bm{x}}}_{\ell+1}-{\bm{x}}_{\ell}.$

We choose the Grippo-Lampariello-Lucidi (GLL) line search [43], which, given a
chosen $\tau\in(0,1)$, finds $\eta>0$ decreasing from $1$ such that

$\begin{split}F_{\lambda}({\bm{x}}_{\ell}+\lambda{\bm{d}}_{\ell})\leq
f_{r}+\tau\eta\langle\nabla
F_{\lambda}({\bm{x}}_{\ell}),{\bm{d}}_{\ell}\rangle,\\\
f_{r}:=\max\\{F_{\lambda}({\bm{x}}_{\ell-i}):0\leq
i\leq\kappa-1\\}.\end{split}$ (30)

Note that the objective function sequence $\\{F_{\lambda}({\bm{x}}_{\ell})\\}$
obtained by the GLL line search can be nonmonotone. This may help avoid the
solution getting stuck at bad local minima [29].

We apply the above ABB method to solve problem (27), of which the detailed
implementation is shown in Algorithm 3. Note that in the algorithm, we apply
homotopy optimization, which is an optimization paradigm that traces a path
from the solution of an easy problem to that of the target problem by the use
of a homotopy. By doing so, the path-tracing strategy may effectively avoid
bad local minima, as numerical results suggest. It is worth noting that
homotopy optimization was successfully applied in many signal processing and
machine learning applications, demonstrating promising performance; the
readers are referred to [44, 11] and the references therein for more details
of homotopy optimization. Here, the transformation is problem (27) and
$\lambda$ serves as the homotopy parameter. Algorithm 3 starts from a small
$\lambda$ and gradually increases its value. When $\lambda=0$, problem (27) is
a convex relaxation of problem (16) and is easy to solve; when $\lambda$ is
large, problem (27) becomes closer to problem (16).

Algorithm 3 The ABB Method for Problem (27)

1: Initialize ${\bm{x}}_{-1}$, ${\bm{x}}_{0}$, $\lambda$, $\lambda_{\max}$,
$\rho$, $\tau\in(0,1)$, $\kappa$, and $c$; $\ell=0$.

2: while $\lambda<\lambda_{\max}$ do

3: repeat

4: update $\ell\leftarrow\ell+1$

5: calculate
${\bm{s}}_{\ell}\leftarrow{\bm{x}}_{\ell}-{\bm{x}}_{\ell-1},\quad\bm{\beta}_{\ell}\leftarrow\nabla
F_{\lambda}({\bm{x}}_{\ell})-\nabla F_{\lambda}({\bm{x}}_{\ell-1});$

6: calculate the ABB step size according to (28);

7: update $\bm{\theta}_{i}$’s according to
$\theta_{i,1}^{\ell}\leftarrow\left[\frac{\rho-{\bm{b}}_{i}^{\top}{\bm{x}}_{\ell}}{2\rho}\right]_{0}^{1},\quad\leavevmode\nobreak\
\forall\leavevmode\nobreak\ i=1,2,\ldots,M;$

8: calculate the gradient  $\begin{split}\nabla
F_{\lambda}({\bm{x}}_{\ell})\leftarrow-\sum_{i=1}^{M}\theta_{i,1}^{\ell}{\bm{b}}_{i}-2\lambda{\bm{x}}_{\ell};\end{split}$

9: calculate
$\begin{split}\bar{{\bm{x}}}_{\ell+1}\leftarrow&\leavevmode\nobreak\
[{\bm{x}}_{\ell}-\alpha_{\ell}\nabla
F_{\lambda}({\bm{x}}_{\ell})]_{-\bm{1}}^{\bm{1}};\end{split}$

10: calculate the line search direction
${\bm{d}}_{\ell}\leftarrow\bar{{\bm{x}}}_{\ell+1}-{\bm{x}}_{\ell};$

11: apply the GLL line search to get $\eta$ according to (30);

12: set ${\bm{x}}_{\ell+1}\leftarrow{\bm{x}}_{\ell}+\eta{\bm{d}}_{\ell}$;

13: until $\|{\bm{x}}_{\ell+1}-{\bm{x}}_{\ell}\|_{2}\leq\epsilon$ for some
$\epsilon>0$.

14: $\lambda\leftarrow\lambda\cdot c$

15: end while

##  V Simulation Results

This section presents simulation results of different algorithms for solving
the one-bit MIMO detection problem. First, we provide simulation results to
compare different formulations and provide insights. Then, we test the BER
performance of the proposed methods and state-of-the-art designs. Finally, we
compare the computational complexity of different algorithms.

We generate the simulation data according to the complex model (2) and then
transform them into the real-valued data. The channel matrix
$\tilde{{\bm{H}}}$ is generated by the element-wise i.i.d. complex circular
Gaussian distribution with zero mean and unit variance. The elements of
$\tilde{{\bm{x}}}$, the symbols, are independently and identically distributed
(i.i.d.) and drawn from the binary constellation $\\{\pm
1\pm\mathfrak{j}\\}^{\tilde{N}}$. The signal-to-noise ratio (SNR) is defined
as

${\rm
SNR}=\frac{\mathbb{E}[\|\tilde{{\bm{H}}}\tilde{{\bm{x}}}\|_{2}^{2}]}{\mathbb{E}[\|\tilde{{\bm{v}}}\|_{2}^{2}]}.$

A total number of 5,000 Monte-Carlo trials were run to obtain the BER and
runtimes of our proposed algorithms and the benchmarked algorithms.

We need to specify the settings for Algorithms 2 and 3. In Algorithm 2, we
initialize $\mathcal{S}$ as $\\{(i,\hat{{\bm{x}}})\mid i=1,2,\ldots,M\\}$
where $\hat{{\bm{x}}}$ is a quantized zero-forcing (ZF) solution, i.e.,
$\hat{{\bm{x}}}=\mbox{sgn}({{\bm{H}}}^{{\dagger}}{{\bm{r}}})$. We initialize
Algorithm 3 by a Bussgang theorem-inspired ZF scheme

${\bm{x}}_{-1}={\bm{x}}_{0}=\frac{\sqrt{\pi(N+\sigma^{2})}}{2}({\bm{H}}^{\top}{\bm{H}}+\sigma^{2}{\bm{I}})^{-1}{\bm{H}}^{\top}({\bm{r}}-{\bm{d}}),$

where ${\bm{d}}$ is a random realization of ${\cal
N}(\bm{0},(1-2/\pi){\bm{I}})$; see [45]. The parameter $\lambda$ is
initialized as $\lambda=0.1\cdot N$. We set $\lambda_{\max}=100$ ,
$\rho=0.3+\log(1+\sigma)$, $\tau=0.1$, $\kappa=4$, and $c=5$.

###  V-A Validation of Different Formulations

(a) $M=128$, $N=16$

(b) $M=256$, $N=32$

Figure 1: The ratio between the total number of $i$ with
${\bm{b}}_{i}^{\top}{\bm{x}}<0$ and $M$.

We first conduct a simulation to validate the effectiveness of the AR
formulations. Based on the discussion in Section IV, it is expected that the
probability of ${\bm{b}}_{i}^{\top}{\bm{x}}<0$ is low, especially when the SNR
is medium to high. We verify this intuition by counting the ratio of
${\bm{b}}_{i}^{\top}{\bm{x}}<0$ for the solutions of different formulations;
in other words, we would like to see in the signal model (1) how many elements
of the received signal ${\bm{y}}$ have opposite signs with the noiseless
signal ${\bm{H}}{\bm{x}}$.

In Fig. 1, we consider (i) the ground-truth transmit signal ${\bm{x}}_{\sf
GT}$; (ii) the ML solution ${\bm{x}}_{\sf ML}$ of problem (3); (iii) the
solution ${\bm{x}}_{\sf AR\mh L1}$ of problem (16), namely “AR-L1” in the
legend; and (iv) the solution ${\bm{x}}_{\sf AR\mh L2}$ to the squared-loss AR
variant (19), namely “AR-L2” in the legend. The solutions in (ii)–(iv) are
obtained by globally solving the corresponding problem formulations,
respectively.

It can be seen from Fig. 1 that the ground-truth transmit signal
${\bm{x}}_{\sf GT}$ yields a low ratio of the sign change (between $y_{i}$ and
${\bm{h}}_{i}^{\top}{\bm{x}}_{\sf GT}$), which coincides with the intuition
that noise can only affect a small portion of the signs, as discussed in
Section IV-A. Moreover, we can observe from Fig. 1 that the solutions to ML,
AR-L1, and AR-L2 also yield comparably low ratios, which from this perspective
validates the efficacy of ML and AR formulations. In particular, when the SNR
is low to medium, we see that both ML and AR-L1 are close to the ground truth,
while AR-L2 has a higher ratio than the others. The above observations suggest
that the AR-L1 formulation may better approximate the ML formulation than
AR-L2.

###  V-B BER Performance

This subsection examines the BER performance of our proposed methods and
state-of-the-art designs. The considered methods are as follows:

  1. (i)

quantized ZF detector[22], abbreviated herein as “quant. ZF”;

  2. (ii)

ML problem (3), globally solved by Algorithm 2, abbreviated as “gML”;

  3. (iii)

ML problem (3), a penalty method in our recent work [11], abbreviated as
“HOTML”;

  4. (iv)

AR problem (16), globally solved by calling CPLEX, abbreviated as “AR-L1”;

  5. (v)

AR problem (16), handled by Algorithm 3, abbreviated as “AR-L1-ABB”;

  6. (vi)

AR problem (19) with the squared loss, globally solved by calling CPLEX,
abbreviated as “AR-L2”;

  7. (vii)

near-maximum likelihood method, abbreviated as “nML” [9];

  8. (viii)

two-stage improved version of nML, abbreviated as “two-stage nML” [9].

(a) $M=36$, $N=8$

(b) $M=128$, $N=16$

(c) $M=256$, $N=32$

Figure 2: BER performance of all compared approaches under different problem
sizes.

The BER performance of all the above listed methods under different system
sizes is shown in Fig. 2. First, it is seen from the figure that gML achieves
the best BER performance, while AR-L1 and AR-L2 follow with a slightly worse
BER performance. We can also see from Fig. 2 that AR-L1 performs better than
AR-L2, which again gives support to our intuition that the $\ell_{1}$-loss is
more preferred than the $\ell_{2}$-loss in this problem. Second, it can be
observed that the AR-L1-ABB method achieves a slightly worse BER performance
than globally solving it by calling CPLEX, and the performance gap becomes
narrow as the problem size increases. In fact, the AR-L1-ABB method achieves a
comparable competitive performance with HOTML [11]. In addition, both
AR-L1-ABB method and HOTML perform much better than nML and its improved two-
stage version. We will see in the coming subsection that the promising
performance of the AR-L1 method is achieved with a low computational
complexity.

###  V-C Runtime Comparison

(a) $M/N=4$, SNR = $10$ dB

(b) $M/N=8$, SNR = $20$ dB

Figure 3: Runtime performance of all compared approaches with varying problem
sizes.

In this subsection, we compare the runtime performance of the considered
algorithms under different simulation settings. First, we test how the average
runtimes of the algorithms scale with the problem size. The results are shown
in Fig. 3. We increase $M$ and $N$ proportionally with fixed ratios $M/N$,
with the SNR being fixed. From Fig. 3, we see that the exhaustive search has a
rapidly increasing runtime; when the problem size is large, it can be more
than 100 times slower than the other algorithms. By comparison, the runtime of
gML scales much better than the exhaustive search. It can be seen from Fig. 3
that AR-L2 and AR-L1 are also computationally efficient. In particular, AR-L1
is the faster one between the two. It is worth noting that the AR-L1-ABB
method exhibits an attractively low running time, which is faster than HOTML.
This, combined with its outstanding BER performance, makes AR-L1-ABB a
competitive candidate algorithm.

To get a better idea with the efficiency of gML, we show the ratio
$|\mathcal{S}|/|\mathcal{C}|$ when gML converges and outputs a global optimal
solution to the ML problem (3). The result is shown in Fig. 4. We set $M=256$
and SNR$=10$ dB, and vary $N$. It can be seen from Fig. 4 that the ratio
$|\mathcal{S}|/|\mathcal{C}|$ is below $1\%$, which means that gML only needs
to solve LP relaxation subproblems that involve less than $1\%$ linear
inequality constraints than problem (8). It is also encouraging to see that as
the number of users increases, the ratio keeps decreasing rapidly. This
indicates that gML has good scalability for massive systems with many users.

Figure 4: The ratio $|\mathcal{S}|/|\mathcal{C}|$ when gML converges.

Fig. 5 shows the average runtimes of the considered algorithms under different
SNRs with fixed problem sizes. It is seen from the figure that the averaged
runtimes of the global algorithms, including gML, AR-L1 and AR-L2, decrease
rapidly with the SNR. On the other hand, the PG-based methods, including
HOTML, nML and AR-L1-ABB, do not show such a significant decreasing runtime
phenomenon. In addition, it is seen from Fig. 5 that nML and HOTML, which
tackle the one-bit ML MIMO problem, show gradually increasing runtimes with
the SNR. Indeed, our recent work [14] showed that the PG-based methods for
handling the one-bit ML MIMO detection problem (3) may require more number of
iterations to converge for high SNR regions. By comparison, the AR-L1-ABB
method handles the AR formulation (16) that has a different objective function
and does not have such issues. Fig. 5 shows that the runtime performance of
AR-L1-ABB does not grow with the SNR.

(a) $M=128$, $N=16$

(b) $M=256$, $N=32$

Figure 5: Runtime performance of all compared algorithms with varying SNRs.

##  VI Conclusion

In this paper, we have proposed new formulations and efficient algorithms for
the one-bit MIMO detection problem. We first developed an efficient global
algorithm for one-bit ML MIMO detection. The proposed global algorithm is a
customized branch-and-bound algorithm and can solve the one-bit ML MIMO
detection problem with a significantly reduced runtime compared to the
complete enumeration approach for large-sized problem instances. The global
algorithm provides an important performance benchmark for performance
evaluation of various existing approximate algorithms for the same problem.
Moreover, we have proposed a new AR formulation which introduces an explicit
amplitude variable and minimizes the $\ell_{1}$-norm residual between the
reconstructed unquantized received signal and the noiseless received signal.
The proposed AR formulation exhibits a simpler objective compared to that in
the ML formulation. We have further devised an efficient first-order algorithm
tailored for the resulting AR formulation. Our numerical results demonstrated
that the proposed AR formulation can achieve a competitive BER performance
while maintaining a low computational complexity, thereby striking a balance
between the BER performance and the runtime.

## References

  * [1] C.-Y. Yu, M. Shao, W.-K. Chen, Y.-F. Liu, and W.-K. Ma, “An efficient global algorithm for one-bit maximum-likelihood MIMO detection,” in _Proc. IEEE Int. Workshop Signal Process. Advances Wireless Commun. (SPAWC)_ , 2023, pp. 231–235.
  * [2] S. Jacobsson, G. Durisi, M. Coldrey, T. Goldstein, and C. Studer, “Quantized precoding for massive MU-MIMO,” _IEEE Trans. Commun._ , vol. 65, no. 11, pp. 4670–4684, Jul. 2017.
  * [3] H. Jedda, A. Mezghani, A. L. Swindlehurst, and J. A. Nossek, “Quantized constant envelope precoding with PSK and QAM signaling,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 12, pp. 8022–8034, Oct. 2018.
  * [4] F. Sohrabi, Y.-F. Liu, and W. Yu, “One-bit precoding and constellation range design for massive MIMO with QAM signaling,” _IEEE J. Sel. Topics Signal Process._ , vol. 12, no. 3, pp. 557–570, Apr. 2018.
  * [5] M. Shao, Q. Li, W.-K. Ma, and A. M.-C. So, “A framework for one-bit and constant-envelope precoding over multiuser massive MISO channels,” _IEEE Trans. Signal Process._ , vol. 67, no. 20, pp. 5309–5324, Aug. 2019\.
  * [6] A. Li, F. Liu, C. Masouros, Y. Li, and B. Vucetic, “Interference exploitation 1-bit massive MIMO precoding: A partial branch-and-bound solution with near-optimal performance,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 5, pp. 3474–3489, Feb. 2020.
  * [7] Z. Wu, J. Ma, Y.-F. Liu, and A. L. Swindlehurst, “Asymptotic SEP analysis and optimization of linear-quantized precoding in massive MIMO systems,” _IEEE Trans. Inf. Theory_ , vol. 70, no. 4, pp. 2566–2589, Apr. 2023.
  * [8] C. Risi, D. Persson, and E. G. Larsson, “Massive MIMO with 1-bit ADC,” 2014\. [Online]. Available: https://arxiv.org/pdf/1404.7736.pdf
  * [9] J. Choi, J. Mo, and R. W. Heath, “Near maximum-likelihood detector and channel estimator for uplink multiuser massive MIMO systems with one-bit ADCs,” _IEEE Trans. Commun._ , vol. 64, no. 5, pp. 2005–2018, May 2016.
  * [10] C. Studer and G. Durisi, “Quantized massive MU-MIMO-OFDM uplink,” _IEEE Trans. Commun._ , vol. 64, no. 6, pp. 2387–2399, Jun. 2016.
  * [11] M. Shao and W.-K. Ma, “Binary MIMO detection via homotopy optimization and its deep adaptation,” _IEEE Trans. Signal Process._ , vol. 69, pp. 781–796, Dec. 2020.
  * [12] S. H. Mirfarshbafan, M. Shabany, S. A. Nezamalhosseini, and C. Studer, “Algorithm and VLSI design for 1-bit data detection in massive MIMO-OFDM,” _IEEE Open J. Circuits Syst._ , vol. 1, pp. 170–184, Sep. 2020\.
  * [13] D. Plabst, J. Munir, A. Mezghani, and J. A. Nossek, “Efficient non-linear equalization for 1-bit quantized cyclic prefix-free massive MIMO systems,” in _Proc. 15th Int. Symposium Wireless Commun. Syst. (ISWCS)_ , Aug. 2018\.
  * [14] M. Shao, W.-K. Ma, J. Liu, and Z. Huang, “Accelerated and deep expectation maximization for one-bit MIMO-OFDM detection,” _IEEE Trans. Signal Processing_ , vol. 72, pp. 1094–1113, Jan. 2024.
  * [15] Y.-S. Jeon, N. Lee, S.-N. Hong, and R. W. Heath, “One-bit sphere decoding for uplink massive MIMO systems with one-bit ADCs,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 7, pp. 4509–4521, Jul. 2018.
  * [16] L. V. Nguyen, A. L. Swindlehurst, and D. H. Nguyen, “Linear and deep neural network-based receivers for massive MIMO systems with one-bit ADCs,” _IEEE Trans. Wireless Commun._ , vol. 20, no. 11, pp. 7333–7345, Nov. 2021\.
  * [17] S. Khobahi, N. Shlezinger, M. Soltanalian, and Y. C. Eldar, “LoRD-Net: Unfolded deep detection network with low-resolution receivers,” _IEEE Trans. Signal Process._ , vol. 69, pp. 5651–5664, Oct. 2021.
  * [18] M. Shao, W.-K. Ma, and J. Liu, “An explanation of deep MIMO detection from a perspective of homotopy optimization,” _IEEE Open J. Signal Process._ , vol. 4, pp. 108–116, Feb. 2023.
  * [19] Z. Yi, P. Wei, J. Zhu, and H. Zhang, “1-bit massive MIMO signal detector based on convex integral quadratic programming,” _IEEE Trans. Wireless Commun., Early Access_ , Sep. 2023.
  * [20] M. O. Damen, H. El Gamal, and G. Caire, “On maximum-likelihood detection and the search for the closest lattice point,” _IEEE Trans. Inf. Theory_ , vol. 49, no. 10, pp. 2389–2402, Oct. 2003.
  * [21] CPLEX, “User’s manual for CPLEX,” https://www.ibm.com/docs/en/icos/20.1.0?topic=cplex-users-manual, 2022 (accessed Apr. 2023).
  * [22] J. Choi, D. J. Love, D. R. Brown, and M. Boutin, “Quantized distributed reception for MIMO wireless systems using spatial multiplexing,” _IEEE Trans. Signal Process._ , vol. 63, no. 13, pp. 3537–3548, Jul. 2015\.
  * [23] Y. Li, C. Tao, G. Seco-Granados, A. Mezghani, A. L. Swindlehurst, and L. Liu, “Channel estimation and performance analysis of one-bit massive MIMO systems,” _IEEE Trans. Signal Process._ , vol. 65, no. 15, pp. 4075–4089, Aug. 2017.
  * [24] L. V. Nguyen, A. L. Swindlehurst, and D. H. Nguyen, “SVM-based channel estimation and data detection for one-bit massive MIMO systems,” _IEEE Trans. Signal Process._ , vol. 69, pp. 2086–2099, Mar. 2021.
  * [25] C.-K. Wen, C.-J. Wang, S. Jin, K.-K. Wong, and P. Ting, “Bayes-optimal joint channel-and-data estimation for massive MIMO with low-precision ADCs,” _IEEE Trans. Signal Process._ , vol. 64, no. 10, pp. 2541–2556, May 2016\.
  * [26] S. S. Thoota and C. R. Murthy, “Variational Bayes’ joint channel estimation and soft symbol decoding for uplink massive MIMO systems with low resolution ADCs,” _IEEE Trans. Commun._ , vol. 69, no. 5, pp. 3467–3481, May 2021.
  * [27] H. Pirzadeh, G. Seco-Granados, S. Rao, and A. L. Swindlehurst, “Spectral efficiency of one-bit sigma-delta massive MIMO,” _IEEE J. Sel. Areas Commun._ , vol. 38, no. 9, pp. 2215–2226, Jun. 2020.
  * [28] S. Verdú, “Computational complexity of optimum multiuser detection,” _Algorithmica_ , vol. 4, no. 1, pp. 303–312, Jun. 1989.
  * [29] Y.-H. Dai and R. Fletcher, “Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming,” _Numer. Math._ , vol. 100, no. 1, pp. 21–47, Feb. 2005.
  * [30] P. H. Tan and L. K. Rasmussen, “The application of semidefinite programming for detection in CDMA,” _IEEE J. Sel. Areas Commun._ , vol. 19, no. 8, pp. 1442–1449, Aug. 2001.
  * [31] W.-K. Ma, T. N. Davidson, K. M. Wong, Z.-Q. Luo, and P.-C. Ching, “Quasi-maximum-likelihood multiuser detection using semi-definite relaxation with application to synchronous CDMA,” _IEEE Trans. Signal Process._ , vol. 50, no. 4, pp. 912–922, Apr. 2002.
  * [32] D. Wübben, D. Seethaler, J. Jalden, and G. Matz, “Lattice reduction,” _IEEE Signal Process. Mag._ , vol. 28, no. 3, pp. 70–91, Apr. 2011.
  * [33] C. Lu, Y.-F. Liu, W.-Q. Zhang, and S. Zhang, “Tightness of a new and enhanced semidefinite relaxation for MIMO detection,” _SIAM J. Optim._ , vol. 29, no. 1, pp. 719–742, Mar. 2019.
  * [34] S. Yang and L. Hanzo, “Fifty years of MIMO detection: The road to large-scale MIMOs,” _IEEE Commun. Surveys & Tuts_, vol. 17, no. 4, pp. 1941–1988, Sep. 2015.
  * [35] P.-F. Zhao, Q.-N. Li, W.-K. Chen, and Y.-F. Liu, “An efficient quadratic programming relaxation based algorithm for large-scale MIMO detection,” _SIAM J. Optim._ , vol. 31, no. 2, pp. 1519–1545, Mar. 2021.
  * [36] M. R. Garey and D. S. Johnson, ““ Strong” NP-completeness results: Motivation, examples, and implications,” _J. ACM_ , vol. 25, no. 3, pp. 499–508, Jul. 1978.
  * [37] D. Bertsimas and J. N. Tsitsiklis, _Introduction to Linear Optimization_. Athena Scientific Belmont, MA, 1997.
  * [38] T. Achterberg, “SCIP: Solving constraint integer programs,” _Math. Program. Comput._ , vol. 1, no. 1, pp. 1–41, Jul. 2009.
  * [39] C. Qian, X. Fu, and N. D. Sidiropoulos, “Amplitude retrieval for channel estimation of MIMO systems with one-bit ADCs,” _IEEE Signal Process. Lett._ , vol. 26, no. 11, pp. 1698–1702, Nov. 2019.
  * [40] C. Huang, M. Shao, W.-K. Ma, and A. M.-C. So, “SISAL revisited,” _SIAM J. Imag. Sci._ , vol. 15, no. 2, pp. 591–624, 2022.
  * [41] Y. Nesterov, “Smooth minimization of non-smooth functions,” _Math. Program._ , vol. 103, no. 1, pp. 127–152, May 2005.
  * [42] J. Liu, Y. Liu, W.-K. Ma, M. Shao, and A. M.-C. So, “Extreme point pursuit–Part I: A framework for constant modulus optimization,” 2024. [Online]. Available: https://arxiv.org/pdf/2403.06506.pdf
  * [43] L. Grippo, F. Lampariello, and S. Lucidi, “A nonmonotone line search technique for Newton’s method,” _SIAM J. Numer. Anal._ , vol. 23, no. 4, pp. 707–716, Aug. 1986.
  * [44] L. Xiao and T. Zhang, “A proximal-gradient homotopy method for the sparse least-squares problem,” _SIAM J. Optim._ , vol. 23, no. 2, pp. 1062–1091, May 2013.
  * [45] J. J. Bussgang, “Crosscorrelation functions of amplitude-distorted Gaussian signals,” _MIT Res. Lab. Electron., Cambridge, MA, USA, Tech. Rep. 216_ , 1952.