{'fraction_non_alphanumeric': 0.03931890556963671, 'fraction_numerical': 0.013257945018522128, 'mean_word_length': 4.105507631055076, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Near-Optimal Detection in MIMO Systems using Gibbs Sampling

In this paper we study a Markov Chain Monte Carlo (MCMC) Gibbs sampler for solving the integer least-squares problem. In digital communication the problem is equivalent to performing Maximum Likelihood (ML) detection in Multiple-Input Multiple-Output (MIMO) systems. While the use of MCMC methods for such problems has already been proposed, our method is novel in that we optimize the"temperature"parameter so that in steady state, i.e. after the Markov chain has mixed, there is only polynomially (rather than exponentially) small probability of encountering the optimal solution. More precisely, we obtain the largest value of the temperature parameter for this to occur, since the higher the temperature, the faster the mixing. This is in contrast to simulated annealing techniques where, rather than being held fixed, the temperature parameter is tended to zero. Simulations suggest that the resulting Gibbs sampler provides a computationally efficient way of achieving approximative ML detection in MIMO systems having a huge number of transmit and receive dimensions. In fact, they further suggest that the Markov chain is rapidly mixing. Thus, it has been observed that even in cases were ML detection using, e.g. sphere decoding becomes infeasible, the Gibbs sampler can still offer a near-optimal solution using much less computations.


I. INTRODUCTION
The problem of performing Maximum Likelihood (ML) decoding in digital communication has gained much attention over the years. One method to obtain the ML solution is Sphere Decoding (SD) [1]- [5]. Over a wide range of Signal-to-Noise Ratios (SNR)s the average complexity of SD is significantly smaller than exhaustive search detectors, but in worst case the complexity is still exponential [6]. Thus, in scenarios with poor SNR or in Multiple-Input Multiple-Output (MIMO) systems with huge transmit and receive dimensions, even SD can be infeasible. A way to overcome this problem is to use approximate Markov Chain Monte Carlo (MCMC) detectors instead, which asymptotically can provide the optimal solution, [7], [8]. Gibbs sampling (also known as Glauber dynamics) is one MCMC method, which is used for sampling from distributions of multiple dimensions. The Gibbs sampler has among others been proposed for detection purposes in wireless communication in [9]- [12] (see also the references therein). The scope of this paper is to describe and analyse a new way of solving the integer least-squares problem using MCMC. It will be shown that the method can be used for achieving a near-optimal and computationally efficient solution of the problem, even for systems having a huge dimension.
The paper is organized as follows; In Section II we present the system model that will be used throughout the paper. The MCMC method is described in Section III and in Section IV we analyse the probability of error for the ML detector. Section V treats the optimal selection of the temperature parameter α, while the simulation results are given in Section VI and some concluding remarks are found in Section VII.

II. SYSTEM MODEL
We consider a real-valued block-fading MIMO antenna system, with N transmit and N receive dimensions, with know channel coefficients. 1 The received signal y ∈ R N can be expressed as where s ∈ Ω N is the transmitted signal, and Ω denotes the constellation set. To simplify the derivations in the paper we will assume that Ω = {±1}. υ ∈ R N is the noise vector where each entry is Gaussian N (0, 1) and independent identically distributed (i.i.d.), and H ∈ R N ×N denotes the channel matrix with i.i.d. N (0, 1) entries. The normalization in (1) guarantees that SNR represents the signal-to-noise ratio per receive dimension (which we define as the ratio of the total transmit energy per channel use divided by the per-component noise variance as described in among others [5]). As explained further below, for analysis purposes we will focus on the regime where SNR > 2 ln(N ), in order to get the probability of error of the ML detector to go to zero. Further, in our analysis, without loss of generality, we will assume that the all minus one vector was transmitted, s = −1. Therefore We are considering a minimization of the average error probability P (e) P (ŝ = s), which is obtained by performing Maximum Likelihood Sequence Detection (here simply referred to as ML detection) given byŝ

III. GIBBS SAMPLING
One way of solving the optimization problem given in (3) is by using Markov Chain Monte Carlo (MCMC) simulations, which asymptotically converge to the optimal solution [13]. More specifically, the MCMC detector we investigate here is the Gibbs sampler, which computes the conditional probability of each symbol in the constellation set at the jth index in the estimated symbol vector. This conditional probability is obtained by keeping the j − 1 other values in the estimated symbol vector fixed. Thus, in kth iteration the probability of the jth symbol adopts the value ω, is given as wheres T j|ω ŝ (k) and where we for simplicity have introduced θ = ŝ (k−1) , y, H . 2 α represents a tunable positive parameter which controls the mixing time of the Markov chain, this parameter is also sometimes called the "temperature". The larger α is the faster the mixing time of the Markov chain will be, but as we will show in the paper, there is an upper limit on α, in order to ensure that the probability of finding the optimal solution in steady state is not exponentially small. The MCMC method will with probability p ŝ (k) j = ω |θ keep ω at the j'th index in estimated symbol vector, and compute conditional probability the (j + 1)th index in a similar fashion. We define one iteration of the Gibbs sampler as a randomly-ordered update of all the j = {1, . . . , N T } indices in the estimated symbol vectorŝ. 3 The initialization of the symbol vectorŝ (0) can either be chosen randomly or, alternatively, e.g. the zero-forcing solution can be used.

A. Complexity of the Gibbs sampler
The conditional probability for the j'th symbol in (4) can be computed efficiently by reusing the result obtained for the j − 1'th symbol, when we evaluate y − SNR/N Hs j|ω 2 . Since we are only changing the j'th symbol in the symbol vector, the difference d j y − SNR/N Hs j|ω can be expressed as where ∆s j|ω s j|ω . Thus, the computation of conditional probability of certain symbol in the j'th position costs 2N operations, where we define an operation as a Multiply and Accumulate (MAC) instruction. 4 This leads to a complexity of O 2N 2 [|Ω| − 1] operations per iteration. For further details on the implementation of the Gibbs sampler see [14].

IV. PROBABILITY OF ERROR
In this paper, we are interested in evaluating the performance of the aforementioned Gibbs sampler, compared to the ML solution. To ease our analysis, we will assume that the ML detector finds the correct transmitted vector. Before we derive the probability of error for the ML detector, we will state a lemma which we will make repeated use of.
Proof: See Appendix VIII-A for a detailed proof.
Assuming that the vector s = −1 was transmitted, the ML detector will make an error if there exists a vector s = −1 such that In other words, for some s = −1, which can be formulated as for some δ = 0. Note that in the above equation δ is a vector of zeros and −1's. Now using the union bound We will use the Chernoff bound to bound the quantity inside the summation. Thus, where β ≥ 0 is the Chernoff parameter, and where we have used Lemma IV.1 with η = −β and The optimal value for β is 1 4 , which yields the tightest bound Note that this depends only on δ 2 , the number of nonzero entries in δ. Plugging this into the union bound yields Let us first look at the linear (i.e., i proportional to N ) terms in the above sum. Thus, where H(·) is entropy in "nats". Clearly, if lim N →∞ SNR = ∞, then the linear terms go to zero (superexponentially fast). Let us now look at the sublinear terms. In particular, let is look at i = 1: Clearly, to have this term go to zero, we require that SNR > 2 ln N . A similar argument shows that all other sublinear terms also go to zero, and so. 5 Lemma IV.2 (SNR scaling). If SNR > 2 ln N , then P e → 0 as N → ∞.

V. COMPUTING THE OPTIMAL α
Assuming that the vector s = −1 has been transmitted, the probability of finding this solution after the Markov chain has mixed is simply π −1 , the steady-state probability of being in the all −1 state. Clearly, if this probability is exponentially small, it will take exponentially long for the Gibbs sampler to find it. We will therefore insist that the mean of π −1 be only polynomially small.

A. Mean of π −1
This calculation has a lot in common with the one given in Section IV. Note that the steady state value of π −1 is simply where δ is a vector of zeros and ones and the summations (over s and δ) are over 2 n terms.

Now, by Jensen's inequality
In (12d) we have used Lemma IV.1 and in (12e) we have defined β 4SNR 1 α 2 (1 − 1 α 2 ). While it is possible to focus on the linear and sublinear terms in the above summation separately, to give conditions for E {π −1 } to have the form of 1/poly(N ), we will be interested in the exact exponent and so will need a more accurate estimate. To do this we shall use saddle point integration. Note that where again H(·) represents the entropy in "nats". And so the summation in the denominator of (12e) can be approximated as a Stieltjes integral: For large N , this is a saddle point integral and can be approximated by the formula where x 0 , is the saddle point of f (·), i.e.,f ′ (x 0 ) = 0. In our case, In general, it is not possible to solve for f ′ (x 0 ) = 0 in closed form. However, in our case, if we assume that β = 4SNR 1 α 2 (1 − 1 α 2 ) ≫ 1 (which is true since the SNR grows at least logarithmically), then it is not too hard to verify that the saddle point is given by and further plugging Replacing these into the saddle point expression in (14) show that We want E {π −1 } to behave as 1 N ζ and according to (12) this means that we want the expression in (17) to behave as N ζ . Let us take Solving for β yields Incidentally, this choice of β yields e − β 4 ≈ 1 √ N , and so we have the following result. Lemma V.1 (Mean of π −1 ). If α is chosen such that

B. Value of α
Note that from (12e) it is clear that the larger β is, the larger π −1 is. Therefore, the range of α that gives a polynomially small probability to π −1 is It can be shown that in the regime, SNR > 2 ln N , the above quadratic inequality in α has two positive real solutions, α + ≥ α − , and that the inequality holds for all α ∈ [α − , α + ]. We know that, the larger α is, the faster the Markov chain mixes. 6 Therefore it is reasonable that we choose the largest permissible value for α, i.e., α + . Figures 1 and 2 show the values of α + and α − as a function of SNR for systems with N = 10 and N = 50, when we have ζ = 1/ ln N .

C. Mixing time of Markov Chain
One open question is whether the Markov chain is rapidly mixing when using the strategy above for choosing α. This is something we are currently investigating, and the simulations presented in Section VI seem to indicate that this is the case. Furthermore, the simulations also suggest that the computed value of α is very close to the optimal choice, even in the case where the condition SNR > 2 ln(N ) is not satisfied.

VI. SIMULATION RESULTS
In this section we present simulation results for a MIMO N × N system with a full square channel matrix containing i.i.d. Gaussian entries. In Fig. 3 and Fig. 4 the Bit Error Rate (BER) of the Gibbs sampler, initialized with a random s, has been evaluated as a function of the number of iterations in a 10 × 10 system using a variety of α values. Thereby, we can inspect how the parameter α affects the convergence rate of the Gibbs sampler. The performance of the Maximum Likelihood (ML), the Zero-Forcing (ZF), and the Linear Minimum Mean Square Error (LMMSE) detector has also been plotted, to ease the comparison of the Gibbs sampler with these. It is seen that the Gibbs sampler outperforms both the ZF and the LMMSE detector after only a  few iterations in all the presented simulations, when the tuning parameter α is chosen properly. Furthermore, it is observed that the parameter α has a huge influence on the convergence rate and that the Gibbs sampler converges toward the ML solution as a function of the iterations. 7 The optimal value of α (in terms of convergence rate) is quite close to the theoretical values from Fig. 1 of α + = 2.7 and α + = 4.6 at SNR's at 10 and 14dB, respectively. It is also observed that the performance of the Gibbs sampler is significantly deteriorated if the temperature parameter is chosen based on the SNR (and thereby on the noise variance), such that α = σ 1/SNR. Thus, the latter strategy is clearly not a wise choice. Figure 5 shows the BER performance for the MCMC detector for fixed number of iterations, k = 100. From the figure we see that the SNR has a significant influence on the optimal choice of α given a fixed number of iterations. The performance of the Gibbs sampler is also shown for a 50 × 50 system, which represents a ML decoding problem of huge complexity where an exhaustive search would require 2 50 ≈ 10 15 evaluations. For this problem even the sphere decoder has an enormous complexity under moderate SNR. 8 Therefore, it has not been possible to simulate the performance of this decoder within a reasonable time and we have therefore "cheated" a little by initializing the radius of the sphere to the minimum of either the norm of the transmitted symbol vector or the solution found by the Gibbs sampler. This has been done in order to evaluate the BER performance of the optimal detector. Figure 6 shows the BER curve as a function of the iteration number, while Figure 7 illustrates the BER curve vs. the SNR. From Figure 6 we see that there is a quite good correspondence between the simulated α and the theoretical value α + = 2.6 obtained from Figure 2. The average complexity (MAC pr. symbol vector) of the Gibbs sampler having a BER performance comparable with the ML detector is shown in Table I. The SD has been included   10.0 · 10 3 1.7 · 10 3 1.5 · 10 3 50 GS 7.6 · 10 5 9.5 · 10 5 10.6 · 10 5 SD ≫ 1.9 · 10 9 ≫ 1.9 · 10 9 37.7 · 10 5 as a reference. 9 It is observed that the complexity of the Gibbs sampler is not affected by the SNR as much as the SD.

VII. CONCLUSION
In this paper we considered solving the integer least-squares problem using Monte Carlo Markov Chain Gibbs sampling. The novelty of the proposed MCMC method is that, unlike simulated annealing techniques, we have a fixed temperature parameter in all the iterations, with the property that after the Markov chain has mixed, the probability of encountering the optimal solution is only polynomial small (i.e. not exponentially small). We further compute the optimal (here largest) value of the temperature parameter that guarantees this. Simulation results indicate the sensitivity of the method to the choice of the temperature parameter and show that our computed value gives a very good approximation to its optimal value. Investigating whether the Markov chain mixes in polynomial time for this choice of temperature parameter is currently under investigation.