Accelerating Coordinate Descent via Active Set Selection for Device Activity Detection for Multi-Cell Massive Random Access

I Introduction

II System Model and Problem Formulation

III Proposed Active Set CD Algorithm

IV Simulation Results

V Conclusions

References

II-A System Model

II-B Problem Formulation

III-A Random CD Algorithm

III-B Proposed Algorithm

III-B1 Active Set Selection

III-B2 Active Set CD Algorithm

Abstract

Index Terms:

Theorem 1.

Ziyue Wang12, Ya-Feng Liu2, Zhilin Chen3, Wei Yu3 Email: [email protected], [email protected], {zchen, weiyu}@ece.utoronto.ca 1School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing, China 2LSEC, ICMSEC, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China 3Department of Electrical and Computer Engineering, University of Toronto, Toronto, Canada

We propose a computationally efficient algorithm for the device activity detection problem in the multi-cell massive multi-input multi-output (MIMO) system, where the active devices transmit their signature sequences to multiple BSs in multiple cells and all the BSs cooperate to detect the active devices. The device activity detection problem has been formulated as a maximum likelihood maximization (MLE) problem in the literature. The state-of-the-art algorithm for solving the problem is the (random) coordinate descent (CD) algorithm. However, the CD algorithm fails to exploit the special sparsity structure of the solution of the device activity detection problem, i.e., most of devices are not active in each time slot. In this paper, we propose a novel active set selection strategy to accelerate the CD algorithm and propose an efficient active set CD algorithm for solving the considered problem. Specifically, at each iteration, the proposed active set CD algorithm first selects a small subset of all devices, namely the active set, which contains a few devices that contribute the most to the deviation from the first-order optimality condition of the MLE problem thus potentially can provide the most improvement to the objective function, then applies the CD algorithm to perform the detection for the devices in the active set. Simulation results show that the proposed active set CD algorithm significantly outperforms the state-of-the-art CD algorithm in terms of the computational efficiency.

Active set, coordinate descent, device activity detection, massive random access.

Massive machine-type communication (mMTC) is expected to play a crucial role in the fifth-generation (5G) and beyond cellular systems [1]. A challenge in mMTC is massive random access, in which a large number of devices with sporadic data traffic wish to connect to the network in the uplink [2]. This task can be accomplished by a pilot stage, during which the active devices transmit their preassigned non-orthogonal signature sequences, and the network then identifies the active devices based on the received signals at the base-stations (BSs) [3]. The non-orthogonality of the sequences inevitably causes both intra-cell and inter-cell interference that impair the detection performance. This paper considers a cloud radio-access network (C-RAN) architecture to alleviate the inter-cell interference, and proposes a novel device activity detection algorithm, which is more computationally efficient than the state-of-the-art algorithm.

The device activity detection problem can be formulated as a compressed sensing problem, in which the instantaneous channel state information (CSI) and the device activity are jointly recovered by exploiting the sparsity in the device activity [4, 5, 6, 7]. When the CSI is not needed and the BSs are equipped with a large number of antennas, it is also possible to jointly estimate the device activities and the channel large-scale fading components by exploiting the channel statistical information via maximum likelihood estimation (MLE). This approach is proposed in [8] and termed as the covariance approach because the detection relies on the sample covariance matrix of the received signal. As compared to the compressed sensing approach, this covariance approach has the advantage of detecting many more active devices due to its quadratic-like scaling law [9]. While [8] considers the covariance approach in the single-cell scenario, the extensions to the multi-cell systems are studied in [10, 11], where the large-scale fading components are further assumed available and the cooperation among BSs are allowed.

In the covariance approach, the coordinate descent (CD) algorithm that iteratively updates the activity indicator of each device is commonly used since it can achieve excellent detection performance; see [8, 12, 13] for more details. In the single-cell scenario, the CD algorithm is also computationally efficient because it admits a closed-form solution for each update. Moreover, the computational efficiency of CD can further be improved by carefully designing the sampling strategy for coordinate selection [14] or employing the active set technique to update only a subset of the coordinates [15]. However, in the multi-cell scenario with BS cooperation, the CD algorithm becomes less appealing as it is generally impossible to get a closed-form solution for each coordinate update, which involves a polynomial function whose degree depends on the number of BSs [10, 11].

