# Device Activity Detection in mMTC with Low-Resolution ADC: A New Protocol

Zhaorui Wang, Ya-Feng Liu, Ziyue Wang, Liang Liu, Haoyuan Pan, and Shuguang
Cui Z. Wang and S. Cui are with the Future Network of Intelligence Institute,
and the School of Science and Engineering, The Chinese University of Hong
Kong, Shenzhen, China, 518172 (e-mail: {wangzhaorui,
shuguangcui}@cuhk.edu.cn). Y.-F. Liu and Z. Wang are with the State Key
Laboratory of Scientific and Engineering Computing, Institute of Computational
Mathematics and Scientific/Engineering Computing, Academy of Mathematics and
Systems Science, Chinese Academy of Sciences, Beijing 100190, China (e-mail:
{yafliu, ziyuewang}@lsec.cc.ac.cn). L. Liu is with the Department of
Electronic and Information Engineering, The Hong Kong Polytechnic University,
Hong Kong (e-mail: liang-eie.liu@polyu.edu.hk). H. Pan is with College of
Computer Science and Software Engineering, Shenzhen University, Shenzhen,
China (e-mail: hypan@szu.edu.cn).

###### Abstract

This paper investigates the effect of low-resolution analog-to-digital
converters (ADCs) on device activity detection in massive machine-type
communications (mMTC). The low-resolution ADCs induce two challenges on the
device activity detection compared with the traditional setup with the
assumption of infinite ADC resolution. First, the codebook design for signal
quantization by the low-resolution ADC is particularly important since a good
design of the codebook can lead to small quantization error on the received
signal, which in turn has significant influence on the activity detector
performance. To this end, prior information about the received signal power is
needed, which depends on the number of active devices $K$. This is sharply
different from the activity detection problem in traditional setups, in which
the knowledge of $K$ is not required by the BS as a prerequisite. Second, the
covariance-based approach achieves good activity detection performance in
traditional setups while it is not clear if it can still achieve good
performance in this paper. To solve the above challenges, we propose a
communication protocol that consists of an estimator for $K$ and a detector
for active device identities: 1) For the estimator, the technical difficulty
is that the design of the ADC quantizer and the estimation of $K$ are closely
intertwined and doing one needs the information/execution from the other. We
propose a progressive estimator which iteratively performs the estimation of
$K$ and the design of the ADC quantizer; 2) For the activity detector, we
propose a custom-designed stochastic gradient descent algorithm to estimate
the active device identities. Numerical results demonstrate the effectiveness
of the communication protocol.

###### Index Terms:

Massive machine-type communications (mMTC), random access, low-resolution ADC,
covariance-based approach

##  I Introduction

###  I-A Motivation

Massive machine-type communications (mMTC) provide efficient random access for
a large number of devices, out of which only a small number of them are
active[1, 2]. For example, a lot of sensors are deployed in a metering system,
while only a small group of them is active to report their status to a BS.
mMTC is expected to play an essential role in 5G/6G systems, with the promise
to revolutionize manufacturing, healthcare, logistics, and process automation
in our future world[3]. A key challenge in mMTC is how to efficiently identify
the active devices since the knowledge of the device activity is quite
important for the subsequent signal processing.

There are generally two kinds of approaches to detect active devices. One is
the compressed sensing (CS) technique by taking advantage of the sporadic
nature of the device activity pattern [4, 5, 6, 7, 8, 9, 10, 11]. The other is
the covariance-based method by making use of the covariance of received
signals[12, 13, 14, 15, 16, 17, 18, 19, 20, 21]. First, [11, 12] have shown
that, the massive multiple-input and multiple-output (MIMO) technique can
improve the performance of the device activity detector significantly. Second,
for the same activity detection performance, the minimum preamble sequence
length required by the covariance-based approach is much smaller than that by
the CS approach[13, 12]. In this paper, considering the merits of the massive
MIMO and covariance-based approach, we study the active device detection
problem through the covariance-based method in mMTC enabled by massive MIMO.

Nowadays, the massive MIMO has been widely deployed in 5G cellular systems,
and will be a key enabler in 6G cellular systems since the massive MIMO can
provide huge beamforming gain[22]. However, there are several problems in
massive MIMO itself. Specifically, in MIMO systems, each antenna equips with a
RF chain which consists of an analog-to-digital converter (ADC). The ADC
converts analog signals to digital signals for baseband processing. The
traditional MIMO system applies high-resolution ADCs for good signal
quantization performance. Note that the high-resolution ADC is not only
expensive, but also power consuming[23, 24, 25]. When it comes to massive
MIMO, since the number of antennas is quite large, the number of ADCs is also
quite large. In this case, if we still apply high-resolution ADC in the
massive MIMO systems, the overall cost would be quite huge. Thus, to solve the
above problems while still harvesting the beamforming gain from massive MIMO,
[26, 27] propose low-resolution ADCs in massive MIMO.

In this paper, we study the device activity detection problem in massive MIMO
under the low-resolution ADCs to reduce the overall cost. This setup makes the
treatment for the device activity detection problem different from that in the
traditional setups which assume ADCs have infinite-resolution[4, 11, 5, 6, 7,
8, 9, 10, 15, 13, 12, 16, 17, 14, 18, 19], for the following two aspects.
First, in this paper, the codebook design for received-signal quantization by
the low-resolution ADC is particularly important since a good design of the
codebook can lead to small quantization error of the received signal, which in
turn has significant influence on the activity detector performance. To this
end, prior information about the received signal power is needed, which
depends on the number of active devices $K$. That is, a large $K$ possibly
induces large received signal power, and vice versa. This is sharply different
from the activity detection problem in the traditional setup, in which the
knowledge of $K$ is not required by the BS as a prerequisite. In this case,
how to get the knowledge of $K$ at the BS is the first challenge.

Second, the covariance-based approach achieves good activity detection
performance in traditional setups since the covariance matrix of the received
signals can be well approximated by the received-quantized signals under ADC
with infinite-resolution in massive MIMO. However, in this paper, since the
received signals are quantized under low-resolution ADCs, the approximation
error of the covariance matrix would be quite large. In this case, how to
design an activity detector based on the received-quantized signals under low-
resolution ADC is the second challenge.

###  I-B Contributions

In this paper, we consider the activity detection problem in mMTC with low-
resolution ADC and propose efficient approaches to solving the corresponding
detection problem, which thus address the above two challenges. The main
contributions of this paper are summarized as follows.

First, we put forth a communication protocol to solve the detection problem
where the antennas at the BS have low-resolution ADCs. The overall
communication is divided into two phases. In phase I, we design an estimator
for the number of active devices $K$. Based on the estimated $K$, the BS
designs the ADC quantizer accordingly; In phase II, the BS detects the active
device identities based on the received signals quantized by low-resolution
ADCs.

Second, we design a detector for active devices in Phase II of the
communication protocol, assuming that the BS already has an estimation of $K$.
In the traditional setup with infinite-resolution ADC, the activity detection
problem can be efficiently solved by the traditional gradient descent
algorithm. However, the gradient in this paper is hard to compute due to the
low-resolution ADC sampling. We solve this problem through a custom-designed
stochastic gradient descent (SGD) algorithm[28] by exploiting the structure of
the problem judiciously. We evaluate the performance of the designed detector.
We test the detector under correlated Rayleigh fading channels. The numerical
results show that, when $K$ is perfectly estimated by the BS, by only applying
a 4-bit ADC quantizer, our detector can achieve nearly the same performance as
that with infinite-resolution ADC quantizer. We also evaluate the performance
of the detector when $K$ is imperfectly estimated by the BS. The numerical
results show that the imperfect knowledge of $K$ can have a significant
penalty on the performance of the detector.

Third, we propose an estimator for $K$ in Phase I of the communication
protocol. In Phase I, the received signals to estimate $K$ still need to go
through the ADC quantizer, while the design of which still need the
information of $K$. Thus, the technical difficulty here is that the design of
the ADC quantizer and the estimation of $K$ are closely intertwined and doing
one needs the information/execution from the other. We propose a progressive
estimator, which iteratively performs the estimation of the number of the
active devices $K$ and the design of the quantizer. The numerical results
demonstrate the effectiveness of the proposed estimator.

###  I-C Related Work

For the device activity detection problem under infinite-resolution ADC, there
are generally two lines of research. The first line of research is to apply
the compressed sensing (CS) technique by taking advantage of the sporadic
nature of the device activity pattern [4, 11, 5, 6, 7, 8, 9, 10]. The second
line of research is to apply the covariance-based approach[13, 15, 12, 16, 17,
14, 18, 19, 20, 21]. Specifically, the activity can be detected merely based
on the covariance matrix of the received signals since the active device
pattern is contained in the covariance matrix. Unlike [4, 11, 5, 6, 7, 8, 9,
10, 13, 15, 12, 16, 17, 14, 18, 19, 20, 21], we study the device activity
detection problem under low-resolution ADCs at the BS.

For the device activity detection problem under low-resolution ADC, there are
few works[29, 30, 31]. Specifically, [29] studied the problem when the BS has
low-resolution ADCs and the end devices have 1-bit ADCs. In addition, [30, 31]
studied the problem under mixed ADCs at the BS, in which parts of ADCs have
infinite-resolution and the others have low-resolution. The key differences
between this paper and the works in [29, 30, 31] are twofold. First, [29, 30,
31] solved the problem by applying the CS approach. Unlike them, we design a
detector for active devices through the covariance-based approach. Second,
[29, 30, 31] implicitly assume that the knowledge of the number of active
devices $K$ is perfectly known at the BS as a priori. Unlike them, we consider
a more general case where the knowledge of $K$ and its statistics are unknown
at the BS. We demonstrate the significant effect of the knowledge $K$ on the
activity detection performance, and propose an estimator to estimate $K$.

###  I-D Organization

The rest of this paper is organized as follows. In Section II, we introduce
the system model, and show that the ADC quantizer design is affected by $K$.
In addition, we also propose a communication protocol that consists of an
estimator for $K$ and an detector for device identities. Assuming the
knowledge of $K$ has been estimated by the BS, we design a detector for active
devices in Section III. We also evaluate the performance of the designed
detector in Section IV. In Section V, we design an estimator for $K$. We also
evaluate the performance of the estimator and the overall communication
protocol. Finally, we conclude this paper in Section VI.

##  II System Model and Communication Protocol

###  II-A System Model

We study a narrowband uplink system which consists of a BS equipped with $M$
antennas and $N$ single-antenna devices. The propagation distance is assumed
to be far larger than the array aperture at the BS so that the devices are in
the far-field of the array. Due to the sporadic traffic, only $K\ll N$ devices
are active at each coherence block. Let $\alpha_{n}$ be an activity indicator
of device $n$, and

