Algorithm Unrolling for Massive Access via Deep Neural Network with Theoretical Guarantee

In this paper, we consider grant-free massive access in an IoT network, where a large number of single-antenna IoT devices sporadically transmit non-orthogonal preamble sequences to a multi-antenna BS. In such a network setting, we formulate the JADCE problem as a group-sparse matrix estimation problem by introducing a mixed $\ell_{1}/\ell_{2}$-norm. Based on the above discussions, we shall develop a new unrolled deep neural network framework by adopting the multidimensional generalization operator, named multidimensional shrinkage thresholding operator (MSTO) [35], to address this problem. Such an extension turns out to be non-trivial, as the MSTO for the group-row-sparse matrix breaks the independency between the sparse vectors, which brings formidable challenge to reveal the weight coupling structure and analyze the convergence rate for the proposed method. We address this challenge and provide the theoretical performance guarantee for the proposed framework that is capable of solving JADCE problem to support massive access in IoT networks.

The major contributions of this paper are summarized as follows:

• •

  We develop a novel unrolled deep neural network framework with three structures for group-sparse matrix estimation to support grant-free massive access in IoT networks. The proposed methods enjoy high robustness by inheriting the structure of ISTA and keep the computational complexity at a low level through end-to-end training.

• •

  We conduct rigorous theoretical analysis to get rid of the interpretability issue and facilitate the efficient training in IoT networks. We reveal the weight coupling structure between the training parameters and identify the property that the learned weight matrix only depends on the preamble signature. The theoretical analysis allows us to further simplify original unrolled network structure by reducing the redundant training parameters. Furthermore, we prove that the simplified unrolling neural networks enjoy a linear convergence rate.

• •

  Extensive simulations are conducted to validate the theoretical analysis and show the superior performance of the proposed algorithms in three critical aspects for grant-free massive access. Firstly, comparing with the robust algorithms such as ISTA, the proposed methods have much lower computational cost. Secondly, the proposed methods are more robust when comparing to computational-efficient algorithms such as AMP-based algorithms by considering simulating different preamble signatures, including Gaussian matrix, binary matrix, and ZC sequence. Thirdly, the proposed algorithms are capable of returning more accurate solutions comparing with the classical CS-based algorithms.

The rest of this paper is organized as follows. The system model and problem formulation are described in Section II. Section III presents the proposed three kinds of unrolled neural networks for solving the group-sparse matrix estimation problem. The convergence analysis of the proposed unrolled neuron networks is presented in Section IV. The numerical results of the proposed algorithms are illustrated in Section V. Finally, Section VI concludes this paper.

Consider the grant-free uplink transmission of a single-cell IoT network consisting of one $M$-antenna BS and $N$ single-antenna IoT devices, as shown in Fig. 2. Full frequency reuse and quasi-static block fading channels are considered in this paper. We denote $[N]=\{1,\ldots,N\}$ as the set of IoT devices, which sporadically communicate with the BS. In each transmission block, all the IoT devices independently decide whether or not to be active. Within a specific transmission block, we denote $a_{n}=1$ if device $n$ is active and $a_{n}=0$ otherwise. Because of the sporadic transmission, it is reasonable to assume that each IoT device is active with a probability being much smaller than 1. In addition, we assume that the active IoT devices are synchronized at the symbol level [17]. The preamble signal received at the BS, denoted as $\bm{y}(\ell)\in\mathbb{C}^{M}$, can be expressed as

where $\bm{h}_{n}\in{\mathbb{C}}^{M}$ denotes the channel vector between device $n$ and the BS, $s_{n}(\ell)\in\mathbb{C}$ denotes the $\ell$-th symbol of the preamble signature sequence transmitted by device $n$, $L$ denotes the length of the signature sequence, and $\bm{z}(\ell)\in\mathbb{C}^{M}$ denotes the additive white Gaussian noise (AWGN) vector at the BS.