In this paper, we propose a computationally efficient active set algorithm for solving the activity detection problem in the mulit-cell scenario. By noting that most of devices are inactive, we exploit the sparsity in the device activity to reduce the computations on the inactive devices to improve the computational efficiency. To this end, with the same motivation as in [15], we design a novel active set selection strategy to accelerate the CD algorithm. Specifically, at each iteration, the proposed active set CD algorithm first selects a small subset of all devices, termed as the active set, which contains a few devices that contribute the most to the deviation from the first-order optimality condition of the optimization problem thus potentially can provide the most improvement to the overall objective function, then applies the CD algorithm to perform the detection for the devices in the active set. Simulation results show that the proposed active set CD algorithm significantly outperforms the state-of-the-art CD algorithm in terms of the computational efficiency without any detection performance loss. We also establish the finite termination property of the proposed active set CD algorithm.

Consider an uplink massive MIMO multi-cell system consisting of $B$ cells. Each cell contains one BS equipped with $M$ antennas and $N$ devices each equipped with a single antenna. We assume a C-RAN architecture, in which all $B$ BSs are connected to a central unit (CU) via fronthaul links such that the received signals can be collected and jointly processed at the CU for inter-cell interference mitigation. Let $\sqrt{g_{ibn}}\mathbf{h}_{ibn}$ denote the channel between device $n$ in cell $b$ and BS $i,$ where $g_{ibn}\geq 0$ is the large-scale fading coefficient depending on path-loss and shadowing, and $\mathbf{h}_{ibn}\in\mathbb{C}^{M}$ is the Rayleigh fading component following $\mathcal{CN}(\mathbf{0},\mathbf{I})$ . Assume that only $K\ll N$ devices are active during any coherence interval. Let $a_{bn}$ indicate the activity of device $n$ in cell $b,$ i.e., $a_{bn}=1$ if the device is active and $a_{bn}=0$ otherwise. For device identification, each device is preassigned a unique signature sequence $\mathbf{s}_{bn}\in\mathbb{C}^{L}$ with $L$ being the sequence length.

In the uplink pilot stage, all active devices transmit their signature sequences as random access requests. Assuming that the sequences are transmitted synchronously, the received signal at BS $b$ can be expressed as

	$\displaystyle\mathbf{Y}_{b}$	$\displaystyle=\sum_{n=1}^{N}a_{bn}\mathbf{s}_{bn}g_{bbn}^{\frac{1}{2}}\mathbf{h}_{bbn}^{T}+\sum_{j\neq b}\sum_{n=1}^{N}a_{jn}\mathbf{s}_{jn}g_{bjn}^{\frac{1}{2}}\mathbf{h}_{bjn}^{T}+\mathbf{W}_{b}$
		$\displaystyle=\mathbf{S}_{b}\mathbf{A}_{b}\mathbf{G}^{\frac{1}{2}}_{bb}\mathbf{H}_{bb}+\sum_{j\neq b}\mathbf{S}_{j}\mathbf{A}_{j}\mathbf{G}^{\frac{1}{2}}_{bj}\mathbf{H}_{bj}+\mathbf{W}_{b}.$		(1)

