# Early Neighbor Rejection-Aided Tabu Search Detection for Large MIMO Systems
## 2 Background
### Conventional TS Algorithm  
We will now briefly explain the basic concepts of a conventional TS algorithm [13; 14], which are necessary for an understanding of the proposed algorithm. The TS algorithm starts the search process from a current solution \(\mathbf{x}^{(c)}\), which is often set to the zero-forcing solution \(\mathbf{x}_{\text{ZF}}=\mathbf{H}^{\dagger}\mathbf{y}\), where \(\mathbf{H}^{\dagger}\) denotes the left Moore-Penrose pseudo-inverse of \(\mathbf{H}\). Neighboring signal vectors around \(\mathbf{x}^{(c)}\) are determined based on neighboring criteria [14; 15]. In an iteration of the search process in TS, the neighborhood of \(\mathbf{x}^{(c)}\) is defined as a subset of vectors in \(\mathbb{A}^{N}\) that differ from \(\mathbf{x}^{(c)}\) in only one element. Specifically, the set of neighboring vectors \(\mathbf{x}\) of \(\mathbf{x}^{(c)}\) can be expressed as  
\[\mathbb{N}(\mathbf{x}^{(c)})=\{\mathbf{x}\in\mathbb{A}^{N}\setminus\mathbb{L}, |\mathbf{x}-\mathbf{x}^{(c)}|=d_{min}\}, \tag{7}\]where \(\mathbb{L}\) denotes a tabu list, which is a set of previously visited neighbors, and \(\mathbb{A}^{N}\setminus\mathbb{L}\) denotes the set of candidate neighboring vectors, excluding the vectors which are in \(\mathbb{L}\). Finally, \(d_{min}\) is the minimum distance between two constellation points. In each iteration, TS examines the neighbors of the current solution \(\mathbb{N}(\mathbf{x}^{(c)})\) and moves to the best neighbor \(\mathbf{x}^{(b)}\), which has the smallest ML metric among the vectors neighboring \(\mathbb{N}(\mathbf{x}^{(c)})\) (even if the best neighboring vector is worse in terms of ML cost \(\|\mathbf{y}-\mathbf{H}\mathbf{x}\|^{2}\) than the \(\mathbf{x}^{(c)}\)) [9]. Specifically, the best neighbor is given by  
\[\mathbf{x}^{(b)}=\arg\min_{\mathbf{x}\in\mathbb{N}(\mathbf{x}^{(c)})}\phi( \mathbf{x}). \tag{8}\]  
Hence, in each iteration, the best neighbor \(\mathbf{x}^{(b)}\) is inserted into \(\mathbb{L}\) to avoid cycling in the search process. If \(\mathbb{L}\) is full, the element that was first inserted into \(\mathbb{L}\) is released to make room for the new best neighbor.  
In each iteration, the ML metric of \(\mathbf{x}^{(b)}\), i.e., \(\phi(\mathbf{x}^{(b)})\), is compared with that of the best solution found so far, which is denoted by \(\phi(\mathbf{x}_{\text{TS}})\). Initially, \(\phi(\mathbf{x}_{\text{TS}})\) is set to \(\phi(\mathbf{x}_{\text{ZF}})\). If \(\phi(\mathbf{x}^{(b)})\) is smaller than \(\phi(\mathbf{x}_{\text{TS}})\), we then update \(\phi(\mathbf{x}_{\text{TS}})\) to \(\phi(\mathbf{x}^{(b)})\). The TS algorithm generally terminates after a preset maximum number of iterations \(M\), but we can employ early termination to reduce the overall complexity. In particular, we keep track of how many iterations have proceeded without any improvement, denoted by \(p\), in the \(\mathbf{x}_{\text{TS}}\). When \(p\) reaches its maximum \(p_{max}\), the TS algorithm is terminated and the final solution is determined to be the best found solution \(\mathbf{x}_{\text{TS}}\)[15; 16].  
It is worth noting that the ML metric of \(\mathbf{x}\) can be computed in a more computationally efficient form as  
\[\phi(\mathbf{x})=\|\mathbf{y}-\mathbf{H}\mathbf{x}\|^{2}=\|\mathbf{u}+\mathbf{ H}\Delta\mathbf{x}\|^{2}=\|\mathbf{u}+\mathbf{h}_{d}\delta_{d}\|^{2}, \tag{9}\]  
where \(\mathbf{u}=\mathbf{y}-\mathbf{H}\mathbf{x}^{(c)}\), \(\Delta\mathbf{x}=\mathbf{x}^{(c)}-\mathbf{x}=[0,\ldots,0,\delta_{d},0,\ldots,0 ]^{T}\) has only one nonzero element, which is \(\delta_{d}=x_{d}^{(c)}-x_{d}\), and \(\mathbf{h}_{d}\) is the \(d\)th column of \(\mathbf{H}\). Here, \(d\) is the index of the unique nonzero element in \(\Delta\mathbf{x}\).