$\alpha_{n}=\left\\{\begin{array}[]{ll}1,~{}{\rm if~{}device}~{}n~{}{\rm
is~{}active},\\\ 0,~{}{\rm otherwise},\end{array}~{}~{}n=1,2,\dots,N.\right.$
(1)

We assume block-fading channels, i.e., the channels remain roughly constant
within each coherence block, but may vary among different coherence blocks.
Let $\sqrt{\beta_{n}}\mbox{\boldmath{$h$}}_{n}\in\mathbb{C}^{M\times 1}$ be
the channel between device $n$ and the BS, where $\beta_{n}$ is the large-
scale fading component due to path-loss and shadowing. In this paper,
$\mbox{\boldmath{$h$}}_{n}$ is modeled as correlated Rayleigh fading channel,
i.e.,

$\displaystyle\mbox{\boldmath{$h$}}_{n}=\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\ddot{\mbox{\boldmath{$h$}}}_{n},~{}n=1,2,\dots,N,$
(2)

where $\mbox{\boldmath{$C$}}_{n}$ denotes the channel covariance matrix of
$\mbox{\boldmath{$h$}}_{n}$ and diagonal elements of
$\mbox{\boldmath{$C$}}_{n}$ are all ones [22], and
$\ddot{\mbox{\boldmath{$h$}}}_{n}\sim\mathcal{CN}(0,\mbox{\boldmath{$I$}})$
follows the independent and identically distributed (i.i.d.) Rayleigh fading
channel model. In addition, we assume that the channels among different
devices are independent with each other, i.e.,
$\mathbb{E}\left(\sqrt{\beta_{n}}\mbox{\boldmath{$h$}}_{n}\sqrt{\beta_{n^{\prime}}}\mbox{\boldmath{$h$}}^{H}_{n^{\prime}}\right)=\mbox{\boldmath{$0$}}$,
for $n\neq n^{\prime}$[22, 32], where $\mathbb{E}(x)$ denotes the expectation
of a random variable $x$.

Each device is preassigned a unique and non-orthogonal preamble sequence
$\mbox{\boldmath{$s$}}_{n}\in\mathbb{C}^{L_{\rm I}\times 1}$ for active device
identity detection at the BS, $n=1,2,\dots,N$, where $L_{\rm I}\ll N$ is the
preamble sequence length for active device Identity detection. The sequences
$\mbox{\boldmath{$s$}}_{n}$’s are known as a priori at the BS. The received
baseband-equivalent signal $\mbox{\boldmath{$Y$}}\in\mathbb{C}^{L_{\rm
I}\times M}$ from time slot111Note that one time slot equals one symbol
duration in the preamble sequence. 1 to time slot $L_{\rm I}$ is expressed as

$Y$
$\displaystyle=\left[\mbox{\boldmath{$y$}}_{1},\mbox{\boldmath{$y$}}_{2},\dots,\mbox{\boldmath{$y$}}_{M}\right]$
$\displaystyle=\sum_{n=1}^{N}\alpha_{n}\mbox{\boldmath{$s$}}_{n}\sqrt{p_{n}}\sqrt{\beta_{n}}\mbox{\boldmath{$h$}}^{T}_{n}+\mbox{\boldmath{$Z$}}$
(3)
$\displaystyle=\sum_{n=1}^{N}\alpha_{n}\mbox{\boldmath{$s$}}_{n}\sqrt{\beta}\mbox{\boldmath{$h$}}^{T}_{n}+\mbox{\boldmath{$Z$}}$
(4)
$\displaystyle=\mbox{\boldmath{$S$}}\mbox{\boldmath{$\gamma$}}^{\frac{1}{2}}\mbox{\boldmath{$H$}}+\mbox{\boldmath{$Z$}},$
(5)

where $\mbox{\boldmath{$y$}}_{m}\in\mathbb{C}^{L_{\rm I}\times 1}$ is the
received signal from time slot 1 to time slot $L_{\rm I}$ at the $m$-th
antenna, $\forall m$; $p_{n}$ is the transmit power of device $n$;
$\mbox{\boldmath{$Z$}}=\left[\mbox{\boldmath{$z$}}_{1},\mbox{\boldmath{$z$}}_{2},\dots,\mbox{\boldmath{$z$}}_{M}\right]\in\mathbb{C}^{L_{\rm
I}\times M}$ is the additive white Gaussian noise with
$\mbox{\boldmath{$z$}}_{m}\sim\mathcal{CN}(0,\sigma^{2}\mbox{\boldmath{$I$}})$,
$\forall m$. Due to the power control on each device, in (4) we have

$\displaystyle\beta=p_{n}\beta_{n},~{}n=1,\dots,N;$ (6)

$\mbox{\boldmath{$S$}}=\left[\mbox{\boldmath{$s$}}_{1},\mbox{\boldmath{$s$}}_{2},\dots,\mbox{\boldmath{$s$}}_{N}\right]\in\mathbb{C}^{L_{\rm
I}\times N}$ is the preamble matrix consisting of the preambles from different
devices; $\mbox{\boldmath{$\gamma$}}={\rm
diag}\left\\{\alpha_{1}\beta,\alpha_{2}\beta,\dots,\alpha_{N}\beta\right\\}\in\mathbb{R}^{N\times
N}$; and
$\mbox{\boldmath{$H$}}=\left[\mbox{\boldmath{$h$}}_{1},\mbox{\boldmath{$h$}}_{2},\dots,\mbox{\boldmath{$h$}}_{N}\right]^{T}\in\mathbb{C}^{N\times
M}$ is the channel matrix. In this paper, the preamble matrix $S$ is designed
as follows. Denote $s_{\ell,n}$ the element in the $\ell$-th row and the
$n$-th column of $S$, $\Re{(s_{\ell,n})}$ the real part of $s_{\ell,n}$, and
$\Im{(s_{\ell,n})}$ the imaginary part of $s_{\ell,n}$. Then, both
$\Re{(s_{\ell,n})}$ and $\Im{(s_{\ell,n})}$ are uniformly chosen from
$\\{-\frac{\sqrt{2}}{2},\frac{\sqrt{2}}{2}\\}$, $\forall n,\ell$. The preamble
matrix $S$ is assumed to be known at the BS.

In the following, we rewrite the received signal $Y$ in (5) in order to show
the ADC quantizer design. In (5), denote
$\hat{\mbox{\boldmath{$y$}}}_{m}=\left[\Re{(\mbox{\boldmath{$y$}}^{T}_{m})},\Im{(\mbox{\boldmath{$y$}}^{T}_{m})}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}\times 1}$ and
$\bar{\mbox{\boldmath{$y$}}}=\left[\hat{\mbox{\boldmath{$y$}}}_{1}^{T},\hat{\mbox{\boldmath{$y$}}}_{2}^{T},\dots,\hat{\mbox{\boldmath{$y$}}}_{M}^{T}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}M\times 1}$. In addition, denote $\mbox{\boldmath{$h$}}^{\rm col}_{m}$ the
$m$-th column of $H$ in (5),
$\hat{\mbox{\boldmath{$h$}}}_{m}=\left[\Re{(\mbox{\boldmath{$h$}}^{\rm
col}_{m})^{T}},\Im{(\mbox{\boldmath{$h$}}^{\rm
col}_{m})^{T}}\right]^{T}\in\mathbb{R}^{2N\times 1}$, and
$\bar{\mbox{\boldmath{$h$}}}=\left[\hat{\mbox{\boldmath{$h$}}}_{1}^{T},\hat{\mbox{\boldmath{$h$}}}_{2}^{T},\dots,\hat{\mbox{\boldmath{$h$}}}_{M}^{T}\right]^{T}\in\mathbb{R}^{2NM\times
1}$. We have the following Theorem 1.

###### Theorem 1

The received signal $Y$ in (5) is equivalent to

$\displaystyle\bar{\mbox{\boldmath{$y$}}}=\bar{\mbox{\boldmath{$S$}}}\bar{\mbox{\boldmath{$\gamma$}}}^{\frac{1}{2}}\bar{\mbox{\boldmath{$h$}}}+\bar{\mbox{\boldmath{$z$}}},$
(7)

where $\bar{\mbox{\boldmath{$S$}}}={\rm
diag}\\{\underbrace{\hat{\mbox{\boldmath{$S$}}},\dots,\hat{\mbox{\boldmath{$S$}}}}_{M}\\}\in\mathbb{R}^{2L_{\rm
I}M\times 2NM}$, which consists of $M$ copies of $\hat{\mbox{\boldmath{$S$}}}$
in its main-diagonal blocks, and

$\displaystyle\hat{\mbox{\boldmath{$S$}}}=\begin{bmatrix}\Re{\left(\mbox{\boldmath{$S$}}\right)}&-\Im{\left(\mbox{\boldmath{$S$}}\right)}\\\
\Im{\left(\mbox{\boldmath{$S$}}\right)}&\Re{\left(\mbox{\boldmath{$S$}}\right)}\end{bmatrix}\in\mathbb{R}^{2L_{\rm
I}\times 2N};$ (8)

$\bar{\mbox{\boldmath{$\gamma$}}}={\rm
diag}\\{\underbrace{\hat{\mbox{\boldmath{$\gamma$}}},\dots,\hat{\mbox{\boldmath{$\gamma$}}}}_{M}\\}\in\mathbb{R}^{2NM\times
2NM}$ with $\hat{\mbox{\boldmath{$\gamma$}}}={\rm
diag}\left\\{\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$\gamma$}}\right\\}$;
and
$\bar{\mbox{\boldmath{$z$}}}=\left[\hat{\mbox{\boldmath{$z$}}}_{1}^{T},\hat{\mbox{\boldmath{$z$}}}_{2}^{T},\dots,\hat{\mbox{\boldmath{$z$}}}_{M}^{T}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}M\times 1}$ with
$\hat{\mbox{\boldmath{$z$}}}_{m}=\left[\Re{(\mbox{\boldmath{$z$}}^{T}_{m})},\Im{(\mbox{\boldmath{$z$}}^{T}_{m})}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}\times 1}$.

###### Proof:

Please refer to Appendix -A. ∎

The covariance matrix of $\bar{\mbox{\boldmath{$y$}}}$ in (7) is expressed as

$\displaystyle\mbox{\boldmath{$\Sigma$}}=\mathbb{E}(\mbox{\boldmath{$\bar{y}$}}\mbox{\boldmath{$\bar{y}$}}^{T})=\bar{\mbox{\boldmath{$S$}}}\bar{\mbox{\boldmath{$\gamma$}}}^{\frac{1}{2}}\mbox{\boldmath{$C$}}\bar{\mbox{\boldmath{$\gamma$}}}^{\frac{1}{2}}\bar{\mbox{\boldmath{$S$}}}^{T}+\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}}=\bar{\mbox{\boldmath{$S$}}}\mbox{\boldmath{$C$}}\bar{\mbox{\boldmath{$\gamma$}}}\bar{\mbox{\boldmath{$S$}}}^{T}+\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}},$
(9)

where
$\mbox{\boldmath{$C$}}=\mathbb{E}(\mbox{\boldmath{$\bar{h}$}}\mbox{\boldmath{$\bar{h}$}}^{T})$.
The derivation of $\Sigma$ in (9) and the way of constructing $C$ from
$\mbox{\boldmath{$C$}}_{n}$’s in (2) are shown in Appendix -B.

###### Theorem 2

Let $\lambda^{\ell,\ell}$ denote the power of $\bar{y}_{\ell}$,
$\ell=1,2,\dots,2L_{\rm I}M$, where $\bar{y}_{\ell}$ is the $\ell$-th element
of the received signal $\bar{\mbox{\boldmath{$y$}}}$ in (7). Then we have

$\displaystyle\lambda^{\ell,\ell}=\mathbb{E}\left(\bar{y}_{\ell}\bar{y}_{\ell}\right)=\frac{K}{2}\beta+\frac{1}{2}\sigma^{2},~{}~{}\forall\ell,$
(10)

where $\beta$ has been defined in (6).

###### Proof:

Please refer to Appendix -C. ∎

Theorem 2 shows that the signal power of each dimension of
$\bar{\mbox{\boldmath{$y$}}}$ is the same. In this case, in (10), denote

$\displaystyle\lambda=\lambda^{\ell,\ell},~{}\ell=1,2,\dots,2L_{\rm I}M.$ (11)

###  II-B ADC Quantizer Design

At the BS, the received signal $\bar{\mbox{\boldmath{$y$}}}$ in (7) is
quantized through ADCs for further baseband processing. Specifically, within
each ADC, denote $Q(\bar{y}_{\ell})$ a $B$-bit quantizer of $\bar{y}_{\ell}$,
$\ell=1,2,\dots,2L_{\rm I}M$, where $B$ specifies the resolution of the
quantizer. In this paper, we apply a uniform quantizer $Q(\bar{y}_{\ell})$ in
ADC like that in [29, 30, 31]. Note that the uniform ADC quantizers have been
widely applied within the receivers in current wireless systems. Denote the
quantization step size by $\Delta$. Then, the $q$-th quantization interval in
$Q(\bar{y}_{\ell})$ is

$\displaystyle\mathcal{I}_{q}=\left\\{\begin{array}[]{lll}\left(-\infty,(1-2^{(B-1)})\Delta\right),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\rm
if}~{}q=1,\\\ \left[(q-1-2^{(B-1)})\Delta,(q-2^{(B-1)})\Delta\right),~{}{\rm
if}~{}q=2,\dots,2^{B}-1,\\\
\left[(2^{(B-1)}-1)\Delta,+\infty\right),~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\rm
if}~{}q=2^{B}.\end{array}\right.$ (15)

In this case, if the input signal $\bar{y}_{\ell}\in\mathcal{I}_{q}$,
$\ell=1,2,\dots,2L_{\rm I}M$, then the output signal after quantization is

$\displaystyle
Q(\bar{y}_{\ell})=\left\\{\begin{array}[]{lll}(\frac{1}{2}-2^{(B-1)})\Delta,~{}~{}~{}~{}~{}~{}{\rm
if}~{}q=1,\\\ (q-2^{(B-1)}-\frac{1}{2})\Delta,~{}{\rm
if}~{}q=2,\dots,2^{B}-1,\\\
(2^{(B-1)}-\frac{1}{2})\Delta,~{}~{}~{}~{}~{}~{}{\rm
if}~{}q=2^{B}.\end{array}\right.$ (19)

With the above ADC quantizer, the received-quantized signal is expressed as

$\displaystyle\bar{\mbox{\boldmath{$y$}}}^{Q}=\left[\bar{y}_{1}^{Q},\bar{y}_{2}^{Q},\dots,\bar{y}_{2L_{\rm
I}M}^{Q}\right]^{T},$ (20)

where

$\displaystyle\bar{y}_{\ell}^{Q}=Q(\bar{y}_{\ell}),~{}~{}\ell=1,2,\dots,2L_{\rm
I}M.$ (21)

In the following, we show the design of the quantization step size $\Delta$ in
the ADC. From (7) and (10), $\bar{y}_{\ell}$ is Gaussian distributed with mean
zero and power (i.e., the variance) $\lambda$, $\forall\ell$. In this case,
most of the realizations of $\bar{y}_{\ell}$ are distributed around the mean
zero. For example, $99.7\%$ of the realizations of $\bar{y}_{\ell}$ fall in
the interval $[-3\sqrt{\lambda},3\sqrt{\lambda}]$. In this case, the
quantization step size should be set such that the received signal
$\bar{y}_{\ell}$ that falls in the interval
$[-3\sqrt{\lambda},3\sqrt{\lambda}]$ can be uniformly quantized. Thus, the
step size in the uniform ADC quantizer $Q(\bar{y}_{\ell})$ in (19) is
expressed as

$\displaystyle\Delta=\frac{\rho\sqrt{\lambda}}{2^{B-1}}=\frac{\rho\sqrt{2K\beta+2\sigma^{2}}}{2^{B}},$
(22)

where $\rho>0$ is a parameter that controls the size of the sample space along
$\bar{y}_{\ell}$, $\ell=1,2,\dots,2L_{\rm I}M$. From (22), given the
quantization bits $B$, a signal with large power $\lambda$ should be quantized
by a quantizer with large quantization step size $\Delta$, and vice versa. As
such, most realizations of the received signals can be well sampled by the
uniform ADC quantizer. Based on the quantization step size $\Delta$ in (22),
we can design the codebook according to (19).

As shown in (22), the quantization step size $\Delta$ depends on the number of
active devices $K$. In particular, a considerably overestimated or
underestimated of $K$ by the BS would result in huge ADC quantization error of
$\bar{\mbox{\boldmath{$y$}}}$, and hence deteriorates the performance of the
active device detector. In Section IV-B, we will numerically show that the
imperfect knowledge of $K$ can have a significant penalty on the performance
of the detector. Therefore, the accurate knowledge of $K$ is quite important
for the detector.. This is quite different from the current studies [4, 11, 5,
6, 7, 8, 9, 10, 15, 13, 12, 16, 17, 14, 18, 19] in mMTC in which they assume
ADC with infinite-resolution and detect the device activities directly without
the knowledge of $K$.

###  II-C Communication Protocol

Figure 1: The overall communication protocol.

To solve this problem, we propose an estimator to estimate $K$ before the
device activity detector. As shown in Fig. 1, the overall communication
protocol is divided into the two phases:

  1. 1.

Phase I: The BS spends $L_{\rm N}$ symbols to estimate the Number of active
devices. The estimated number of active devices is denoted by $\hat{K}$. Based
on $\hat{K}$, the BS designs the quantization codebook according to (22) and
(19) (by replacing $K$ by $\hat{K}$ therein).

  2. 2.

Phase II: The devices report their activity through $L_{\rm I}$ preambles.
Then, the BS detects the active devices based on the received signals
quantized by the designed ADC quantizer.

The total time slots used for detection and estimation are

$\displaystyle L=L_{\rm N}+L_{\rm I}.$ (23)

In Section III of this paper, we first show the design of the device activity
detector in Phase II of the communication protocol, assuming the BS has the
knowledge of $\hat{K}$ from Phase I. Through the numerical results in Section
IV, we show that the knowledge of $\hat{K}$ indeed has significant influence
on the performance of the activity detector. However, fortunately, the
numerical results also show that we actually do not need an accurate estimate
of $K$. Instead, a rough estimate of $K$ is good enough for the device
activity detector in Phase II. Then, building on this important observation,
we show the design of the estimator for $K$ in Phase I in Section V.

##  III Device Activity Detector in Phase II

In this section, we study the device activity detector in Phase II of the
communication protocol shown in Fig. 1, under the assumption that the BS has
the estimated knowledge $\hat{K}$ from Phase I. In this case, in Phase II, the
received signal $\bar{\mbox{\boldmath{$y$}}}$ to detect activity is now
quantized by the ADC quantizer according to (19) and (22) (by replacing $K$ by
$\hat{K}$ therein). We show how to estimate $\gamma$ in (5) based on the
received-quantized signal $\bar{\mbox{\boldmath{$y$}}}^{Q}$ in (21). Once
$\gamma$ is estimated, we can determine the active devices based on the
estimated $\gamma$.

###  III-A Problem Formulation

Denote
$p(\bar{\mbox{\boldmath{$y$}}}^{Q}|\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
the probability density function (PDF) of $\bar{\mbox{\boldmath{$y$}}}^{Q}$
given $\gamma$ and $S$. The detection problem is formulated as

$\displaystyle\min_{\mbox{\boldmath{$\gamma$}}}$
$\displaystyle-p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
(24) s.t. $\displaystyle\mbox{\boldmath{$\gamma$}}\geq 0.$

The PDF
$p(\mbox{\boldmath{$y$}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
in (24) is expressed as

$\displaystyle
p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})=\int_{\mathcal{I}_{f(\bar{y}_{1}^{Q})}}\int_{\mathcal{I}_{f(\bar{y}_{2}^{Q})}}\dots\int_{\mathcal{I}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}}p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})d\bar{y}_{1}d\bar{y}_{2}\dots
d\bar{y}_{2L_{\rm I}M},$ (25)