In the above, $\mathbf{S}_{j}=[\mathbf{s}_{j1},\ldots,\mathbf{s}_{jN}]\in\mathbb{C}^{L\times N}$ is the signature sequence matrix of the devices in cell $j,$ $\mathbf{A}_{j}=\operatorname{diag}\{a_{j1},\ldots,a_{jN}\}$ is a diagonal matrix that indicates the activity of the devices in cell $j,$ $\mathbf{G}_{bj}=\operatorname{diag}\{g_{bj1},\ldots,g_{bjN}\}$ contains the large-scale fading components between the devices in cell $j$ and BS $b,$ $\mathbf{H}_{bj}=[\mathbf{h}_{bj1},\ldots,\mathbf{h}_{bjN}]^{T}\in\mathbb{C}^{N\times M}$ is the Rayleigh fading channel between the devices in cell $j$ and BS $b,$ and $\mathbf{W}_{b}$ is the additive Gaussian noise that follows $\mathcal{CN}(\mathbf{0},\sigma_{w}^{2}\mathbf{I}),$ where $\sigma_{w}^{2}$ is the variance of the background noise normalized by the transmit power for notational simplicity.

Let $\underline{\mathbf{a}}=[\mathbf{a}_{1}^{T},\ldots,\mathbf{a}_{B}^{T}]^{T}\in\mathbb{R}^{BN}$ indicate the activity of all the devices, where $\mathbf{a}_{j}=[a_{j1},\ldots,a_{jN}]^{T}$ denotes the diagonal entries of $\textbf{A}_{j}.$

In this paper, we consider the activity detection problem with known large-scale fading coefficients, i.e., we assume $\mathbf{G}_{bj},$ for all $b$ and $j$ are known at the BS. In this case, the activity detection problem is to detect the active devices in the system based on the received signals $\mathbf{Y}_{b},~{}b=1,\ldots,B,$ and is equivalent to estimating the activity indicator vector $\underline{\mathbf{a}}.$

As shown in [11], the above activity dectction problem can be mathematically formulated as the MLE problem. Notice from (II-A) that for each BS $b,$ the received signals at the $M$ antennas are i.i.d. due to the fact that the Rayleigh fading components are i.i.d. over the antennas. Let $\mathbf{y}_{bm}$ denote the received signal at the $m$ -th antenna. Then one can show that $\mathbf{y}_{bm}\sim\mathcal{CN}(\mathbf{0},\bm{\Sigma}_{b}),$ where $\bm{\Sigma}_{b}$ is given by

\displaystyle{\bm{\Sigma}_{b}=\frac{1}{M}\mathbb{E}\left[\mathbf{Y}_{b}\mathbf{Y}_{b}^{H}\right]=\sum_{j=1}^{B}\mathbf{S}_{j}\mathbf{A}_{j}\mathbf{G}_{bj}\mathbf{S}_{j}^{H}+\sigma_{w}^{2}\mathbf{I},}

(2)

and the likelihood function of $\mathbf{Y}_{b}$ can be expressed as

\displaystyle p(\mathbf{Y}_{b}\mid\underline{\textbf{a}})=\frac{1}{|\pi\bm{\Sigma}_{b}|^{M}}\exp{\left(-\operatorname{tr}\left(M\bm{\Sigma}_{b}^{-1}\hat{\bm{\Sigma}}_{b}\right)\right)},

(3)

where $\hat{\bm{\Sigma}}_{b}=\mathbf{Y}_{b}\mathbf{Y}_{b}^{H}/M$ is the sample covariance matrix computed by averaging over different antennas. Since the received signals $\mathbf{Y}_{b},$ $b=1,\ldots,B,$ are independent given $\underline{\mathbf{a}},$ the likelihood function of $\mathbf{Y}_{1},\ldots,\mathbf{Y}_{B}$ can then be written as

\displaystyle p(\mathbf{Y}_{1},\ldots,\mathbf{Y}_{B}\mid\underline{\textbf{a}})=\prod_{b=1}^{B}p(\mathbf{Y}_{b}\mid\underline{\textbf{a}}).

The maximization of the log-likelihood function, which is equivalent to the minimization of $-\tfrac{1}{M}\log p(\mathbf{Y}_{1},\ldots,\mathbf{Y}_{B}|~{}\underline{\textbf{a}}),$ can be formulated as


