# Gibbs Sampling Detection for Large MIMO and MTC Uplinks with Adaptive Modulation
## 3 Gibbs Sampling for MIMO Detection
### Mixed Gibbs Sampling with Multiple Restarts  
As stated previously, stalling occurs because the ML cost of the state vector may be trapped in a local minima for many iterations [23]. That is in part due to the norm inside the exponential in (5), which may cause disparate sampling probabilities. One possible approach is to try and optimize the temperature parameter \(\alpha\) such that the probability of encountering the optimal solution is as high as possible. This evaluation was done in [22], and its performance will be shown in a subsequent section. Following what was done in [23; 27], a mixed Gibbs sampling will be studied. This consists of a change in the update rule in (8): instead of drawing _all_ samples from (6) with one probability, there is a chance \(q_{\infty}=(1-q_{1})\) that the values are instead taken from a uniform distribution as  
\[p(\mathbf{x}_{j}^{(t+1)}=\omega|\theta)\sim U[0,1], \tag{13}\]  
such that \(\sum p(\mathbf{x}_{j}^{(t+1)}=\omega|\theta)=1\). This corresponds to setting \(\alpha=\infty\) in (6). Hence, the method acquires the name of mixed Gibbs sampling (MGS), and as long as \(q_{\infty}\) is chosen accordingly, the stalling problem is alleviated: if stuck in a local minima, there is a non-zero probability \(q_{\infty}\) that the detector performs a random walk to move away from the local solution. Unless otherwise stated, the mixing ratio value is set to \(q_{\infty}=\frac{1}{n}\) (as suggested in [23]), which is equivalent to performing one random walk per each block iteration on average. To further improve performance, the multiple restarts (MR) technique, as proposed in [23; 27], will also be contemplated. Due to the random nature of MGS, different instances of the algorithm may lead to different outputs, even when the input values are the same. Denote the maximum number of allowed restarts by \(R\). When \(R>1\), the output solution is the one yielding the lowest ML cost and since each of the restarts is independent of the others, a parallel computation of the various instances can be performed to decrease overall detection time. With the introduction of MR, the algorithm has now three distinct loop levels: \(R\) restarts, \(t\) block iterations and \(n\) sampling processes per block iteration. Thus, the method can become computationally demanding. However, when a close enough solution to optimal has already been found, additional iterations may be redundant. Hence, in order to limit complexity, a suitable stopping criterion can be defined. If the ML cost remains unchanged for two consecutive block iterations, stalling is said to have occurred [23]. Then, stalling mode is entered, where only a maximum number of iterations \(\theta_{s}\) more is allowed. If during stalling mode, a vector \(\mathbf{x}\) with lower ML cost is found, then stalling mode is left; otherwise, the algorithm terminates after \(\theta_{s}\) iterations. The parameter \(\theta_{s}\) is chosen as large if the stalled ML cost is high and chosen as small when the margin for improvement is narrow. If the algorithm does not stop as a result of the stalling mode, then the initially set maximum number of block iterations \(t_{\max}\) are performed. Under the considered model and when \(\mathbf{x}\) is error free, the ML cost is \(||\mathbf{n}||^{2}\), whose distribution is a chi-square with \(2N_{R}\) degrees of freedom, mean \(N_{R}\sigma_{n}^{2}\) and variance \(N_{R}\sigma_{n}^{4}\)[34] (Chapter 11). Thus, a normalized ML cost of solution vector \(\mathbf{x}\) can be characterized as [23]  
\[\phi(\mathbf{x})=\frac{||\mathbf{y}-q\mathbf{H}\mathbf{x}||^{2}-N\sigma_{n}^{ 2}}{\sqrt{N}\sigma_{n}^{2}}. \tag{14}\]  
The metric (14) can be seen as a a difference between ML cost and the mean of \(||\mathbf{n}||^{2}\) normalized by the standard deviation of \(||\mathbf{n}||^{2}\) (note that under the channel model in (1),\(\sigma_{n}^{2}=1\)). In addition to the ML cost, the stopping criteria \(\theta_{s}\) should also take into account the size of the QAM constellation.