As the length of the signature sequence is typically much smaller than the number of IoT devices, i.e., $L\ll N$, it is impossible to allocate mutually orthogonal signature sequences to all the IoT devices. Hence, each IoT device is assigned a unique signature sequence, which is generally non-orthogonal to the preamble sequences assigned to other IoT devices. Note that three different kinds of non-orthogonal preamble sequences will be considered in the simulations.

For notational ease, we denote $\bm{Y}=[\bm{y}(1),...,\bm{y}(L)]^{T}\in\mathbb{C}^{L\times M}$ as the received preamble signal matrix across $M$ antennas over the transmission duration of $L$ symbols, $\bm{H}=[\bm{h}_{1},...,\bm{h}_{N}]^{T}\in\mathbb{C}^{N\times M}$ as the channel matrix between $N$ devices and the BS, $\bm{Z}=[\bm{z}(1),...,\bm{z}(L)]\in\mathbb{C}^{L\times M}$ as the noise matrix at the BS, and $\bm{S}=[\bm{s}(1),...,\bm{s}(L)]^{T}\in\mathbb{C}^{L\times N}$ as the known preamble signature sequence matrix with $\bm{s}(\ell)=[s_{1}(\ell),...,s_{N}(\ell)]^{T}\in\mathbb{C}^{N}$. As a result, the preamble signal received at the BS can be rewritten as

where $\bm{A}={\rm{diag}}(a_{1},...,a_{N})\in\mathbb{R}^{N\times N}$ denotes the diagonal activity matrix. We aim to simultaneously detect the activity matrix $\bm{A}$ and estimate the channel matrix $\bm{H}$, which is known as a JADCE problem [13]. By denoting $\bm{X}^{\natural}=\bm{AH}\in\mathbb{C}^{N\times M}$, matrix $\bm{X}^{\natural}$ thus has the group-sparse structure in rows [17], as shown in Fig. 2. We further rewrite (2) as

Note that the active devices and their corresponding channel vectors can be recovered from the estimation of matrix $\bm{X}^{\natural}$ [17].

To estimate the group-row sparse matrix $\bm{X}^{\natural}$, we adopt the mixed $\ell_{1}/\ell_{2}$-norm [17] to induce the group sparsity, i.e., $\mathcal{R}(\bm{X})=\sum_{n=1}^{N}\|\bm{X}[n,:]\|_{2},$ where $\bm{X}[n,:]$ is the $n$-th row of matrix $\bm{X}$. The group-sparse matrix estimation problem can be reformulated as the following unconstrained convex optimization problem (also known as group LASSO) [36]

where $\lambda>0$ denotes the regulation parameter. As matrix $\bm{X}$ is group sparse in rows, problem $\mathscr{P}$ is essentially a group-sparse matrix estimation problem.

To facilitate efficient algorithm design, we rewrite (3) as its real-valued counterpart

where $\Re\{\cdot\}$ and $\Im\{\cdot\}$ represent the real part and imaginary part of a complex matrix. As a result, problem $\mathscr{P}$ can be further rewritten as

Therefore, our goal of JADCE becomes the recovering of matrix $\bm{\tilde{X}}^{\natural}$ based on the preamble matrix $\bm{\tilde{S}}$ and the noisy observation $\bm{\tilde{Y}}$.

The ISTA [36] is a popular approach to solve the group LASSO problem. In particular, the resulting ISTA iteration for (6) can be written as

where $\bm{\tilde{X}}^{k}$ is an estimate of ground truth $\bm{\tilde{X}}^{\natural}$ at iteration $k$, $\frac{1}{C}$ plays a role as step size, $\lambda$ is regulation parameter, and $\eta_{\lambda/C}(\cdot)$ denotes the MSTO [35]. Specifically, $\eta_{\theta}(\bm{X})[n]$ denotes as the $n$-th row of the matrix $\bm{X}$ after applying $\eta_{\theta}(\cdot)$, which is defined as [20]