$\displaystyle\underset{\underline{\textbf{a}}}{\operatorname{minimize}}$	$\displaystyle\sum_{b=1}^{B}\left(\log\left\|\bm{\Sigma}_{b}\right\|+\operatorname{tr}\left(\bm{\Sigma}_{b}^{-1}\hat{\bm{\Sigma}}_{b}\right)\right)$	(4a)
$\displaystyle\operatorname{subject\,to}$	$\displaystyle a_{bn}\in[0,1],\,\forall\,b,n,$	(4b)

where the box constraint (4b) is a continuous relaxation of the binary constraint $a_{bn}\in\{0,1\}.$ The approach of estimating activity devices based on solving problem (4) is called the covariance based approach, because the solution of problem (4) depends on the received signal $\mathbf{Y}_{b}$ only through its sample covariance $\hat{\bm{\Sigma}}_{b}.$ The above problem (4) looks similar to its single-cell counterpart at the first glance, but in reality problem (4) is much more difficult to solve.

Let $f(\underline{\textbf{a}})$ denote the objective function of problem (4). Then, for any $b=1,2,\ldots,B,\,n=1,2,\ldots,N,$ the gradient of $f(\underline{\textbf{a}})$ with respect to $a_{bn}$ is

\left[\nabla f(\underline{\textbf{a}})\right]_{bn}=\sum_{j=1}^{B}g_{jbn}\left(\mathbf{s}_{bn}^{H}\bm{\Sigma}_{j}^{-1}\mathbf{s}_{bn}-\mathbf{s}_{bn}^{H}\bm{\Sigma}_{j}^{-1}\hat{\bm{\Sigma}}_{j}\bm{\Sigma}_{j}^{-1}\mathbf{s}_{bn}\right).

The first-order optimality condition of problem (4) is

\displaystyle\left[\nabla f(\underline{\textbf{a}})\right]_{bn}\begin{cases}\geq 0,&\operatorname{if}~{}a_{bn}=0;\\ \leq 0,&\operatorname{if}~{}a_{bn}=1;\\ =0,&\operatorname{if}~{}0<a_{bn}<1,\end{cases}\ \forall~{}b,n,

(5)

which is equivalent to

\operatorname{Proj}(\underline{\textbf{a}}-\nabla f(\underline{\textbf{a}}))-\underline{\textbf{a}}=\textbf{0},

where $\operatorname{Proj}(\cdot)$ is the projection operator onto the interval $[0,1].$

The basic idea of the proposed active set CD algorithm for solving problem (4) is to fully exploit the special structure of its solution, i.e., most components of the solution will be located at the boundary of the box constraint. In principle, the active set idea can be applied to accelerate any algorithm for solving problem (4) which does not exploit the special structure of its solution. Since the random CD algorithm is the state-or-the-art algorithm for solving problem (4), this paper devotes to further accelerate the random CD algorithm by the active set strategy. Below, we first introduce the random CD algorithm in details.

Random permuted CD [16] is one of the most efficient variants of the CD type of algorithms for solving problem (4). At each iteration, the algorithm randomly permutes the indices of all variables and then updates the variables one by one according to the order in the permutation. In particular, for any given coordinate $(b,n),$ we need to solve the following one-dimensional problem

in order to possibly update $a_{bn}.$ The closed-form solution for the above problem does not exist, which is different from the single-cell case. However, as the derivative of the objective function of (6) involves a polynomial function of degree $2B-1,$ we can find the desired $d$ by a root-finding algorithm. The CD algorithm is terminated when

\|\operatorname{Proj}(\underline{\textbf{a}}-\nabla f(\underline{\textbf{a}}))-\underline{\textbf{a}}\|_{2}<\varepsilon

(7)

is satisfied, where $\varepsilon>0$ is the error tolerance. The details of the random CD algorithm are summarized in Algorithm 1.

