Optimized Markov Chain Monte Carlo for Signal Detection in MIMO Systems: An Analysis of the Stationary Distribution and Mixing Time

We introduce an optimized Markov chain Monte Carlo (MCMC) technique for solving integer least-squares (ILS) problems, which include maximum likelihood (ML) detection in multiple-input multiple-output (MIMO) systems. Two factors contribute to its speed of finding the optimal solution: the probability of encountering the optimal solution when the Markov chain has converged to the stationary distribution, and the mixing time of the MCMC detector. First, we compute the optimal "temperature" parameter value, so that once the Markov chain has mixed to its stationary distribution, there is a polynomially small probability ( 1/poly(N), instead of exponentially small) of encountering the optimal solution, where N is the system dimension. This temperature is shown to be O(√{SNR}/ln(N)), where SNR > 2ln(N) is the SNR. Second, we study the mixing time of the underlying Markov chain of the MCMC detector. We find that, the mixing time is closely related to whether there is a local minimum in the ILS problem's lattice structure. For some lattices without local minima, the mixing time is independent of SNR, and grows polynomially in N. Conventional wisdom proposed to set temperature as the noise standard deviation, but our results show that, under such a temperature, the mixing time grows unbounded with SNR if the lattice has local minima. Our results suggest that, very often the temperature should instead be scaling at least as Ω(√{SNR}). Simulation results show that the optimized MCMC detector efficiently achieves approximately ML detection in MIMO systems having a huge number of transmit and receive dimensions. ; © 2014 IEEE. Manuscript received November 13, 2013; revised March 31, 2014 and June 09, 2014; accepted June 18, 2014. Date of publication July 01, 2014; date of current version August 07, 2014. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Tongtong Li. The work of B. Hassibi was supported in part by the National Science Foundation under grants ...