However, ISTA suffers from an inherent trade-off between estimation performance and convergence rate based on the choice of $\lambda$, i.e., a larger $\lambda$ leads to faster convergence but a poorer estimation performance [21]. Moreover, the choice of step size $\frac{1}{C}$ also influences the convergence rate [33]. In the next section, we shall propose a learned ISTA framework by learning the parameters including $\lambda$ and the step size $\frac{1}{C}$ simultaneously to improve the convergence rate and estimation performance of ISTA for the group-sparse matrix estimation problem (ISTA-GS).

In this subsection, we propose three neural network structures under the unrolled framework for group-sparse matrix estimation problem $\mathscr{P}_{r}$.

In the training stage, we consider the framework that the neural networks learn to solve group-sparse matrix estimation problem $\mathscr{P}_{r}$ in a supervised way. Note that we denote $P$ samples training data as $\{\bm{\tilde{X}}_{i}^{\natural},\bm{\tilde{Y}}_{i}\}_{i=1}^{P}$, where $\bm{\tilde{X}}_{i}^{\natural}$ and $\bm{\tilde{Y}}_{i}$ are viewed as the label and the input, respectively. The following optimization problem is adopted in the whole training stage for training a $k$-layer network,

However, such large scale optimization easily converged to a bad local minimum [40]. The layer-wise training strategy is used to separate (16) into the following two parts, i.e., (17) and (18), where (17) is to find a good initialization of (18) to avoid bad local minima of (16). In particular, for training a $k$-layer network, we denote $\bm{\Theta}_{0:k-1}$ as the trainable parameters from layer $0$ to layer $k-1$, and $\bm{\Theta}_{k-1}$ as the trainable parameters in layer $k-1$. By fixing the parameters $\bm{\Theta}_{0:k-2}$ of the former $k-1$-layer network that has been trained and the parameters $\bm{\Theta}_{k-1}$’s initialization is given in Table I, we first learn the parameters $\bm{\Theta}_{k-1}$ with the learning rate $\alpha_{0}$ by using Adam algorithm [41] to solve the following optimization problem

where $\bm{\tilde{X}}^{k}(\bm{\Theta}_{0:k-1},\bm{\tilde{Y}},\bm{\tilde{X}}^{0})$ denotes the output of the $k$-layer network with input $\bm{\tilde{Y}}$ and initial point $\bm{\tilde{X}}^{0}$. Then, we use the parameters $\bm{\Theta}_{k-1}$ obtained by (17) and the fixed parameters $\bm{\Theta}_{0:k-2}$ as initialization and then tune all parameters $\bm{\Theta}_{0:k-1}$ with the learning rate $\alpha_{1}$ which is smaller than $\alpha_{0}$ by using Adam algorithm to solve

After applying the procedure successfully, we obtain the parameters $\bm{\Theta}_{0:k-1}$ for the whole $k$-layer network. So next we can train a $(k+1)$-layer network.

In the testing stage, since the known preamble signature $\bm{S}$ remains unchanged, the proposed unrolled networks can recover the changing channels. Given a newly received signal $\bm{\tilde{Y}}^{{}^{\prime}}$, the learned unrolled networks, i.e., LISTA-GS in (10), LISTA-GSCP in (13) and ALISTA-GS in (15), are applied for group-sparse matrix estimation. For instance, with LISTA-GS, we obtain the $(k+1)$-th layer recovered signal by using $\bm{\tilde{X}}^{k+1}=\eta_{(\theta^{k})^{*}}((\bm{W}_{1}^{k})^{*}\bm{\tilde{Y}}^{{}^{\prime}}+(\bm{W}_{2}^{k})^{*}\bm{\tilde{X}}^{k})$, where $(\theta^{k})^{*},(\bm{W}_{1}^{k})^{*}$, and $(\bm{W}_{2}^{k})^{*}$ are the learned parameters of the $k$-th layer.