Algorithm 1: Random CD algorithm for solving problem (4) 1: Initialize: $\underline{\textbf{a}}=\mathbf{0},$ $\bm{\Sigma}_{b}^{-1}=\sigma_{w}^{-2}\textbf{I},$ $b=1,\ldots B,$ and $\varepsilon>0;$ 2: repeat {one iteration} 3: Randomly select a permutation $\{i_{1},i_{2},\ldots i_{BN}\}$ of the coordinate indices $\{1,2,\ldots BN\}$ of $\underline{\textbf{a}};$ 4: for $n=1$ to $BN$ do 5: Solve problem (6) to obtain $d;$ 6: $a_{i_{n}}\leftarrow a_{i_{n}}+d;$ 7: $\bm{\Sigma}_{b}^{-1}\leftarrow\bm{\Sigma}_{b}^{-1}-d\frac{\bm{\Sigma}_{b}^{-1}\textbf{s}_{i_{n}}\textbf{s}_{i_{n}}^{H}\bm{\Sigma}_{b}^{-1}}{1+d\textbf{s}_{i_{n}}^{H}\bm{\Sigma}_{b}^{-1}\textbf{s}_{i_{n}}},$ $b=1,\ldots,B;$ 8: end for 9: until $\|\operatorname{Proj}(\underline{\textbf{a}}-\nabla f(\underline{\textbf{a}}))-\underline{\textbf{a}}\|_{2}<\varepsilon$ 10: Output: $\underline{\textbf{a}}.$

Notice that, at each iteration, Algorithm 1 treats all coordinates equally and tries to update all of them. However, due to the special structure of the solution of problem (4), there will be quite a lot of coordinates $(b,n)$ with which problem (6) has been solved but $a_{bn}$ does not change, i.e., the corresponding solution of problem (6) is zero. This kind of computation is unnecessary and slows down Algorithm 1. The goal of this paper is to use the active set selection strategy to reduce the unnecessary computations and accelerate Algorithm 1.

In contrast to Algorithm 1, at each iteration, the active set CD algorithm first judiciously selects an active set, then uses Algorithm 1 to update the coordinates in the active set once. Due to the special structure of the solution of problem (4), it is expected that the cardinality of the selected active set will be significantly less than the total number of devices (i.e., $BN$ ), and more importantly will gradually decrease as the iteration goes on. Therefore, the active set CD algorithm will save much unnecessary computational cost in Algorithm 1 and significantly accelerates it.

In principle, the desirable active set should contain coordinates that contribute the most to the deviation from the optimality condition in (5) at each iteration, so that their updates would improve the objective function as much as possible; on the other hand, its cardinality should be as small as possible in order to avoid unnecessary computation and improve the computational efficiency. Therefore, there is a trade-off in selecting the coordinates that violate (5) into the active set. In practice, our selection strategy of the active set $\mathcal{A}^{k}$ at a given feasible point $\underline{\mathbf{a}}^{k}$ is mainly based on the degree of the violation of the first-order optimality condition (5). Specifically, at the $k$ -th iteration, (i) in case $a^{k}_{bn}=0,$ we only choose coordinates with a sufficiently large negative gradient into the active set; (ii) similarly, in case $a^{k}_{bn}=1,$ we choose coordinates with a sufficiently large positive gradient into the active set; and (iii) in case $a^{k}_{bn}\in(0,1),$ we choose coordinates with the absolute value of the gradient being large enough into the active set. Mathematically, the proposed selection strategy of the active set $\mathcal{A}^{k}$ can be expressed as

$\displaystyle\mathcal{A}^{k}=$	$\displaystyle\left\{(b,n)\mid a^{k}_{bn}=0\ \textup{and}\ \nabla f^{k}_{bn}<-\delta_{bn}^{k}\right\}$
	$\displaystyle\cup\left\{(b,n)\mid a^{k}_{bn}=1\ \textup{and}\ \nabla f^{k}_{bn}>\delta_{bn}^{k}\right\}$	(8)
	$\displaystyle\cup\left\{(b,n)\mid 0<a^{k}_{bn}<1\ \textup{and}\ \left\|\nabla f^{k}_{bn}\right\|>\delta_{bn}^{k}\right\},$