where $f(x)$ maps $x$ to the index of the quantization interval where it falls
in, i.e.,

$\displaystyle f(x)=\left\\{\begin{array}[]{lll}1,~{}~{}~{}~{}{\rm
if}~{}x\in\left(-\infty,(1-2^{(B-1)})\Delta\right),\\\ q,~{}~{}~{}~{}{\rm
if}~{}x\in\left[(q-1-2^{(B-1)})\Delta,(q-2^{(B-1)})\Delta\right),~{}q\in[2,2^{B}-1],\\\
2^{B},~{}~{}{\rm
if}~{}x\in\left[(2^{(B-1)}-1)\Delta,+\infty\right),\end{array}\right.$ (29)

and
$p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
denotes the PDF of $\bar{\mbox{\boldmath{$y$}}}$ given $\gamma$ and $S$, i.e.,

$\displaystyle
p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})=\frac{1}{(2\pi)^{ML}|\mbox{\boldmath{$\Sigma$}}|^{\frac{1}{2}}}\exp{\left(-\frac{1}{2}\bar{\mbox{\boldmath{$y$}}}^{T}\mbox{\boldmath{$\Sigma$}}^{-1}\bar{\mbox{\boldmath{$y$}}}\right)}.$
(30)

The expression of $\Sigma$ is shown in (9).

###  III-B Computational Challenge of Problem (24) and Motivation of SGD
Algorithm

In the rest of this section, we show how to solve the estimation problem in
(24). Specifically, if the ADC resolution is infinite, then the objective
function
$p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
in (24) reduces to

$\displaystyle
p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})=p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}}).$
(31)

In this case, the problem in (24) could be solved efficiently by the
traditional gradient descent algorithm[33, 16], where the gradient of
$p(\bar{\mbox{\boldmath{$y$}}}^{Q}|\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
with respect to $\gamma$ can be computed with ${\cal O}(NL_{\rm I}^{2})$
complexity. However, in this paper when the ADC resolution is finite, the
objective function
$p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
is an integral of
$p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
over the space

$\displaystyle\mathcal{I}\left(\bar{y}_{1}^{Q},\bar{y}_{2}^{Q},\dots,\bar{y}_{2L_{\rm
I}M}^{Q}\right)\overset{\Delta}{=}\mathcal{I}_{f(\bar{y}_{1}^{Q})}\times\mathcal{I}_{f(\bar{y}_{2}^{Q})}\times\dots\times\mathcal{I}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})},$ (32)

and its gradient is also an integral of the gradient of
$p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
over the space $\mathcal{I}\left(\bar{y}_{1}^{Q},\dots,\bar{y}_{2L_{\rm
I}M}^{Q}\right)$, i.e.,

$\displaystyle\nabla
p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})=\int_{\mathcal{I}_{f(\bar{y}_{1}^{Q})}}\int_{\mathcal{I}_{f(\bar{y}_{2}^{Q})}}\dots\int_{\mathcal{I}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}}\nabla
p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})d\bar{y}_{1}d\bar{y}_{2}\dots
d\bar{y}_{2L_{\rm I}M},$ (33)

where $\nabla p(\mbox{\boldmath{$x$}})$ denotes the gradient of
$p(\mbox{\boldmath{$x$}})$.

It is challenging to compute the gradient in (33) and apply the traditional
gradient descent algorithm to solve problem (24). More specifically, although
we can get a closed-form of $\nabla
p(\bar{\mbox{\boldmath{$y$}}}|\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
in (33), it is hard to get a closed-form of $\nabla
p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
due to the high-dimensional integration (especially in the massive MIMO system
where $M$ is usually large). As an alternative, one can numerically compute
the gradient in (33). However, the computational complexity is quite high,
which further prevents us from applying the traditional gradient descent
algorithm to solve the problem (24). Specifically, if we sample
$\bar{\mbox{\boldmath{$y$}}}$ uniformly, the gradient $\nabla
p(\bar{\mbox{\boldmath{$y$}}}^{Q}|\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
in (33) can be approximated as

$\displaystyle\nabla
p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})\approx\mu\sum_{i_{1}}\sum_{i_{2}}\dots\sum_{i_{2L_{\rm
I}M}}\nabla
p\left(\left[\bar{y}_{1}^{(i_{1})},\bar{y}_{2}^{(i_{2})},\dots,\bar{y}_{2L_{\rm
I}M}^{(i_{2L_{\rm
I}M})}\right]^{T}\Big{|}\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}}\right),$
(34)

where $\mu$ is a constant, and $\bar{y}_{\ell}^{(i_{\ell})}$ is the
$i_{\ell}$-th sample of $\bar{y}_{\ell}$ in the sample space
$\mathcal{I}_{f(\bar{y}_{{\ell}}^{Q})}$. Suppose the number of samples in each
dimension is $I$. Then from (34), we know that the computational complexity is
in the order of ${\cal O}(I^{2L_{\rm I}M})$, which would be prohibitively high
when $M$ and $L_{\rm I}$ are large.

To solve the aforementioned computational challenge, we propose to apply a
stochastic gradient descent (SGD) algorithm[28] to solve the problem (24).
Specifically, at each iteration, the SGD algorithm computes a stochastic
gradient of
$p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
by sampling only one point in each dimension of $\bar{\mbox{\boldmath{$y$}}}$,
instead of sampling many points in each dimension of
$\bar{\mbox{\boldmath{$y$}}}$ to approximately compute the true gradient like
that in (34). The per-iteration computational complexity is thus reduced
significantly. Moreover, [28] has proven the convergence of the SGD algorithm.

In the next two subsections, we tailor the SGD algorithm to solve our
interested problem (24), which essentially requires two basic steps. The first
step is to rewrite the problem (24) into a favorable expectation form required
by SGD. The second step is to compute the stochastic gradient, which is still
a nontrivial task.

###  III-C Rewriting (24) as a Form of Expected-Value Objective Function

The SGD algorithm is well suited for solving problems with an expected-value
objective function[28], e.g., in this paper the objective function should have
a form like

$\displaystyle\mathbb{E}_{\mbox{\boldmath{$x$}}}\left(g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)\right),$
(35)

where $g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)$ is a
function consisting of a random vector $x$ and a deterministic vector $\gamma$
that needs to be estimated in this paper. In this case, we should rewrite our
objective function in (24) as an expected-value objective function like that
in (35).

First, from (7) we know that each dimension of $\bar{\mbox{\boldmath{$y$}}}$
is Gaussian distributed with zero mean. In particular, for $\bar{y}_{\ell}$,
$\ell=1,\dots,2NL_{\rm I}$, although the range of its PDF extends to infinity
on both sides, $95\%$ of the realizations of $\bar{y}_{\ell}$ fall in the
interval $[-2\sqrt{\lambda},2\sqrt{\lambda}]$, and $99.7\%$ of the
realizations fall in the interval $[-3\sqrt{\lambda},3\sqrt{\lambda}]$, where
$\sqrt{\lambda}$ denotes the standard deviation of $\bar{y}_{\ell}$ that has
been defined in (11). In this case, the objective function
$p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
in (24) can be well approximated if the integration in (25) does not take
account the values of $\bar{\mbox{\boldmath{$y$}}}$ that are far from its mean
$0$, i.e.,

$\displaystyle
p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})$
$\displaystyle\approx\int_{\mathcal{J}_{f(\bar{y}_{1}^{Q})}}\int_{\mathcal{J}_{f(\bar{y}_{2}^{Q})}}\dots\int_{\mathcal{J}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}}p(\bar{\mbox{\boldmath{$y$}}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})d\bar{y}_{1}d\bar{y}_{2}\dots
d\bar{y}_{2L_{\rm I}M}$
$\displaystyle\overset{\Delta}{=}v\left(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}}\right),$
(36)

where

$\displaystyle\mathcal{J}_{q}=\left\\{\begin{array}[]{lll}\left(-2^{(B-1)}\Delta,(1-2^{(B-1)})\Delta\right),~{}{\rm
if}~{}q=1,\\\ \left[(2^{(B-1)}-1)\Delta,2^{(B-1)}\Delta\right),~{}~{}~{}{\rm
if}~{}q=2^{B},\\\
\mathcal{I}_{q},~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}{\rm
if}~{}q=2,\dots,2^{B}-1,\end{array}\right.$ (40)

and $f(x)$ has been defined in (29).

Second, in (36) the equality still holds when replacing the variable
$\bar{\mbox{\boldmath{$y$}}}$ by another variable
$\mbox{\boldmath{$x$}}=[x_{1},\dots,x_{2L_{\rm I}M}]^{T}$ inside the integral,
i.e.,

$\displaystyle
v\left(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}}\right)$
$\displaystyle=\int_{\mathcal{J}_{f(\bar{y}_{1}^{Q})}}\int_{\mathcal{J}_{f(\bar{y}_{2}^{Q})}}\dots\int_{\mathcal{J}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}}p(\mbox{\boldmath{$x$}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})dx_{1}dx_{2}\dots
dx_{2L_{\rm I}M}$
$\displaystyle=\int_{\mathcal{J}_{f(\bar{y}_{1}^{Q})}}\int_{\mathcal{J}_{f(\bar{y}_{2}^{Q})}}\dots\int_{\mathcal{J}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}}p(\mbox{\boldmath{$x$}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})\frac{1}{p(\mbox{\boldmath{$x$}})}p(\mbox{\boldmath{$x$}})dx_{1}dx_{2}\dots
dx_{2L_{\rm I}M},$ (41)

where $p(\mbox{\boldmath{$x$}})$ in (41) is defined as the PDF of $x$. Last,
in (41) denote

$\displaystyle
g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)=p(\mbox{\boldmath{$x$}}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}})\frac{1}{p(\mbox{\boldmath{$x$}})}.$
(42)

Then,
$v\left(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}}\right)$
in (41) is expressed as

$\displaystyle
v\left(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$S$}}\right)$
$\displaystyle=\int_{\mathcal{J}_{f(\bar{y}_{1}^{Q})}}\int_{\mathcal{J}_{f(\bar{y}_{2}^{Q})}}\dots\int_{\mathcal{J}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}}g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)p(\mbox{\boldmath{$x$}})dx_{1}dx_{2}\dots
dx_{2L_{\rm I}M}$
$\displaystyle=\mathbb{E}_{\mbox{\boldmath{$x$}}}\left(g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)\right).$
(43)

In particular, in this paper, to ease the algorithm execution and analysis, we
define the PDF of $x$ as

$\displaystyle
p(\mbox{\boldmath{$x$}})=\frac{1}{|\mathcal{J}_{f(\bar{y}_{1}^{Q})}||\mathcal{J}_{f(\bar{y}_{2}^{Q})}|\dots|\mathcal{J}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}|},$ (44)

i.e., $x$ is uniformly distributed in the space

$\displaystyle\mathcal{J}\left(\bar{y}_{1}^{Q},\dots,\bar{y}_{2L_{\rm
I}M}^{Q}\right)\overset{\Delta}{=}\mathcal{J}_{f(\bar{y}_{1}^{Q})}\times\mathcal{J}_{f(\bar{y}_{2}^{Q})}\times\dots\times\mathcal{J}_{f(\bar{y}_{2L_{\rm
I}M}^{Q})}.$ (45)

The optimization problem in (24) is then reformulated as