The time complexity for the three neural network structures are mainly due to matrix multiplication. For LISTA-GS, the evaluation of the matrix multiplication $\bm{W}_{1}^{k}\bm{\tilde{Y}}$ and $\bm{W}_{2}^{k}\bm{\tilde{X}}^{k}$ require $\mathcal{O}(NLM+N^{2}M)$ time at each iteration. As for LISTA-GSCP and ALISTA-GS, the evaluation of the matrix multiplication $(\bm{W}^{k})^{T}(\bm{\tilde{Y}}-\bm{\tilde{S}}\bm{\tilde{X}}^{k})$ and $\gamma^{k}\bm{W}^{T}(\bm{\tilde{Y}}-\bm{\tilde{S}}\bm{\tilde{X}}^{k})$ require $\mathcal{O}(LNM)$ time at each iteration. Since the proposed methods converge faster than ISTA and with the same complexity per iteration, thereby reducing the computational cost.

For $K$-layer RNN, the ALISTA-GS contains only $2K$ total trainable parameters $\{\theta^{k},\gamma^{k}\}_{k=0}^{K-1}$, while LISTA-GS and LISTA-GSCP require $K(N^{2}+LN+1)$ variables $\{\bm{W}_{1}^{k},\bm{W}_{2}^{k},\theta^{k}\}_{k=0}^{K-1}$ and $K(LN+1)$ variables $\{\bm{W}^{k},\theta^{k}\}_{k=0}^{K-1}$, respectively. We summarize the initialization and the required numbers of trainable parameters for the $K$-layer networks in Table I. Since $\theta^{k}$ and $\gamma^{k}$ should be initialize to proper constants, we initialize $\theta^{k}=0.1$ and $\gamma^{k}=1$ in this paper.

In this subsection, we shall give the definition of “good” parameters for the LISTA-GSCP network structure that guarantees the linear convergence rate.

First, we need to introduce several fundamental definitions inspired by [34]. The first one is the mutual coherence [45] of $\bm{\tilde{S}}$, which characterizes the coherence between different columns of $\bm{\tilde{S}}$.

Lemma $1$ in [34] tells us that there exists a matrix $\bm{W}\in\mathbb{R}^{2L\times 2N}$ that attaches the infimum given in (21), i.e., $\mathcal{W}(\bm{\tilde{S}})\neq\emptyset,$ where a set of “good” weight matrices is defined as

Then, we define the “good” parameters to be learned in LISTA-GSCP as follows.

In Definition 2, we propose the “good” choice of the learning parameters in LISTA-GSCP. In the following subsection, we prove that the sequence of “good” parameters lead to the conclusion (19) in Theorem 2.

In this subsection, we give an upper bound of the recovery error for one sample $(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})\in\mathcal{X}(\beta,s,\sigma)$. We first introduce the extra notation $\psi$, to provide information about the group sparsity. For each $\bm{\tilde{X}}\in\mathbb{R}^{2N\times M}$, we define a function $\psi:\mathbb{R}^{2N\times M}\rightarrow\mathbb{R}^{2N}$ as

Specifically, for a vector $\bm{v}=[v_{1},v_{2},\ldots,v_{2N}]^{T}\in\mathbb{R}^{2N}$, we have $\psi(\bm{v})_{i}=|v_{i}|,\text{for all }i\in[2N].$ Note that ${\rm{supp}}(\psi(\bm{A}))$ can provide information about group sparsity of a given matrix $\bm{A}$. By simple calculations, one can get the following lemma.

By taking one sample $(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})\in\mathcal{X}(\beta,s,\sigma)$ and letting $\mathcal{I}={\rm{supp}}(\psi(\bm{\tilde{X}}^{\natural}))$, we establish the error bound by two steps: (i) We show that there are no false positive rows in $\bm{\tilde{X}}^{k}$ for all $k$. (ii) Since the no-false-positive property holds, we consider the component on $\mathcal{I}$.

In step (i), we prove the following lemma.

Lemma 2 shows that there are no false positive entries in $\bm{\tilde{X}}^{k}$. In another word, if (23) in LISTA-GSCP hold, then

This property implies that the recovery error of the component beyond $\mathcal{I}$ turns to be $0$.