where $\nabla f_{bn}^{k}$ denotes $\left[\nabla f(\underline{\mathbf{a}}^{k})\right]_{bn}$ and $\bm{\delta}^{k}\in\mathbb{R}^{BN}_{+}$ is a threshold vector which changes with interation.

The choice of the threshold vector $\bm{\delta}^{k}$ in (III-B1) plays an important role in balancing the competing goals of decreasing the objective function and reducing the cardinality of the active set (thus the computational cost) at the $k$ -th iteration. If the components of $\bm{\delta}^{k}$ are large, the cardinality of the active set at the $k$ -th iteration will be small (and the iteration will need less computations), but the decrease of the objective function will also be small. The reverse is also true. In particular, if $\bm{\delta}^{k}=\textbf{0},$ all coordinates that violate (5) will be chosen in the active set. A way of choosing the parameter $\bm{\delta}^{k}$ is to set a relatively large initial $\bm{\delta}^{0}$ and then gradually decrease $\bm{\delta}^{k}$ at each iteration.

Based on the above analysis, we propose the active set CD algorithm for solving problem (4), which is detailed in Algorithm 2.

Algorithm 2: Proposed active set CD algorithm for solving problem (4) 1: Initialize: $\underline{\textbf{a}}^{0}=\mathbf{0},$ $k=0,$ and $\varepsilon>0;$ 2: repeat {one iteration} 3: Update $\bm{\delta}^{k};$ 4: Select the active set $\mathcal{A}^{k}$ according to (III-B1); 5: Apply Algorithm 1 to update all coordinates in $\mathcal{A}^{k}$ only once; 6: Set $k\leftarrow k+1;$ 7: until $\|\operatorname{Proj}(\underline{\textbf{a}}^{k}-\nabla f^{k})-\underline{\textbf{a}}^{k}\|_{2}<\varepsilon$ 8: Output: $\underline{\textbf{a}}^{k}.$

The convergence property of the proposed active set CD Algorithm 2 is presented in the following Theorem 1. Note that a poor choice of the active set might lead to oscillation and even divergence of the corresponding algorithm. The following finite termination property of the proposed Algorithm 2 is mainly because of the active set selection strategy in (III-B1) (and careful choices of vectors $\bm{\delta}^{k}$ ), and the convergence property of Algorithm 1. Due to the space limitation, we omit the rigorous proof of Theorem 1.

For any given error tolerance $\varepsilon>0,$ suppose that the threshold vector $\bm{\delta}^{k}$ in (III-B1) satisfy that $\|\bm{\delta}^{k}\|_{2}$ decreases monotonically with $k$ and $\lim\limits_{k\rightarrow\infty}\|\bm{\delta}^{k}\|_{2}<\varepsilon,$ then the proposed active set CD Algorithm 2 will terminate within a finite number of iterations.

Finally, it is worth mentioning that the motivation of Algorithm 2 in this paper is similar to that of [15], which also uses the sporadic nature of the device activities to lower the complexity in algorithmic design. However, the philosophy of selecting the active set in the two algorithms substantially differs from each other. In particular, the active set in [15] aims to contain all the active devices, while the active set in Algorithm 2 aims to contain devices whose activities are most likely to be incorrect. The reason for the difference is that the large-scale fading coefficients are assumed to be known in this paper, so that $\textbf{0}\leq\underline{\textbf{a}}\leq\textbf{1},$ but in [15] the large-scaling fading coefficients need to be estimated. This difference further leads to a totally different convergence behavior of the active set in the two algorithms: the cardinality of the active set in [15] will converge to a constant (which is in the same order as the number of active devices) but the cardinality of the active set in Algorithm 2 will converge to zero, i.e., there will be no (uncertain) devices which will violate the optimality condition when the algorithm terminates.