$\displaystyle\min_{\mbox{\boldmath{$\gamma$}}}$
$\displaystyle-\mathbb{E}_{\mbox{\boldmath{$x$}}}\left(g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)\right)$
(46) s.t. $\displaystyle\mbox{\boldmath{$\gamma$}}\geq 0,$

where
$\mbox{\boldmath{$x$}}\in\mathcal{J}\left(\bar{y}_{1}^{Q},\dots,\bar{y}_{2L_{\rm
I}M}^{Q}\right)$, and
$g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)$ is expressed
in $\eqref{eq:g}$.

###  III-D Tailored Stochastic Gradient Descent Algorithm

The SGD algorithm to solve problem (46) is carried out as follows. At the
$i$-th iteration, the algorithm uniformly generates a vector
$\mbox{\boldmath{$x$}}^{(i)}$ from the sample space
$\mathcal{J}\left(\bar{y}_{1}^{Q},\bar{y}_{2}^{Q},\dots,\bar{y}_{2L_{\rm
I}M}^{Q}\right)$ according to its PDF defined in (44). Then the variable
$\gamma$ is updated as follows:

$\displaystyle\mbox{\boldmath{$\gamma$}}^{(i)}=\mbox{\boldmath{$\gamma$}}^{(i-1)}-\theta_{i}\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right),$
(47)

where $\mbox{\boldmath{$\gamma$}}^{(i)}$ is the value of $\gamma$ at the
$i$-th iteration, $\theta_{i}$ is a step size parameter that controls the
convergence speed of the SGD algorithm, and $\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)$
is the stochastic gradient at the $i$-th iteration. The algorithm is
terminated when

$\displaystyle\frac{||\mbox{\boldmath{$\gamma$}}^{(i)}-\mbox{\boldmath{$\gamma$}}^{(i-1)}||_{1}}{N}<\epsilon$
(48)

where $\epsilon>0$ is a threshold that controls the termination of the
algorithm.

In this paper, it is nontrivial to compute the stochastic gradient $\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)$
in (47) in order to execute the SGD algorithm. Specifically, $\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)$
at the $i$-th iteration is expressed as

$\displaystyle\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)=\exp{\left(\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)\right)}\nabla\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right),$
(49)

where

$\displaystyle\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)$
$\displaystyle=\log{\left(g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)\right)}$
$\displaystyle=-\frac{1}{2}\left(\mbox{\boldmath{$x$}}^{(i)}\right)^{T}\mbox{\boldmath{$\Sigma$}}^{-1}\mbox{\boldmath{$x$}}^{(i)}-\frac{1}{2}\log{\left(|\mbox{\boldmath{$\Sigma$}}|\right)}-ML_{\rm
I}\log{\left(2\pi\right)}-\log{\left(p(\mbox{\boldmath{$x$}}^{(i)})\right)}.$
(50)

Note that $\Sigma$ in (9) is a function of
$\mbox{\boldmath{$\gamma$}}^{(i-1)}$. In (49), the computation of
$\nabla\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)$
is simple. However, the other term
$\exp{\left(\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)\right)}$
in (49) often takes either a value which is very close to zero or a pretty
large value due to the exponential operator. This problem further leads to the
vanishing and exploding gradient problem, which makes the SGD algorithm
fragile to be used to solve problem (34). To overcome the above instability
issue, we propose to normalize the overall gradient $\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)$
at each iteration, i.e., the $\mbox{\boldmath{$\gamma$}}^{(i)}$ updated in
(47) is revised as

$\displaystyle\mbox{\boldmath{$\gamma$}}^{(i)}=\mbox{\boldmath{$\gamma$}}^{(i-1)}-\theta_{i}\frac{\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)}{||\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)||_{2}}.$
(51)

In the following, we explain the intuition of the above normalization.
Specifically, in (49), denote the gradient direction by

$\displaystyle\mbox{\boldmath{$a$}}^{(i)}=\frac{\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)}{||\nabla
g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)||_{2}}=\frac{\nabla\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)}{||\nabla\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)||_{2}},$
(52)

and the gradient length by

$\displaystyle
b^{(i)}=\exp{\left(\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)\right)}||\nabla\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)||_{2}.$
(53)

The gradient direction $\mbox{\boldmath{$a$}}^{(i)}$ determines the direction
along which $\mbox{\boldmath{$\gamma$}}^{(i)}$ moves at the $i$-th iteration.
The term $b^{(i)}$ determines the step length with which
$\mbox{\boldmath{$\gamma$}}^{(i)}$ moves along the corresponding direction at
the $i$-th iteration. Note that, here we only study the step length arising
from the gradient itself, not the additional parameter $\theta_{i}$ in (47).
With the step length information $b^{(i)}$, the algorithm might converge
quickly. Without the step length information $b^{(i)}$, e.g., the step length
is set to be $b^{(i)}=1$, a good performance of the algorithm can still be
expected as long as the gradient direction information
$\mbox{\boldmath{$a$}}^{(i)}$ is provided, and a sufficient number of
iterations is performed. In our case, since the term
$\exp{\left(\bar{g}\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}^{(i-1)}\right)\right)}$
causes significant disturbance of the overall gradient, we only use the
gradient direction information $\mbox{\boldmath{$a$}}^{(i)}$ as that in (51).
Note that, compared with the original SGD update in (47), the above
normalization may lead to a bias term (i.e., $b^{(i)}$) on the update in (51).
We will show in Section IV-A that, this bias term does not affect the
convergence of the SGD algorithm. We name this algorithm as the Normalized SGD
(NSGD) algorithm. The detailed procedures of the NSGD algorithm is shown in
Algorithm 1.

Algorithm 1 Proposed NSGD Algorithm for Solving Problem (46)

1:Initialization: $i=0$,
$\mbox{\boldmath{$\gamma$}}^{(0)}=\mbox{\boldmath{$0$}}$, $\eta=1$,
$\epsilon>0$.

2:while $\eta>\epsilon$ do

3: $i\leftarrow i+1$;

4: Generate
$\mbox{\boldmath{$x$}}^{(i)}\in\mathcal{J}\left(\bar{y}_{1}^{Q},\dots,\bar{y}_{2L_{\rm
I}M}^{Q}\right)$ in a uniform manner;

5: Update $\mbox{\boldmath{$\gamma$}}^{(i)}$ according to (51);

6: Compute
$\eta=\frac{||\mbox{\boldmath{$\gamma$}}^{(i)}-\mbox{\boldmath{$\gamma$}}^{(i-1)}||_{1}}{N}$;

7:end while

8:Output $\mbox{\boldmath{$\gamma$}}^{(i)}$.

The above NSGD algorithm can be viewed as a process that solves a series of
optimization problems, each of which is inexactly solved by the traditional
gradient descent algorithm with only one gradient descent iteration. That is,
instead of solving a problem with objective function being
$\mathbb{E}_{\mbox{\boldmath{$x$}}}\left(g\left(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}}\right)\right)$
in (46), Algorithm 1 solves a series of problems with objective function being
$g(\mbox{\boldmath{$x$}},\mbox{\boldmath{$\gamma$}})$. Specifically, at the
$i$-th iteration the problem being solved is

$\displaystyle\min_{\mbox{\boldmath{$\gamma$}}}$
$\displaystyle-g\left(\mbox{\boldmath{$x$}}^{(i)},\mbox{\boldmath{$\gamma$}}\right)$
(54) s.t. $\displaystyle\mbox{\boldmath{$\gamma$}}\geq 0.$

Performing a normalized gradient descent step on the above problem at the
current point $\mbox{\boldmath{$\gamma$}}^{(i-1)}$ yields the update in (51).

##  IV Numerical Results of Device Activity Detector

In this section, we present the device activity detection performance of the
proposed NSGD algorithm in terms of missed detection probability (MDP) and
false alarm probability (FAP). The MDP is the probability that an active
device is detected to be inactive; the FAP is the probability that an inactive
device is detected to be active. The noise power spectrum density is -169
dBm/Hz, the bandwidth is 10 MHz, the transmit power of each device is set to
be 23 dBm, and the large-scale fading component is modeled as
$128.1+37.6\log_{10}(d)$, where $d$ is the distance between the BS and devices
in km[34]. In the simulations, we set $d=1$ km. In addition, all the channel
covariance matrices in (2) follow the exponential covariance matrix model[35],
i.e., for a covariance matrix $C$, the element at the $i$-th row and $j$-th
column of $C$ is expressed as $[\mbox{\boldmath{$C$}}]_{i,j}=c^{i-j}$ if
$i\geq j$, and
$[\mbox{\boldmath{$C$}}]_{i,j}=[\mbox{\boldmath{$C$}}]_{j,i}^{*}$ if $i<j$,
with $|c|\leq 1$. Moreover, we set $\rho=2$ in (22). Furthermore, we set
$\theta_{i}=i^{-\frac{1}{2}}$ in (51). To evaluate efficiency of the proposed
Algorithm 1, denote $\hat{I}$ the average number of iterations to meet the
termination criterion. Last, we have one benchmark to evaluate the detection
performance of the proposed NSGD algorithm as follows:

Figure 2: Convergence behavior of proposed Algorithm 1 when $N=1000$, $K=100$,
$L_{\rm I}=40$, $M=128$, and $\epsilon=10^{-3}$.

  * •

$B=\infty$. We consider an ADC with infinite-resolution, i.e., the
quantization bits $B=\infty$. In this case, the device activity detection
problem can be solved by applying the traditional gradient descent
algorithm[33, 16].

###  IV-A Performance of NSGD with Perfect Knowledge of $K$

We first present the performance of NSGD when $\hat{K}=K$. Fig. 2 plots the
convergence behavior of the proposed Algorithm 1 when $N=1000$, $K=100$,
$L_{\rm I}=40$, and $M=128$. In the y-axis in Fig. 2, denote

$\displaystyle\delta=\frac{||\mbox{\boldmath{$\gamma$}}^{(i)}-\mbox{\boldmath{$\gamma$}}^{*}||_{1}}{N}$
(55)

where $\mbox{\boldmath{$\gamma$}}^{*}$ denotes the optimized value of $\gamma$
through Algorithm 1. We have the following observations from Fig. 2. First, if
we set $\epsilon=10^{-3}$ in (48), the NSGD indeed converges under different
$B$. Second, for the same convergence control parameter $\epsilon$, a larger
$B$ can reduce the total number of iterations for the algorithm to meet the
termination criterion. For example, the NSGD with $B=3$ converges more quickly
than the NSGD with $B=2$. Third, when $B$ is large enough, for the same
convergence control parameter $\epsilon$, increasing $B$ can not reduce the
number of iterations significantly. For example, the number of iterations
required for satisfying the termination criterion are the nearly same when
$B=3$ and $B=4$.

(a) Detection performance of NSGD when $N=100$, $K=10$, $L_{\rm I}=13$, and
$M=32$.

(b) Detection performance of NSGD when $N=1000$, $K=100$, $L_{\rm I}=40$, and
$M=128$.

Figure 3: Detection performance of NSGD algorithm under different setups.

Next, we present the detection performance of the NSGD algorithm benchmarked
against the case with $B=\infty$. First, as shown in Fig. 3, the performance
of NSGD with $B=4$ can approach to the case with infinite ADC resolution. This
phenomenon shows that, although the BS is equipped with low-resolution ADCs,
in terms of active device detection, we can achieve the performance of the
detector with infinite-resolution ADC. Second, the performance of NSGD
algorithm increases with the ADC resolution $B$. Third, improving the solution
accuracy (by setting a smaller tolerance $\epsilon$) will require a larger
number of iterations. But on the upside it can also possibly improve the
detection performance of the proposed NSGD algorithm. Specifically, as shown
in Fig. 3(a), when $\epsilon=10^{-3}$, the performance of NSGD with $B=4$ is
roughly the same as that with $B=3$. But if we set $\epsilon=10^{-4}$ or
equivalently increase $\hat{I}$ of NSGD from 30.27 to 209.04, we can see that
the performance of NSGD with $B=4$ increases significantly, and even
approaches to the performance of the case with infinite ADC resolution. We
have similar observations and conclusions on Fig. 3(b).

###  IV-B Performance of NSGD with Imperfect Knowledge of $K$

(a) Detection performance of NSGD versus different $\hat{K}$ when $B=4$,
$\epsilon=10^{-4}$, $N=1000$, $K=100$, $L_{\rm I}=40$, and $M=128$.

(b) Detection performance of NSGD versus different $\hat{K}$ when $B=4$,
$\epsilon=10^{-4}$, $N=1000$, $K=10$, $L_{\rm I}=15$, and $M=64$.

Figure 4: Detection performance of NSGD algorithm versus $\hat{K}$ under
different setups.

Next, we present the performance of NSGD when only an estimate of $K$, i.e.,
$\hat{K}$, is known at the BS. The imperfect knowledge of $K$ will affect the
estimation of the signal power in (10), and in turn affect the quantization
step size design (22) as well as the quantization codebook design in (19). The
numerical results that evaluate the influence of $\hat{K}$ on the NSGD
performance are shown in Fig. 4 when $B=4$. First, Fig. 4 shows that when
$\hat{K}\neq K$, there are detection performance penalties under different
$\hat{K}$. For example, there are big performance penalties when $\hat{K}=1$
in Fig. 4(a), and when $\hat{K}=N$ in Fig. 4(b). Note that, when assuming
$\hat{K}=N$, the detector performs much better in Fig. 4(a) than that in Fig.
4(b). This is because the designed codebook is the same in Fig. 4(a) and Fig.
4(b) for the same $\hat{K}$ according to (10) and (22). Since the gap between
$K=100$ and $\hat{K}=N$ is smaller than that between $K=10$ and $\hat{K}=N$,
the designed codebook matches the received signals when $K=100$ in Fig. 4(a)
better than that when $K=10$ in Fig. 4(b). This phenomenon clearly suggests
that, the knowledge of $K$ is important for the ADC quantizer design.
Otherwise, the mismatch between the ADC quantizer to the received signals will
induce big performance penalties. Second, fortunately, the performance of NSGD
is still satisfactory when the estimation error of $K$ is not very large. For
example, when $\hat{K}=\frac{K}{2}$, there is only a small penalty on the
performance of the NSGD in Fig. 4.

