A Caltech Library Service

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

Hassibi, Babak and Hansen, Morten and Dimakis, Alexandros G. and Alshamary, Haider Ali Jasim and Xu, Weiyu (2014) Optimized Markov Chain Monte Carlo for Signal Detection in MIMO Systems: An Analysis of the Stationary Distribution and Mixing Time. IEEE Transactions on Signal Processing, 62 (17). pp. 4436-4450. ISSN 1053-587X.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© 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 CCF-0729303, CNS-0932428 and CCF-1018927, by the Office of Naval Research under the MURI grant N00014-08-0747, and by King Abdulaziz University. This work of A. G. Dimakis has been supported by NSF Grants CCF 1344179, CCF 1344364 and research gifts by Microsoft and Google. The work of W. Xu was partially supported by a grant from the Simons Foundation (318608 to W. Xu). H. A. J. Alshamary is supported by a scholarship from the Higher Committee of Education Development in Iraq. Part of this paper was presented in the IEEE Global Communications Conference 2009 [1], and the Fifty-First IEEE Conference on Decision and Control 2012 [2].
Funding AgencyGrant Number
Office of Naval Research (ONR) Multidisciplinary University Research Initiative (MURI)N00014-08-0747
King Abdulaziz UniversityUNSPECIFIED
NSFCCF 1344179
NSFCCF 1344364
Simons Foundation318608
Higher Committee of Education Development in Iraq scholarshipUNSPECIFIED
Subject Keywords:MIMO; Markov Chain Monte Carlo algorithm; mixing time; integer least squares problem; wireless communication
Issue or Number:17
Record Number:CaltechAUTHORS:20140918-142934393
Persistent URL:
Official Citation:Hassibi, B.; Hansen, M.; Dimakis, AG.; Alshamary, H.AJ.; Weiyu Xu, "Optimized Markov Chain Monte Carlo for Signal Detection in MIMO Systems: An Analysis of the Stationary Distribution and Mixing Time," Signal Processing, IEEE Transactions on , vol.62, no.17, pp.4436,4450, Sept.1, 2014 doi: 10.1109/TSP.2014.2334558
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:49834
Deposited By: Ruth Sustaita
Deposited On:18 Sep 2014 21:49
Last Modified:03 Oct 2019 07:17

Repository Staff Only: item control page