In this section, we demonstrate the efficiency of our proposed active set CD algorithm via numerical simulations. The parameters in simulations are the same as those in [11]. More specifically, we consider a multi-cell system consisting of $B=7$ hexagonal cells with wrap-around at the boundary, and $N$ devices uniformly distributed within each cell. The radius of each cell is $250$ m; the channel path-loss is modeled as $128.1+37.6\log_{10}(d),$ where $d$ is the corresponding BS-device distance in km; the transmit power of each device is set as $23$ dBm, and the background noise power is $-169$ dBm/Hz over $10$ MHz; and the number of antennas at each BS is $M=512.$ In all simulations, all signature sequences are sampled from i.i.d. complex Gaussian distribution with zero mean and unit variance. The tolerance is $\varepsilon=10^{-3}$ and in the proposed Algorithm 2, the threshold vector $\bm{\delta}^{k}$ is chosen as

\displaystyle\delta_{bn}^{k}=\begin{cases}10^{-k-2}\times\max\left\{\left|\nabla f^{k}_{bn}\right|\mid a_{bn}^{k}=0\right\},&\operatorname{if}~{}a_{bn}^{k}=0;\\ 10^{-k-2}\times\max\left\{\left|\nabla f^{k}_{bn}\right|\mid a_{bn}^{k}=1\right\},&\operatorname{if}~{}a_{bn}^{k}=1;\\ \max\{5^{-k},\varepsilon/\sqrt{0.3BN}\},&\operatorname{otherwise,}\end{cases}

which satisfies the conditions in Theorem 1.

Refer to caption — Figure 1: Average CPU time comparison of the proposed active set CD algorithm and the random CD algorithm.

Fig. 1 plots the CPU time comparison of Algorithm 1 and Algorithm 2 versus the number of devices in each cell. In each cell, for a given number of devices $N,$ we set the number of active devices $K=N/10$ with $L$ ranging from $15$ (for $N=100$ ) to $45$ (for $N=1000$ ). The simulation results are obtained by averaging over $200$ Monte-Carlo runs. It can be observed that the active set CD algorithm is significantly more efficient than the random CD algorithm.

We now compare the detection performance (i.e., probability of missed detection and probability of false alarm) of the two algorithms in Fig. 2 with $N=200,$ $K=20,$ and $L=20.$ A trade-off between missed detection and false alarm can be obtained by selecting different thresholds. We can observe from Fig. 2 that the detection performance curves of these two algorithms completely overlap, which shows that both the active set CD algorithm and the random CD algorithm converge to the same solution of problem (4) (albeit the problem is generally nonconvex).

To reveal why and how the active set selection helps significantly reduce the computational cost, we present more details on the update of each variable and classify it into two different cases: case (i) where the variable is successfully updated and case (ii) where unnecessary check/computation is done (and the variable is not updated). The dominant computational cost in case (i) consists of solving the roots of the polynomial function with degree $2B-1$ and doing rank-one updates to the matrix $\bm{\Sigma}_{b}^{-1}$ for all $b$ and the dominant computational cost in case (ii) is to solve the roots of the polynomial function.

Fig. 3 plots the numbers of cases (i) and (ii) that happened in different algorithms on a (randomly generated) problem instance with $N=200,$ $K=20,$ and $L=20.$ It can be clearly seen from Fig. 3 that the number of unnecessary checks is significantly greater than the number of successful updates in the random CD algorithm, which shows that a lot of unnecessary computations are done in it. This is not surprising, as many entries of the solution of problem (4) are either $0$ or $1$ but the random CD algorithm fails to exploit this special structure by treating all entries equally. We can also observe from Fig. 3 that the proposed active set CD algorithm can significantly reduce the number of unnecessary checks thus significantly improving the computational efficiency of the random CD algorithm. This shows the importance of exploiting the special structure of problem (4) as well as the efficiency of the proposed active set selection strategy.

Fig. 3 shows the cardinality of the active set at each iteration in the proposed active set CD algorithm. We can observe from Fig. 3 that the cardinality of the active set gradually decreases and becomes zero when the algorithm terminates, which is in sharp contrast to that in [15]. Fig. 3 also demonstrates the active set CD algorithm can converge quickly and verifies the finite termination property of the algorithm in Theorem 1.