In summary, in the case where the knowledge of $K$ and its statistics are
unknown at the BS, it is necessary to have an estimation of $K$ at the BS.
Fortunately, the estimation does not need to be very accurate, and a fairly
good estimation of $K$ is sufficient to achieve satisfactory detection
performance.

##  V Number of Active device Estimator in Phase I

In this section, we propose an estimator to estimate the number of active
devices $K$ in Phase I of the communication protocol. The received signals to
estimate $K$ still need to go through the ADC quantizer, while the design of
which still need the information of $K$. Thus, the technical difficulty here
is that the design of the ADC quantizer and the estimation of $K$ are closely
intertwined and doing one needs the information/execution from the other. This
seems like a chicken-and-egg problem. This section aims to propose an
efficient algorithm to solve this dilemma.

###  V-A Problem Formulation

In this section, we study the estimator for $K$ under i.i.d. Rayleigh fading
channels. The i.i.d. Rayleigh fading model is widely assumed in the current
literature, e.g., [5, 11, 12, 13, 14, 15, 16, 17, 18, 19]. Specifically,
following the correlated Rayleigh fading channel model assumed in (2), for the
i.i.d. Rayleigh fading channel we have
$\mbox{\boldmath{$C$}}_{n}=\mbox{\boldmath{$I$}}$ and

$\displaystyle\mbox{\boldmath{$h$}}_{n}=\ddot{\mbox{\boldmath{$h$}}}_{n},~{}n=1,2,\dots,N.$
(56)

In Section V-E, we will show that our estimator designed for i.i.d. Rayleigh
fading channel also works well under correlated Rayleigh fading channel.

Since in Phase I we only need to estimate $K$ instead of their identities, the
devices can use and send identical preambles, i.e.,
$\mbox{\boldmath{$s$}}_{1}=\dots=\mbox{\boldmath{$s$}}_{N}=\mbox{\boldmath{$s$}}\in\mathbb{C}^{L_{\rm
N}\times 1}$. The received signal in (5) is re-expressed as

$\displaystyle\mbox{\boldmath{$Y$}}=\sum_{n=1}^{N}\alpha_{n}\mbox{\boldmath{$s$}}_{n}\sqrt{\beta}\mbox{\boldmath{$h$}}^{T}_{n}+\mbox{\boldmath{$Z$}}=\mbox{\boldmath{$s$}}\sqrt{\beta}\sum_{n=1}^{N}\alpha_{n}\mbox{\boldmath{$h$}}^{T}_{n}+\mbox{\boldmath{$Z$}}.$
(57)

Note that we abuse the notations of the received signals $Y$, the preambles
$\mbox{\boldmath{$s$}}_{n}$’s, and the other relevant notations in Phase I and
Phase II without inducing confusions. In (57), since the channels follow
i.i.d. Rayleigh distribution, we have

$\displaystyle\sum_{n=1}^{N}\alpha_{n}\mbox{\boldmath{$h$}}^{T}_{n}\overset{d}{=}\sqrt{K}\mbox{\boldmath{$h$}}^{T}_{1}\sim\mathcal{CN}(0,K\mbox{\boldmath{$I$}}).$
(58)

where $\overset{d}{=}$ denotes equal in the distribution. In this case, we
have

$\displaystyle\mbox{\boldmath{$Y$}}\overset{d}{=}\sqrt{K\beta}\mbox{\boldmath{$s$}}\mbox{\boldmath{$h$}}^{T}_{1}+\mbox{\boldmath{$Z$}}.$
(59)

That is, the received signal $Y$ is a function of $K$ in terms of its
distribution. The received signal $Y$ can be rewritten as a vector form
$\bar{\mbox{\boldmath{$y$}}}$ like that in (7) by setting
$\mbox{\boldmath{$s$}}_{1}=\dots=\mbox{\boldmath{$s$}}_{N}=\mbox{\boldmath{$s$}}$
therein, then goes through ADC quantizers. The quantized signal is
$\bar{\mbox{\boldmath{$y$}}}^{Q}$. The estimation problem is thus formulated
as

$\displaystyle\min_{K}$ $\displaystyle-p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid
K,\mbox{\boldmath{$s$}})$ (60) s.t. $\displaystyle N\geq K\geq 0.$

The objective function is expressed as

$\displaystyle p(\bar{\mbox{\boldmath{$y$}}}^{Q}\mid
K,\mbox{\boldmath{$s$}})=\int_{\mathcal{I}_{f(\bar{y}_{1}^{Q})}}\int_{\mathcal{I}_{f(\bar{y}_{2}^{Q})}}\dots\int_{\mathcal{I}_{f(\bar{y}_{2L_{\rm
N}M}^{Q})}}\prod_{m=1}^{M}p(\hat{\mbox{\boldmath{$y$}}}_{m}\mid
K,\mbox{\boldmath{$s$}})d\bar{y}_{1}d\bar{y}_{2}\dots d\bar{y}_{2L_{\rm N}M},$
(61)

where

$\displaystyle p(\hat{\mbox{\boldmath{$y$}}}_{m}\mid
K,\mbox{\boldmath{$s$}})=\frac{1}{(2\pi)^{L_{\rm
N}}|\mbox{\boldmath{$\Sigma_{m}$}}|^{\frac{1}{2}}}\exp{\left(-\frac{1}{2}\hat{\mbox{\boldmath{$y$}}}_{m}^{T}\mbox{\boldmath{$\Sigma$}}_{m}^{-1}\hat{\mbox{\boldmath{$y$}}}_{m}\right)},$
(62)

and $\hat{\mbox{\boldmath{$y$}}}_{m}$ has been similarly defined above (7).
The covariance matrix of $\hat{\mbox{\boldmath{$y$}}}_{m}$ is expressed as

$\displaystyle\mbox{\boldmath{$\Sigma$}}_{m}=\mathbb{E}(\mbox{\boldmath{$\hat{y}$}}_{m}\mbox{\boldmath{$\hat{y}$}}_{m}^{T})=\frac{1}{2}K\hat{\mbox{\boldmath{$s$}}}_{1}\hat{\mbox{\boldmath{$s$}}}_{1}^{T}+\frac{1}{2}K\hat{\mbox{\boldmath{$s$}}}_{1+N}\hat{\mbox{\boldmath{$s$}}}_{1+N}^{T}+\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}},$
(63)

where $\hat{\mbox{\boldmath{$s$}}}_{n}$ is the $n$-th column of
$\hat{\mbox{\boldmath{$S$}}}$ in (8) when
$\mbox{\boldmath{$s$}}_{1}=\dots=\mbox{\boldmath{$s$}}_{N}$. The estimation
problem in (60) can be solved by applying the NSGD algorithm detailed in
Section III. We omit the details here.

###  V-B One-Shot Estimator for Number of Active Devices

Similar to the detector for device activities studied in Section III, the BS
in this section still needs to do ADC quantization once receiving signals from
active devices. Then, the BS estimates the number of active devices by solving
the estimation problem in (60). Note that, in order to do the ADC quantization
at the BS in Phase I, the BS still needs to have the knowledge of $K$
beforehand.

Figure 5: Performance of OEA over different $\hat{K}_{\rm I}$ when $B=4$,
$N=1000$, $K=100$, and $M=128$.

Denote $\hat{K}^{(0)}$ the initial guess that is used to design the ADC
quantizer in Phase I. A naive way is that, we arbitrarily set a value of
$\hat{K}^{(0)}$ from 1 to $N$, e.g., $\hat{K}^{(0)}=N$, to start the estimator
in Phase I. Then, BS quantizes signals accordingly and estimates $K$ by
solving problem (60). The estimated $K$ is denoted by $\hat{K}$. We name this
estimator as One-shot Estimator for the number of Active devices (OEA). The
estimated $K$ through the estimator is delivered to Phase II for detection of
the active device identities.

Fig. 5 shows the performance of OEA when $B=4$, $N=1000$, $K=100$, and
$M=128$. The channel setups are the same as that in Section IV. Denote $E_{K}$
mean of the estimation error of $K$, and express it as

$\displaystyle E_{K}=\mathbb{E}\\{|K-\hat{K}|\\}.$ (64)

First, the performance of OEA is sensitive to the initial value
$\hat{K}^{(0)}$. Specifically, OEA performs well when $\hat{K}^{(0)}=N$, while
it performs poorly when $\hat{K}^{(0)}=1$. The reason for the poor performance
of OEA when $\hat{K}^{(0)}=1$ is that, the estimated sample space in this case
is much smaller than the real one in the ADC quantizer. As such, the
quantization error would be quite large. Second, the estimation error
decreases slowly with $L_{\rm N}$. This shows that, in order to reduce the
estimation error, increasing $L_{\rm N}$ is not a good idea. Much worse, if
too much time is spent on the estimation of $K$, the time for the identity
detection would be quite limited.

###  V-C Progressive Estimator for Number of Active Devices

We observe from Fig. 5 that when $\hat{K}^{(0)}=1$, the estimation error of
OEA is

$\displaystyle E_{K}=\mathbb{E}\\{|100-\hat{K}|\\}\approx 90.$ (65)

If we treat the initial guess $\hat{K}^{(0)}=1$ as the estimated value as
well, then the estimation error would be

$\displaystyle E_{K}=\mathbb{E}\\{|100-\hat{K}^{(0)}|\\}=99,$ (66)

which is larger than the estimation error of OEA in (65). That is, although
the estimation error of OEA is pretty large, OEA can help reduce the
estimation error arising from the initial value as in (66). This is also true
if the initial value is chosen to be $10$.

Building upon this observation, we propose a Progressive Estimator for the
number of Active devices (PEA). PEA turns the one-shot estimation in OEA into
a series of progressive estimations. Specifically, at the $i$-th estimation,
each device only uses one symbol $s_{i}\in\mathbb{C}$ to estimate $K$, where
$s_{i}$ denotes the $i$-th element in $s$. In this case, for PEA, the number
of estimations equals the number of preamble length $L_{\rm N}$. Denote the
estimated $K$ at the $i$-th estimation by $\hat{K}^{(i)}$, $i=1,\dots,L_{\rm
N}$. Then, the procedures of the PEA are summarized in Algorithm 2.

Algorithm 2 Proposed PEA Algorithm

1:Initialization: $L_{\rm N}$, $\hat{K}^{(0)}$.

2:for $i=1,\dots,L_{\rm N}$ do

3: According to $\hat{K}^{(i-1)}$, the BS designs the ADC quantizer based on
(19);

4: Each device transmits symbol $s_{i}$ to estimate $K$;

5: The BS quantizes the received signals $\bar{\mbox{\boldmath{$y$}}}$
according to the designed ADC quantizer;

6: The BS estimates $K$ by solving the problem (60), the output of which is
$\hat{K}^{(i)}$.

7:end for

8:Output $\hat{K}=\hat{K}^{(L_{\rm N})}$ that is delivered to Phase II for the
detection of device activities.

(a) Estimated $K$ over different initial values $\hat{K}^{(0)}$.

(b) Estimation error of $K$ over different initial values $\hat{K}^{(0)}$.

Figure 6: Estimation performance of PEA when $B=4$, $N=1000$, $K=100$, and
$M=128$.

###  V-D Performance of PEA under I.I.D. Rayleigh Fading Channel

In this section, we present the numerical results of the proposed estimator
PEA for the number of active devices, and the overall performance of the
communication protocol in Fig. 1 when $B=4$, $N=1000$, $K=100$, and $M=128$.
The channel setups are the same as that in Section IV.

Fig. 6(a) shows the estimated $K$ over different initial values
$\hat{K}^{(0)}$. First, when $\hat{K}^{(0)}=1$ and $L_{\rm N}\leq 6$, the
output value of PEA is always closer to the real $K$ than the input value,
i.e.,

$\displaystyle\mathbb{E}\\{|K-\hat{K}^{(i)}|\\}<\mathbb{E}\\{|K-\hat{K}^{(i-1)}|\\},~{}i=1,\dots,L_{\rm
N}.$ (67)

Also, as shown in Fig. 6(b), the estimation error of $K$ decreases as $L_{\rm
N}$ increases when $\hat{K}^{(0)}=1$. Benchmarked against OEA (which is
sensitive to the initial value) when the initial value is set to be 1, PEA has
significant performance improvement. Second, as shown in Fig. 6(a), for
different $\hat{K}^{(0)}$, the estimated $K$ can converge to $\hat{K}^{(L_{\rm
N})}=85$ as the increase of $L_{\rm N}$. This phenomenon suggests that our PEA
is quite robust to the choice of initial value $\hat{K}^{(0)}$. The finally
converged value $\hat{K}^{(L_{\rm N})}=85$ may be mainly determined by the
number of antennas $M$ and the quantization bits $B$. We leave it as a future
work to analyze the convergence and the influence factors on the converged
value.

Figure 7: Detection performance of the communication protocol in Fig. 1.

In Fig. 7, we show the performance of the proposed communication protocol in
Fig. 1 that consists of an estimator for the number of active devices and a
detector for device identity. To evaluate its performance, we have the
following to benchmarks:

  1. 1.

Benchmark 1: It only consists of a detector for device identity, and has
perfect knowledge of $K$, i.e., $\hat{K}=K$.

  2. 2.

Benchmark 2: It only consists of a detector for device identity, and simply
assumes $\hat{K}=1$.

As shown in Fig. 7, our proposed communication protocol performs quite well.
First, for the same overall preamble length $L$, compared with Benchmark 2,
our protocol has significant improvement on the detection performance since we
allocate some preambles to estimate $K$ while Benchmark 2 simply assumes
$\hat{K}=1$. That is, although we use less number of preambles to detect user
identities in Phase II, we can still achieve the overall performance
improvement compared with Benchmark 2, since the estimation of $K$ is good
enough. Second, compared with Benchmark 1 which has perfect knowledge of $K$,
by using additional 5 preambles to estimate $K$, our protocol performs nearly
the same as Benchmark 1. This clearly shows that the proposed PEA performs
well and the estimated $K$ is good enough for the detector in Phase II.