In step (ii), we consider the component on $\mathcal{I}$. For all $i\in\mathcal{I}$, the LISTA-GSCP in (13) gives

where $\partial\|\cdot\|_{2}$ is given in (51). It can be viewed that (28) consists of three parts $(T1)$, $(T2)$, $(T3)$. Since $(\bm{W}^{k}[:,i])^{T}\bm{\tilde{S}}[:,i]=1$, then (28) can expressed as

The definition of $\partial\|\cdot\|_{2}$ in (51) shows that $\|\partial\|\bm{\tilde{X}}^{k+1}[i,:]\|_{2}\|_{2}\leq 1.$ Then, taking the norm on both sides in (29), one can get that for all $i\in\mathcal{I}$,

where (a) follows from the triangle inequality, (b) arises from the choice of “good” parameters in (2) and $\big{\|}(\bm{W}^{k}[:,i])^{T}\bm{\tilde{Z}}\big{\|}_{2}\leq\big{\|}\bm{W}^{k}[:,i]\big{\|}_{2}\|\bm{\tilde{Z}}\|_{F}.$ It is easy to check that (27) implies that $\big{\|}\bm{\tilde{X}}^{k}-\bm{\tilde{X}}^{\natural}\big{\|}_{2,1}=\big{\|}\bm{\tilde{X}}^{k}[\mathcal{I},:]-\bm{\tilde{X}}^{\natural}[\mathcal{I},:]\big{\|}_{2,1}$ for all $k$. Therefore, based on (IV-B), it follows that

where $C_{W}=\underset{k\geq 0}{\max}~{}\|\bm{W}^{k}\|_{2,1}$. The inequality (IV-B) provides the recursive form for consecutive errors of $\|\bm{\tilde{X}}^{k+1}-\bm{\tilde{X}}^{\natural}\|_{2,1}$ and $\|\bm{\tilde{X}}^{k}-\bm{\tilde{X}}^{\natural}\|_{2,1}$. Hence, we establish the recover error bound of mixed-norm for one sample $(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})\in\mathcal{X}(\beta,s,\sigma)$.

In this subsection, we give an upper bound of recovery error for the whole training samples. Note that $|\mathcal{I}|:={\rm{supp}}(\psi(\bm{\tilde{X}}^{\natural}))\leq s$ for all $(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})\in\mathcal{X}(\beta,s,\sigma)$. Taking supremum over $(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})\in\mathcal{X}(\beta,s,\sigma)$ on both sides of (IV-B), we have

Considering the “good” parameters of $\theta^{k}=\tilde{\mu}\sup_{(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})}\|\bm{\tilde{X}}^{k}-\bm{\tilde{X}}^{\natural}\|_{2,1}+\sigma C_{W},$ it follows that

provided that $2\tilde{\mu}s-\tilde{\mu}<1$. By letting $c=-\log(2\tilde{\mu}s-\tilde{\mu}),C=\frac{(s+1)C_{W}}{1+\tilde{\mu}-2\tilde{\mu}s}$, we have $\sup_{(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})}\|\bm{\tilde{X}}^{k+1}-\bm{\tilde{X}}^{\natural}\|_{2,1}\leq s\beta\exp(-c(k+1))+C\sigma.$ The fact that $\|\bm{X}\|_{F}\leq\|\bm{X}\|_{2,1}$ for any matrix $\bm{X}$ gives an upper bound of error with respect to Frobenius norm

As long as $s\leq(1+1/\tilde{\mu})/2$ and $c=-\log(2\tilde{\mu}s-\tilde{\mu})>0$ hold, the error bound holds uniformly for all $(\bm{\tilde{X}}^{\natural},\bm{\tilde{Z}})\in\mathcal{X}(\beta,s,\sigma)$. Then for $k$-layer network, we have

Therefore, we complete the proof of Theorem 2.

In this subsection, we first give the definition of the “good” parameters to be learned in the ALISTA-GS network. We then verify the convergence of ALISTA-GS for noiseless case. For noisy case, the analysis can be referred to that of Theorem $1$.