This paper proposes an efficient active set CD algorithm for solving covariance based device activity detection in a cooperative multi-cell massive MIMO system. The proposed algorithm selects those coordinates that can potentially most improve the objective function in the active set and only updates the coordinates in the active set at each iteration, which is in contrast to the random CD algorithm which updates all coordinates at each iteration. Numerical results show that the proposed active set CD algorithm can achieve the same detection performance as the state-of-the-art random CD algorithm but with a significant less CPU time.

$\displaystyle\underset{d}{\operatorname{minimize}}$

$\displaystyle\sum_{j=1}^{B}\Bigg{(}\log\left(1+dg_{jbn}\mathbf{s}_{bn}^{H}\bm{\Sigma}_{j}^{-1}\mathbf{s}_{bn}\right)$

$\displaystyle\qquad\qquad\left.-\frac{dg_{jbn}\mathbf{s}_{bn}^{H}\bm{\Sigma}_{j}^{-1}\hat{\bm{\Sigma}}_{j}\bm{\Sigma}_{j}^{-1}\mathbf{s}_{bn}}{1+dg_{jbn}\mathbf{s}_{bn}^{H}\bm{\Sigma}_{j}^{-1}\mathbf{s}_{bn}}\right)$

$\displaystyle\operatorname{subject\,to}$

$\displaystyle d\in[-a_{bn},1-a_{bn}]$

[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, 2021.
[3] L. Liu, E. G. Larsson, W. Yu, P. Popovski, Č. Stefanović, and E. de Carvalho, “Sparse signal processing for grant-free massive connectivity: A future paradigm for random access protocols in the internet of things,” IEEE Signal Process. Mag., vol. 35, no. 5, pp. 88–99, Sept. 2018.
[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] 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, June 2018.
[6] 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.
[7] L. Liu and Y.-F. Liu, “An efficient algorithm for device detection and channel estimation in asynchronous IoT systems,” in Proc. IEEE Int. Conf. Acoustics, Speech, Signal Process. (ICASSP), Toronto, Canada, 2021. [Online]. Available: https://arxiv.org/abs/2010.09979
[8] 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), Vail, CO, USA, June 2018, pp. 381–385.
[9] A. Fengler, S. Haghighatshoar, P. Jung, and G. Caire, “Non-Bayesian activity detection, large-scale fading coefficient estimation, and unsourced random access with a massive MIMO receiver,” 2019. [Online]. Available: http://arxiv.org/abs/1910.11266
[10] 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), Atlanta, GA, USA, May 2020, pp. 1–5.
[11] Z. Chen, F. Sohrabi, and W. Yu, “Sparse activity detection in multi-cell massive MIMO exploiting channel large-scale fading,” 2021. [Online]. Available: https://arxiv.org/abs/2103.00782
[12] Z. Chen, F. Sohrabi, Y.-F. Liu, and W. Yu, “Phase transition analysis for covariance based massive random access with massive MIMO,” 2020. [Online]. Available: https://arxiv.org/abs/2003.04175
[13] D. Jiang and Y. Cui, “ML estimation and MAP estimation for device activities in grant-free random access with interference,” in Proc. IEEE Wireless Commun. Netw. Conf. (WCNC), 2020, pp. 1–6.
[14] J. Dong, J. Zhang, Y. Shi, and J. H. Wang, “Faster activity and data detection in massive random access: A multi-armed bandit approach,” 2020. [Online]. Available: https://arxiv.org/abs/2001.10237
[15] Z. Wang, Z. Chen, Y.-F. Liu, F. Sohrabi, 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. Acoustics, Speech, Signal Process. (ICASSP), Toronto, Canada, 2021. [Online]. Available: https://arxiv.org/abs/2102.03490
[16] 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), Shanghai, China, May 2019, pp. 1–6.