###  V-E Performance of PEA under Correlated Rayleigh Fading Channel

Figure 8: Estimation performance of PEA when $B=4$, $N=1000$, $K=100$, and
$M=128$ under correlated Rayleigh fading channel.

In Fig. 8, under correlated Rayleigh fading channels, we show the performance
of PEA that has been designed for i.i.d. Rayleigh fading channels in Section
V-B. The channel setups and the channel covariance model are the same as that
in Section IV. Fig. 8 shows that the performance of PEA under correlated
Rayleigh fading channels is roughly the same as that under i.i.d. Rayleigh
fading channels, which thus shows that our designed estimator for the number
of active devices is quite robust to the channel distributions. The possible
reason is that the proposed estimator PEA does not have high estimation
accuracy. In this case, the prior information of the channel distribution is
not important for the estimator.

##  VI Conclusion

We investigated a device activity detection problem in mMTC, where the BS is
equipped with a massive MIMO and low-resolution ADCs. This setup causes
additional challenges in the activity detection problem. First, the BS should
have the knowledge of the number of active devices $K$ in order to do better
ADC quantization. Second, it is not clear if the covariance-based approach can
still achieve good performance. To solve the above problems, we proposed a
communication protocol that consists of an estimator for $K$ and a detector
for active device identities. For the estimator for $K$, we proposed a
progressive estimator PEA which iteratively performs the estimation of $K$ and
the design of the quantizer. For the detector for active device identities, we
proposed a custom-designed NSGD algorithm to solve the problem whose objective
involves high-dimensional integration. Numerical results demonstrated the
effectiveness of the proposed communication protocol.

###  -A Proof of Theorem 1

First, from (5), the received signal $\mbox{\boldmath{$y$}}_{m}$ at the $m$-th
antenna is

$\displaystyle\mbox{\boldmath{$y$}}_{m}=\mbox{\boldmath{$S$}}\mbox{\boldmath{$\gamma$}}^{\frac{1}{2}}\mbox{\boldmath{$h$}}^{\rm
col}_{m}+\mbox{\boldmath{$z$}}_{m},~{}m=1,2,\dots,M,$ (68)

where $\mbox{\boldmath{$h$}}^{\rm col}_{m}$ denotes the $m$-th column of $H$
in (5). Second, to express (68) into a real form, denote
$\hat{\mbox{\boldmath{$y$}}}_{m}=\left[\Re{(\mbox{\boldmath{$y$}}^{T}_{m})},\Im{(\mbox{\boldmath{$y$}}^{T}_{m})}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}\times 1}$,
$\hat{\mbox{\boldmath{$S$}}}=\begin{bmatrix}\Re{\left(\mbox{\boldmath{$S$}}\right)}&-\Im{\left(\mbox{\boldmath{$S$}}\right)}\\\
\Im{\left(\mbox{\boldmath{$S$}}\right)}&\Re{\left(\mbox{\boldmath{$S$}}\right)}\end{bmatrix}\in\mathbb{R}^{2L_{\rm
I}\times 2N}$, $\hat{\mbox{\boldmath{$\gamma$}}}={\rm
diag}\left\\{\mbox{\boldmath{$\gamma$}},\mbox{\boldmath{$\gamma$}}\right\\}$,
$\hat{\mbox{\boldmath{$h$}}}_{m}=\left[\Re{(\mbox{\boldmath{$h$}}^{\rm
col}_{m})^{T}},\Im{(\mbox{\boldmath{$h$}}^{\rm
col}_{m})^{T}}\right]^{T}\in\mathbb{R}^{2N\times 1}$, and
$\hat{\mbox{\boldmath{$z$}}}_{m}=\left[\Re{(\mbox{\boldmath{$z$}}^{T}_{m})},\Im{(\mbox{\boldmath{$z$}}^{T}_{m})}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}\times 1}$. In this case, (68) can be rewritten as

$\displaystyle\hat{\mbox{\boldmath{$y$}}}_{m}=\hat{\mbox{\boldmath{$S$}}}\hat{\mbox{\boldmath{$\gamma$}}}^{\frac{1}{2}}\hat{\mbox{\boldmath{$h$}}}_{m}+\hat{\mbox{\boldmath{$z$}}}_{m},~{}m=1,2,\dots,M,$
(69)

where
$\hat{\mbox{\boldmath{$z$}}}_{m}\sim\mathcal{N}(0,\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}})$,
$\forall m$. Last, denote
$\bar{\mbox{\boldmath{$y$}}}=\left[\hat{\mbox{\boldmath{$y$}}}_{1}^{T},\dots,\hat{\mbox{\boldmath{$y$}}}_{M}^{T}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}M\times 1}$, $\bar{\mbox{\boldmath{$S$}}}={\rm
diag}\\{\underbrace{\hat{\mbox{\boldmath{$S$}}},\dots,\hat{\mbox{\boldmath{$S$}}}}_{M}\\}\in\mathbb{R}^{2L_{\rm
I}M\times 2NM}$ which consists of $M$ copies of $\hat{\mbox{\boldmath{$S$}}}$
in its main-diagonal blocks, $\bar{\mbox{\boldmath{$\gamma$}}}={\rm
diag}\\{\underbrace{\hat{\mbox{\boldmath{$\gamma$}}},\dots,\hat{\mbox{\boldmath{$\gamma$}}}}_{M}\\}\in\mathbb{R}^{2NM\times
2NM}$,
$\bar{\mbox{\boldmath{$h$}}}=\left[\hat{\mbox{\boldmath{$h$}}}_{1}^{T},\dots,\hat{\mbox{\boldmath{$h$}}}_{M}^{T}\right]^{T}\in\mathbb{R}^{2NM\times
1}$, and
$\bar{\mbox{\boldmath{$z$}}}=\left[\hat{\mbox{\boldmath{$z$}}}_{1}^{T},\dots,\hat{\mbox{\boldmath{$z$}}}_{M}^{T}\right]^{T}\in\mathbb{R}^{2L_{\rm
I}M\times 1}$. Then, the received signal $Y$ in (5) is rewritten as

$\displaystyle\bar{\mbox{\boldmath{$y$}}}=\bar{\mbox{\boldmath{$S$}}}\bar{\mbox{\boldmath{$\gamma$}}}^{\frac{1}{2}}\bar{\mbox{\boldmath{$h$}}}+\bar{\mbox{\boldmath{$z$}}}.$
(70)

###  -B Derivations of $\Sigma$ and $C$ in (9)

We first derive the $\Sigma$ in (9). Since the first equality in (9) is
straightforward, we mainly focus on the proof of the second equality. To this
end, we first take a close look at the covariance matrix
$\mbox{\boldmath{$C$}}=\mathbb{E}(\mbox{\boldmath{$\bar{h}$}}\mbox{\boldmath{$\bar{h}$}}^{T})$
in (9). Specifically, from Section II-B, we know

$\displaystyle\bar{\mbox{\boldmath{$h$}}}=\left[\hat{\mbox{\boldmath{$h$}}}_{1}^{T},\dots,\hat{\mbox{\boldmath{$h$}}}_{M}^{T}\right]^{T}=\left[\Re{(\mbox{\boldmath{$h$}}^{\rm
col}_{1})^{T}},\Im{(\mbox{\boldmath{$h$}}^{\rm
col}_{1})^{T}},\dots,\Re{(\mbox{\boldmath{$h$}}^{\rm
col}_{M})^{T}},\Im{(\mbox{\boldmath{$h$}}^{\rm col}_{M})^{T}}\right]^{T},$
(71)

where $\mbox{\boldmath{$h$}}^{\rm col}_{m}$ denotes the $m$-th column of $H$
in (5). It follows from (71) that

$\displaystyle\bar{\mbox{\boldmath{$h$}}}_{2m-1}=\Re{(\mbox{\boldmath{$h$}}^{\rm
col}_{m})},~{}\bar{\mbox{\boldmath{$h$}}}_{2m}=\Im{(\mbox{\boldmath{$h$}}^{\rm
col}_{m})},~{}m=1,\dots,M.$ (72)

The covariance matrix of $\bar{\mbox{\boldmath{$h$}}}$ is further expressed as

$\displaystyle\mbox{\boldmath{$C$}}=\mathbb{E}(\mbox{\boldmath{$\bar{h}$}}\mbox{\boldmath{$\bar{h}$}}^{T})=\begin{bmatrix}\mbox{\boldmath{$C$}}_{1,1}&\mbox{\boldmath{$C$}}_{1,2}&\cdots&\mbox{\boldmath{$C$}}_{1,2M}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mbox{\boldmath{$C$}}_{2M,1}&\mbox{\boldmath{$C$}}_{2M,2}&\cdots&\mbox{\boldmath{$C$}}_{2M,2M}\end{bmatrix},$
(73)

where

$\displaystyle\mbox{\boldmath{$C$}}_{m,\bar{m}}$
$\displaystyle=\mathbb{E}(\bar{\mbox{\boldmath{$h$}}}_{m}\bar{\mbox{\boldmath{$h$}}}_{\bar{m}}^{T})$
(74)
$\displaystyle=\mathbb{E}\left(\left[\bar{h}_{1,m},\dots,\bar{h}_{N,m}\right]^{T}\left[\bar{h}_{1,\bar{m}},\dots,\bar{h}_{N,\bar{m}}\right]\right),~{}m,\bar{m}=1,\dots,2M,$
(75)

where $\bar{h}_{n,m}$ denotes the $n$-th element in
$\bar{\mbox{\boldmath{$h$}}}_{m}$. Now let us take a close look at
$\mbox{\boldmath{$C$}}_{m,\bar{m}}$. Recall that $\bar{h}_{n,m}$ is the
channel of device $n$, and $\bar{h}_{\bar{n},\bar{m}}$ is the channel of
device $\bar{n}$. Since the channels among different devices are independent,
we have $\mathbb{E}\left(\bar{h}_{n,m}\bar{h}_{\bar{n},\bar{m}}\right)=0$,
$\forall n\neq\bar{n}$. As a result, $\mbox{\boldmath{$C$}}_{m,\bar{m}}$’s in
(74) are diagonal matrices. Based on this fact, in (9) we have

$\displaystyle\mbox{\boldmath{$\gamma$}}^{\frac{1}{2}}\mbox{\boldmath{$C$}}_{m,\bar{m}}\mbox{\boldmath{$\gamma$}}^{\frac{1}{2}}=\mbox{\boldmath{$C$}}_{m,\bar{m}}\mbox{\boldmath{$\gamma$}},~{}~{}\forall
m,\bar{m}.$ (76)

Combining (76) with the definition of $\Sigma$ (i.e., the first equality in
(9)) gives

$\displaystyle\mbox{\boldmath{$\Sigma$}}=$
$\displaystyle\bar{\mbox{\boldmath{$S$}}}\begin{bmatrix}\mbox{\boldmath{$C$}}_{1,1}\mbox{\boldmath{$\gamma$}}&\mbox{\boldmath{$C$}}_{1,2}\mbox{\boldmath{$\gamma$}}&\cdots&\mbox{\boldmath{$C$}}_{1,2M}\mbox{\boldmath{$\gamma$}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mbox{\boldmath{$C$}}_{2M,1}\mbox{\boldmath{$\gamma$}}&\mbox{\boldmath{$C$}}_{2M,2}\mbox{\boldmath{$\gamma$}}&\cdots&\mbox{\boldmath{$C$}}_{2M,2M}\mbox{\boldmath{$\gamma$}}\end{bmatrix}\bar{\mbox{\boldmath{$S$}}}^{T}+\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}}$
(77)
$\displaystyle=\bar{\mbox{\boldmath{$S$}}}\mbox{\boldmath{$C$}}\bar{\mbox{\boldmath{$\gamma$}}}\bar{\mbox{\boldmath{$S$}}}^{T}+\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}}.$
(78)

This completes the derivation of $\Sigma$ in (9).

Next, we derive the expression of $C$ in (73). Basically, we want to build
connections between the elements in
$\mbox{\boldmath{$C$}}=\mathbb{E}(\mbox{\boldmath{$\bar{h}$}}\mbox{\boldmath{$\bar{h}$}}^{T})$
and the elements in
$\mbox{\boldmath{$C$}}_{n}=\mathbb{E}(\mbox{\boldmath{$h$}}_{n}\mbox{\boldmath{$h$}}_{n}^{T})$’s
in (2). To this end, we first show the relationship between
$\mbox{\boldmath{$h$}}_{n}$ and $\bar{\mbox{\boldmath{$h$}}}$. We do this
through the following two steps:

  1. 1.

The relationship between $\mbox{\boldmath{$h$}}_{n}$ and
$\mbox{\boldmath{$h$}}_{m}^{\rm col}$ in $\bar{\mbox{\boldmath{$h$}}}$,
$n=1,\dots,N$, $m=1,\dots,M$. Recall that $\mbox{\boldmath{$h$}}_{m}^{\rm
col}$ denotes the $m$-th column of
$\mbox{\boldmath{$H$}}=[\mbox{\boldmath{$h$}}_{1},\mbox{\boldmath{$h$}}_{2},\dots,\mbox{\boldmath{$h$}}_{N}]^{T}$.
Then we have

$\displaystyle\mbox{\boldmath{$h$}}_{n}^{T}=\left[h_{n,1}^{\rm
col},\dots,h_{n,M}^{\rm col}\right],$ (79)

where $h_{n,m}^{\rm col}$ is the $n$-th element in
$\mbox{\boldmath{$h$}}_{m}^{\rm col}$. Moreover, rewriting
$\mbox{\boldmath{$h$}}_{n}$ in a real form gives

$\displaystyle\left[\Re{\left(\mbox{\boldmath{$h$}}_{n}^{T}\right)},\Im{\left(\mbox{\boldmath{$h$}}^{T}_{n}\right)}\right]^{T}=\left[\Re{\left(h_{n,1}^{\rm
col}\right)},\dots,\Re{\left(h_{n,M}^{\rm col}\right)},\Im{\left(h_{n,1}^{\rm
col}\right)},\dots,\Im{\left(h_{n,M}^{\rm col}\right)}\right].$ (80)

  2. 2.

