Journal article
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, Vol.62(17), pp.4436-4450
09/01/2014
DOI: 10.1109/TSP.2014.2334558
Abstract
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.
Details
- Title: Subtitle
- Optimized Markov Chain Monte Carlo for Signal Detection in MIMO Systems: An Analysis of the Stationary Distribution and Mixing Time
- Creators
- Babak Hassibi - California Institute of TechnologyMorten Hansen - Renesas Mobile Corp., Copenhagen, DenmarkAlexandros G Dimakis - University of Texas at AustinHaider Ali Jasim Alshamary - University of IowaWeiyu Xu - University of Iowa
- Resource Type
- Journal article
- Publication Details
- IEEE transactions on signal processing, Vol.62(17), pp.4436-4450
- DOI
- 10.1109/TSP.2014.2334558
- ISSN
- 1053-587X
- eISSN
- 1941-0476
- Publisher
- IEEE
- Grant note
- CCF-0729303; CNS-0932428; CCF-1018927 / National Science Foundation; National Science Foundation (10.13039/100000001) 318608 / Simons Foundation; Simons Foundation King Abdulaziz University; King Abdulaziz University (10.13039/501100004054) CCF 1344179; CCF 1344364 / NSF; NSF N00014-08¿0747 / Office of Naval Research; Office of Naval Research (10.13039/100000006) Higher Committee of Education Development in Iraq; Higher Committee of Education Development in Iraq Microsoft and Google; Microsoft and Google
- Language
- English
- Date published
- 09/01/2014
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984197412802771
Metrics
6 Record Views