The relationship between $\mbox{\boldmath{$h$}}_{m}^{\rm col}$ and
$\bar{\mbox{\boldmath{$h$}}}_{m}$ in $\bar{\mbox{\boldmath{$h$}}}$,
$m=1,\dots,M$. Specifically, according to the definition in (72), we have

$\displaystyle\Re{\left(h_{n,m}^{\rm
col}\right)}=\bar{h}_{n,2m-1},~{}\Im{\left(h_{n,m}^{\rm
col}\right)}=\bar{h}_{n,2m},~{}m=1,\dots,M.$ (81)

Then, substituting (81) into (80), the relationship
$\mbox{\boldmath{$h$}}_{n}$ and $\bar{\mbox{\boldmath{$h$}}}$ can be expressed
as

$\displaystyle\left[\Re{\left(\mbox{\boldmath{$h$}}_{n}^{T}\right)},\Im{\left(\mbox{\boldmath{$h$}}^{T}_{n}\right)}\right]^{T}=\left[\bar{h}_{n,1},\bar{h}_{n,3},\dots,\bar{h}_{n,2M-1},\bar{h}_{n,2},\bar{h}_{n,4},\dots,\bar{h}_{n,2M}\right]^{T},~{}n=1,\dots,N.$
(82)

Second, we show the relationship between the elements in
$\mbox{\boldmath{$C$}}=\mathbb{E}(\mbox{\boldmath{$\bar{h}$}}\mbox{\boldmath{$\bar{h}$}}^{T})$
and the elements in
$\mbox{\boldmath{$C$}}_{n}=\mathbb{E}(\mbox{\boldmath{$h$}}_{n}\mbox{\boldmath{$h$}}_{n}^{T})$’s
through (82). Note that, from (2) we have

$\displaystyle\left[\Re{\left(\mbox{\boldmath{$h$}}_{n}^{T}\right)},\Im{\left(\mbox{\boldmath{$h$}}^{T}_{n}\right)}\right]^{T}=\bar{\mbox{\boldmath{$C$}}}_{n}^{\frac{1}{2}}\left[\Re{\left(\ddot{\mbox{\boldmath{$h$}}}_{n}^{T}\right)},\Im{\left(\ddot{\mbox{\boldmath{$h$}}}^{T}_{n}\right)}\right]^{T},$
(83)

where

$\displaystyle\bar{\mbox{\boldmath{$C$}}}_{n}^{\frac{1}{2}}=\begin{bmatrix}\Re{\left(\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\right)}&-\Im{\left(\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\right)}\\\
\Im{\left(\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\right)}&\Re{\left(\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\right)}\end{bmatrix},$
(84)

$\Re{\left(\ddot{\mbox{\boldmath{$h$}}}_{n}\right)}\sim\mathcal{N}(0,\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}})$,
and
$\Im{\left(\ddot{\mbox{\boldmath{$h$}}}_{n}\right)}\sim\mathcal{N}(0,\frac{1}{2}\sigma^{2}\mbox{\boldmath{$I$}})$.
Combining (82), (83), and (84) together, we have

$\displaystyle\mathbb{E}\left(\left[\bar{h}_{n,1},\dots,\bar{h}_{n,2M-1},\bar{h}_{n,2},\dots,\bar{h}_{n,2M}\right]^{T}\left[\bar{h}_{n,1},\dots,\bar{h}_{n,2M-1},\bar{h}_{n,2},\dots,\bar{h}_{n,2M}\right]\right)$
$\displaystyle=\mathbb{E}\left(\left[\Re{\left(\mbox{\boldmath{$h$}}_{n}^{T}\right)},\Im{\left(\mbox{\boldmath{$h$}}^{T}_{n}\right)}\right]^{T}\left[\Re{\left(\mbox{\boldmath{$h$}}_{n}^{T}\right)},\Im{\left(\mbox{\boldmath{$h$}}^{T}_{n}\right)}\right]\right)$
$\displaystyle=\bar{\mbox{\boldmath{$C$}}}_{n}^{\frac{1}{2}}\frac{1}{2}\mbox{\boldmath{$I$}}\bar{\mbox{\boldmath{$C$}}}_{n}^{\frac{1}{2}}=\frac{1}{2}\bar{\mbox{\boldmath{$C$}}}_{n},~{}~{}\forall
n.$ (85)

Denote $c^{n,n}_{m,\bar{m}}$ the $n$-th diagonal element of
$\mbox{\boldmath{$C$}}_{m,\bar{m}}$ in (73). From (85), for
$k,\bar{k}=1,\dots,M$, the $n$-th diagonal element of the diagonal matrix
$\mbox{\boldmath{$C$}}_{m,\bar{m}}$ is expressed as

$\displaystyle
c^{n,n}_{m,\bar{m}}=\mathbb{E}\left(\bar{h}_{n,m}\bar{h}_{n,\bar{m}}\right)=\left\\{\begin{array}[]{llll}\frac{1}{2}\bar{c}_{n}^{k,\bar{k}},~{}~{}~{}~{}~{}~{}~{}{\rm
if}~{}m=2k-1,\bar{m}=2\bar{k}-1,\\\
\frac{1}{2}\bar{c}_{n}^{k,\bar{k}+M},~{}~{}~{}~{}{\rm
if}~{}m=2k-1,\bar{m}=2\bar{k},\\\
\frac{1}{2}\bar{c}_{n}^{k+M,\bar{k}},~{}~{}~{}~{}{\rm
if}~{}m=2k,\bar{m}=2\bar{k}-1,\\\
\frac{1}{2}\bar{c}_{n}^{k+M,\bar{k}+M},~{}{\rm
if}~{}m=2k,\bar{m}=2\bar{k},\end{array}\right.$ (90)

Though (90), we can construct $C$ from $\mbox{\boldmath{$C$}}_{n}$’s.

###  -C Proof of Theorem 2

Let $\lambda^{\ell,\ell}$ denote the power of $\bar{y}_{\ell}$,
$\ell=1,2,\dots,2L_{\rm I}M$, where $\bar{y}_{\ell}$ denotes the $\ell$-th
element of the received signal $\bar{\mbox{\boldmath{$y$}}}$ in (7). Since
$\Sigma$ is the covariance matrix of $\bar{\mbox{\boldmath{$y$}}}$, we compute
the diagonal elements of $\Sigma$, i.e., $\lambda^{\ell,\ell}$, $\forall l$.
In (9), denote

$\displaystyle\mbox{\boldmath{$D$}}=\bar{\mbox{\boldmath{$S$}}}\mbox{\boldmath{$C$}}\bar{\mbox{\boldmath{$\gamma$}}}\bar{\mbox{\boldmath{$S$}}}^{T}\in\mathbb{R}^{2L_{\rm
I}M\times 2L_{\rm I}M},$ (91)

and $d^{\ell,\ell}$ the $\ell$-th diagonal element of $D$. According to (9),
we have

$\displaystyle\lambda^{\ell,\ell}=d^{\ell,\ell}+\frac{1}{2}\sigma^{2},~{}~{}\ell=1,\dots,2L_{\rm
I}M.$ (92)

In the following, we compute $d^{\ell,\ell}$. Substituting
$\bar{\mbox{\boldmath{$S$}}}={\rm
diag}\\{\underbrace{\hat{\mbox{\boldmath{$S$}}},\dots,\hat{\mbox{\boldmath{$S$}}}}_{M}\\}$,
$C$ in (73), and $\bar{\mbox{\boldmath{$\gamma$}}}={\rm
diag}\\{\underbrace{\hat{\mbox{\boldmath{$\gamma$}}},\dots,\hat{\mbox{\boldmath{$\gamma$}}}}_{M}\\}$
into $D$ in (91), we have

$\displaystyle\mbox{\boldmath{$D$}}=\bar{\mbox{\boldmath{$S$}}}\mbox{\boldmath{$C$}}\bar{\mbox{\boldmath{$\gamma$}}}\bar{\mbox{\boldmath{$S$}}}^{T}=\begin{bmatrix}\mbox{\boldmath{$D$}}_{1,1}&\mbox{\boldmath{$D$}}_{1,2}&\cdots&\mbox{\boldmath{$D$}}_{1,M}\\\
\vdots&\vdots&\ddots&\vdots\\\
\mbox{\boldmath{$D$}}_{M,1}&\mbox{\boldmath{$D$}}_{M,2}&\cdots&\mbox{\boldmath{$D$}}_{M,M}\end{bmatrix}$
(93)

where

$\displaystyle\mbox{\boldmath{$D$}}_{m,\bar{m}}=\hat{\mbox{\boldmath{$S$}}}\begin{bmatrix}\mbox{\boldmath{$C$}}_{2m-1,2\bar{m}-1}\mbox{\boldmath{$\gamma$}}&\mbox{\boldmath{$C$}}_{2m-1,2\bar{m}}\mbox{\boldmath{$\gamma$}}\\\
\mbox{\boldmath{$C$}}_{2m,2\bar{m}-1}\mbox{\boldmath{$\gamma$}}&\mbox{\boldmath{$C$}}_{2m,2\bar{m}}\mbox{\boldmath{$\gamma$}}\end{bmatrix}\hat{\mbox{\boldmath{$S$}}}^{T},~{}~{}m,\bar{m}=1,\dots,M,$
(94)

and the expression of $\hat{\mbox{\boldmath{$S$}}}$ is shown below (68). Since
we want to compute the diagonal elements of $D$ in (93), we only care about
the diagonal elements in $\mbox{\boldmath{$D$}}_{m,m}$ in (94), $m=1,\dots,M$.

First, we show that within (94), we have

$\displaystyle\mbox{\boldmath{$C$}}_{2m-1,2m}=\mbox{\boldmath{$C$}}_{2m,2m-1}=\mbox{\boldmath{$0$}},m=1,\dots,M.$
(95)

We first show $\mbox{\boldmath{$C$}}_{2m-1,2m}=\mbox{\boldmath{$0$}}$,
$m=1,\dots,M$. Since $\mbox{\boldmath{$C$}}_{2m-1,2m}$ is a diagonal matrix,
it suffices to show that all diagonal elements of
$\mbox{\boldmath{$C$}}_{2m-1,2m}$ are zero. According to (90), the $n$-th
diagonal element in $\mbox{\boldmath{$C$}}_{2m-1,2m}$ is expressed as

$\displaystyle c_{2m-1,2m}^{n,n}=\frac{1}{2}\bar{c}^{m,m+M}_{n},n=1,\dots,N.$
(96)

In the following, we compute $\bar{c}^{m,m+M}_{n}$’s in
$\bar{\mbox{\boldmath{$C$}}}_{n}$. The $\bar{\mbox{\boldmath{$C$}}}_{n}$ in
(84) is expressed as

$\displaystyle\bar{\mbox{\boldmath{$C$}}}_{n}=\left(\bar{\mbox{\boldmath{$C$}}}_{n}\right)^{\frac{1}{2}}\left(\bar{\mbox{\boldmath{$C$}}}_{n}\right)^{\frac{1}{2}}$
$\displaystyle=\begin{bmatrix}\mbox{\boldmath{$A$}}_{n}&-\mbox{\boldmath{$B$}}_{n}\\\
\mbox{\boldmath{$B$}}_{n}&\mbox{\boldmath{$A$}}_{n}\end{bmatrix}\begin{bmatrix}\mbox{\boldmath{$A$}}_{n}&-\mbox{\boldmath{$B$}}_{n}\\\
\mbox{\boldmath{$B$}}_{n}&\mbox{\boldmath{$A$}}_{n}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$A$}}_{n}-\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$B$}}_{n}&-\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$B$}}_{n}-\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$A$}}_{n}\\\
\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$B$}}_{n}+\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$A$}}_{n}&\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$A$}}_{n}-\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$B$}}_{n}\end{bmatrix},$
(97)

where
$\mbox{\boldmath{$A$}}_{n}=\Re{\left(\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\right)}$
and
$\mbox{\boldmath{$B$}}_{n}=\Im{\left(\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\right)}$.
In addition, since

$\displaystyle\mbox{\boldmath{$C$}}_{n}$
$\displaystyle=\Re{\left(\mbox{\boldmath{$C$}}_{n}\right)}+i\Im{\left(\mbox{\boldmath{$C$}}_{n}\right)}=\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}\mbox{\boldmath{$C$}}_{n}^{\frac{1}{2}}=\left(\mbox{\boldmath{$A$}}_{n}+i\mbox{\boldmath{$B$}}_{n}\right)\left(\mbox{\boldmath{$A$}}_{n}+i\mbox{\boldmath{$B$}}_{n}\right)$
$\displaystyle=\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$A$}}_{n}-\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$B$}}_{n}+i\left(\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$B$}}_{n}+\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$A$}}_{n}\right),~{}\forall
n,$ (98)

we have

$\displaystyle\Re{\left(\mbox{\boldmath{$C$}}_{n}\right)}=\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$A$}}_{n}-\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$B$}}_{n},~{}\Im{\left(\mbox{\boldmath{$C$}}_{n}\right)}=\mbox{\boldmath{$A$}}_{n}\mbox{\boldmath{$B$}}_{n}+\mbox{\boldmath{$B$}}_{n}\mbox{\boldmath{$A$}}_{n}.$
(99)

Substituting (99) into (97), we have

$\displaystyle\bar{\mbox{\boldmath{$C$}}}_{n}=\begin{bmatrix}\Re{\left(\mbox{\boldmath{$C$}}_{n}\right)}&-\Im{\left(\mbox{\boldmath{$C$}}_{n}\right)}\\\
\Im{\left(\mbox{\boldmath{$C$}}_{n}\right)}&\Re{\left(\mbox{\boldmath{$C$}}_{n}\right)}\end{bmatrix},n=1,\dots,N.$
(100)

Denote $c_{n}^{m,m}$ the $m$-th diagonal element of
$\mbox{\boldmath{$C$}}_{n}$. Since $c_{n}^{m,m}=1$, $m=1,\dots,M$, in (100) we
have

$\displaystyle\bar{c}^{m,m+M}_{n}=-\Im{\left(c_{n}^{m,m}\right)}=0,$ (101)

which, together with (96), further implies

$\displaystyle
c_{2m-1,2m}^{n,n}=\frac{1}{2}\bar{c}^{m,m+M}_{n}=0,n=1,\dots,N.$ (102)

Thus, $\mbox{\boldmath{$C$}}_{2m-1,2m}=\mbox{\boldmath{$0$}}$, $m=1,\dots,M$.
Similarly, we can show that
$\mbox{\boldmath{$C$}}_{2m,2m-1}=\mbox{\boldmath{$0$}}$, $m=1,\dots,M$.

By combining the facts that $\mbox{\boldmath{$C$}}_{2m-1,2m}$’s and
$\mbox{\boldmath{$C$}}_{2m,2m-1}$’s are zero matrices, we can further express
$\mbox{\boldmath{$D$}}_{m,m}$ in (94) as

$\displaystyle\mbox{\boldmath{$D$}}_{m,m}$
$\displaystyle=\sum_{n=1}^{N}c^{2m-1,2m-1}_{n,n}\gamma_{n}\hat{\mbox{\boldmath{$s$}}}_{n}\hat{\mbox{\boldmath{$s$}}}_{n}^{T}+c^{2m,2m}_{n,n}\gamma_{n}\hat{\mbox{\boldmath{$s$}}}_{n+N}\hat{\mbox{\boldmath{$s$}}}_{n+N}^{T}$
(103)
$\displaystyle=\frac{1}{2}\sum_{n=1}^{N}\gamma_{n}\hat{\mbox{\boldmath{$s$}}}_{n}\hat{\mbox{\boldmath{$s$}}}_{n}^{T}+\gamma_{n}\hat{\mbox{\boldmath{$s$}}}_{n+N}\hat{\mbox{\boldmath{$s$}}}_{n+N}^{T},\forall
m,$ (104)

where $\gamma_{n}$ denotes the $n$-th element of $\gamma$ in (5), and
$\hat{\mbox{\boldmath{$s$}}}_{n}$ is the $n$-th column of
$\hat{\mbox{\boldmath{$S$}}}$. In addition, (103) to (104) follows from the
fact that, according to (96), we have
$c^{2m-1,2m-1}_{n,n}=c^{2m,2m}_{n,n}=\frac{1}{2}$, $m=1\dots,M$, and
$N=1,\dots,N$. Denote $d_{m,m}^{\ell,\ell}$ the $\ell$-th diagonal element in
$\mbox{\boldmath{$D$}}_{m,m}$. We have

$\displaystyle
d^{\ell,\ell}_{m,m}=\frac{1}{2}\sum_{n=1}^{N}\gamma_{n}\hat{s}_{\ell,n}\hat{s}_{\ell,n}+\frac{1}{2}\sum_{n=1}^{N}\gamma_{n}\hat{s}_{\ell,n+N}\hat{s}_{\ell,n+N},~{}m=1,\dots,M,~{}\ell=1,\dots,2L_{\rm
I},$ (105)

where $\hat{s}_{\ell,n}$ denotes the element in the $\ell$-th row and $n$-th
column of $\hat{\mbox{\boldmath{$S$}}}$. Within (105), for the first term in
the right-hand side, we have

$\displaystyle\frac{1}{2}\sum_{n=1}^{N}\gamma_{n}\hat{s}_{\ell,n}\hat{s}_{\ell,n}\overset{(a)}{=}\frac{1}{4}\sum_{n=1}^{N}\gamma_{n}=\frac{1}{4}\sum_{n\in\mathcal{K}}\beta=\frac{K}{4}\beta,$
(106)

where the equality $(a)$ follows from the fact that
$|\hat{s}_{\ell,n}|^{2}=\frac{1}{2}$, and the set
$\mathcal{K}=\\{n:\alpha_{n}=1,\forall n\\}$ denotes the set containing the
indices of $K$ active devices. Similarly, for the second term in the right-
hand side of (105), we have

$\displaystyle\frac{1}{2}\sum_{n=1}^{N}\gamma_{n}\hat{s}_{\ell,n+N}\hat{s}_{\ell,n+N}=\frac{1}{4}\sum_{n\in\mathcal{K}}\beta=\frac{K}{4}\beta.$
(107)

Substituting (106) and (107) into (105), we have

$\displaystyle
d^{\ell,\ell}_{m,m}=\frac{K}{2}\beta,~{}~{}m=1,\dots,M,~{}\ell=1,\dots,2L_{\rm
I}.$ (108)

Thus, we have

$\displaystyle d^{\ell,\ell}=\frac{K}{2}\beta,~{}~{}\ell=1,\dots,2L_{\rm I}M.$
(109)

Substituting (109) into (92), we have

$\displaystyle\lambda^{\ell,\ell}=d^{\ell,\ell}+\frac{1}{2}\sigma^{2}=\frac{K}{2}\beta+\frac{1}{2}\sigma^{2},~{}~{}\ell=1,\dots,2L_{\rm
I}M.$ (110)

## References

  * [1] C. Bockelmann, N. Pratas, H. Nikopour, K. Au, T. Svensson, C. Stefanovic, P. Popovski, and A. Dekorsy, “Massive machine-type communications in 5G: Physical and MAC-layer solutions,” _IEEE Commun. Mag._ , vol. 54, no. 9, pp. 59–65, Sept. 2016.
  * [2] X. Chen, D. W. K. Ng, W. Yu, E. G. Larsson, N. Al-Dhahir, and R. Schober, “Massive access for 5G and beyond,” _IEEE J. Sel. Areas Commun._ , vol. 39, no. 3, pp. 615–637, Mar. 2020.
  * [3] H. Shariatmadari, R. Ratasuk, S. Iraji, A. Laya, T. Taleb, R. Jäntti, and A. Ghosh, “Machine-type communications: Current status and future perspectives toward 5G systems,” _IEEE Commun. Mag._ , vol. 53, no. 9, pp. 10–17, Sept. 2015.
  * [4] K. Senel and E. G. Larsson, “Grant-free massive MTC-enabled massive MIMO: A compressive sensing approach,” _IEEE Trans. Commun._ , vol. 66, no. 12, pp. 6164–6175, Dec. 2018.
  * [5] Z. Chen, F. Sohrabi, and W. Yu, “Sparse activity detection for massive connectivity,” _IEEE Trans. Signal Process._ , vol. 66, no. 7, pp. 1890–1904, Apr. 2018.
  * [6] T. Jiang, Y. Shi, J. Zhang, and K. B. Letaief, “Joint activity detection and channel estimation for IoT networks: Phase transition and computation-estimation tradeoff,” _IEEE Internet of Things J._ , vol. 6, no. 4, pp. 6212–6225, Aug. 2018.
  * [7] M. Ke, Z. Gao, Y. Wu, X. Gao, and R. Schober, “Compressive sensing-based adaptive active user detection and channel estimation: Massive access meets massive MIMO,” _IEEE Trans. Signal Process._ , vol. 68, pp. 764–779, Jan. 2020.
  * [8] T. Ding, X. Yuan, and S. C. Liew, “Sparsity learning-based multiuser detection in grant-free massive-device multiple access,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 7, pp. 3569–3582, Jul. 2019.
  * [9] Z. Sun, Z. Wei, L. Yang, J. Yuan, X. Cheng, and L. Wan, “Exploiting transmission control for joint user identification and channel estimation in massive connectivity,” _IEEE Trans. Commun._ , vol. 67, no. 9, pp. 6311–6326, Sept. 2019.
  * [10] Y. Mei, Z. Gao, Y. Wu, W. Chen, J. Zhang, D. W. K. Ng, and M. Di Renzo, “Compressive sensing based joint activity and data detection for grant-free massive IoT access,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 3, pp. 1851–1869, Sept. 2021.
  * [11] L. Liu and W. Yu, “Massive connectivity with massive MIMO—Part I: Device activity detection and channel estimation,” _IEEE Trans. Signal Process._ , vol. 66, no. 11, pp. 2933–2946, Jun. 2018.
  * [12] Z. Chen, F. Sohrabi, Y.-F. Liu, and W. Yu, “Phase transition analysis for covariance-based massive random access with massive MIMO,” _IEEE Trans. Inf. Theory_ , vol. 68, no. 3, pp. 1696–1715, Dec. 2021.
  * [13] S. Haghighatshoar, P. Jung, and G. Caire, “Improved scaling law for activity detection in massive MIMO systems,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , June 2018, pp. 381–385.
  * [14] Z. Chen, F. Sohrabi, and W. Yu, “Sparse activity detection in multi-cell massive MIMO exploiting channel large-scale fading,” _IEEE Trans. Signal Process._ , vol. 69, pp. 3768 – 3781, Jun. 2021.
  * [15] Z. Chen, F. Sohrabi, Y.-F. Liu, and W. Yu, “Covariance based joint activity and data detection for massive random access with massive MIMO,” in _Proc. IEEE Int. Conf. Commun. (ICC)_ , May 2019, pp. 1–6.
  * [16] Z. Wang, Z. Chen, Y.-F. Liu, F. Sohrab, and W. Yu, “An efficient active set algorithm for covariance based joint data and activity detection for massive random access with massive MIMO,” in _Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Process. (ICASSP)_ , Jun. 2021.
  * [17] U. K. Ganesan, E. Björnson, and E. G. Larsson, “An algorithm for grant-free random access in cell-free massive MIMO,” in _Proc. IEEE Workshop Signal Process. Adv. Wireless Commun. (SPAWC)_ , May 2020, pp. 1–5.
  * [18] Z. Wang, Y.-F. Liu, Z. Chen, and W. Yu, “Accelerating coordinate descent via active set selection for device activity detection for multi-cell massive random access,” in _Proc. IEEE Workshop Signal Process. Adv. Wireless Commun. (SPAWC)_ , Sept. 2021.
  * [19] Z. Wang, Y.-F. Liu, and L. Liu, “Covariance-based joint device activity and delay detection in asynchronous mMTC,” _IEEE Signal Process. Lett._ , vol. 29, pp. 538–542, Jan. 2022.
  * [20] Y. Li, Q. Lin, Y.-F. Liu, B. Ai, and Y.-C. Wu, “Asynchronous activity detection for cell-free massive MIMO: From centralized to distributed algorithms,” _to appear in IEEE Trans. Wireless Commun._ , 2022.
  * [21] Z. Wang, Y.-F. Liu, Z. Wang, and W. Yu, “Scaling law analysis for covariance based activity detection in cooperative multi-cell massive MIMO,” [Online] Available: https://arxiv.org/abs/2210.14688.
  * [22] E. Björnson, J. Hoydis, and L. Sanguinetti, “Massive MIMO networks: Spectral, energy, and hardware efficiency,” _Foundations and Trends® Signal Process._ , vol. 11, no. 3-4, pp. 154–655, Nov. 2017.
  * [23] Y. Li, B. Bakkaloglu, and C. Chakrabarti, “A system level energy model and energy-quality evaluation for integrated transceiver front-ends,” _IEEE Trans. Very Large Scale Integration Syst._ , vol. 15, no. 1, pp. 90–103, Jan. 2007\.
  * [24] R. H. Walden, “Analog-to-digital converter survey and analysis,” _IEEE J. Sel. Areas Commun._ , vol. 17, no. 4, pp. 539–550, Apr. 1999.
  * [25] B. Le, T. W. Rondeau, J. H. Reed, and C. W. Bostian, “Analog-to-digital converters,” _IEEE Signal Process. Mag._ , vol. 22, no. 6, pp. 69–77, Oct. 2005.
  * [26] J. Mo and R. W. Heath, “Capacity analysis of one-bit quantized MIMO systems with transmitter channel state information,” _IEEE Trans. Signal Process._ , vol. 63, no. 20, pp. 5498–5512, Oct. 2015.
  * [27] J. Mo, P. Schniter, and R. W. Heath, “Channel estimation in broadband millimeter wave MIMO systems with few-bit ADCs,” _IEEE Trans. Signal Process._ , vol. 66, no. 5, pp. 1141–1154, Dec. 2017.
  * [28] L. Bottou, F. E. Curtis, and J. Nocedal, “Optimization methods for large-scale machine learning,” _SIAM Review_ , vol. 60, no. 2, pp. 223–311, 2018.
  * [29] X. Yang, S. Jin, C.-K. Wen, X. Li, and J. Xue, “Joint activity detection and channel estimation for massive connectivity network with 1-bit DAC,” in _Proc. IEEE Int. Conf. Wireless Commun. Signal Process. (WCSP)_ , Dec. 2019\.
  * [30] T. Liu, S. Jin, C.-K. Wen, M. Matthaiou, and X. You, “Generalized channel estimation and user detection for massive connectivity with mixed-ADC massive MIMO,” _IEEE Trans. Wireless Commun._ , vol. 18, no. 6, pp. 3236–3250, Apr. 2019.
  * [31] Y. Mei, Z. Gao, D. Mi, M. Matthaiou, P. Xiao, and R. Schober, “Massive access in extra large-scale MIMO with mixed-ADC over near field channels,” [Online] Available: https://arxiv.org/abs/2207.01983.
  * [32] E. Björnson, M. Matthaiou, and M. Debbah, “Massive MIMO with non-ideal arbitrary arrays: Hardware scaling laws and circuit-aware design,” _IEEE Trans. Wireless Commun._ , vol. 14, no. 8, pp. 4353–4368, Apr. 2015\.
  * [33] E. G. Birgin, J. M. Martínez, and M. Raydan, “Nonmonotone spectral projected gradient methods on convex sets,” _SIAM J. Optim._ , vol. 10, no. 4, pp. 1196–1211, 2000.
  * [34] 3GPP, “Evolved universal terrestrial radio access (E-UTRA); radio frequency (RF) system scenarios,” Technical Specification (TS) 36.942.
  * [35] S. L. Loyka, “Channel capacity of MIMO architecture using the exponential correlation matrix,” _IEEE Commun. lett._ , vol. 5, no. 9, pp. 369–371, Sept. 2001.