Near-Optimal Detection in MIMO Systems using Gibbs Sampling

Morten Hansen, Babak Hassibi, Georgios Alexandros Dimakis, Weiyu Xu

    Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

    470 Downloads (Pure)


    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 preforming 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.
    Original languageEnglish
    Title of host publicationGlobal Telecommunications Conference, 2009. GLOBECOM 2009. IEEE
    Publication date2009
    ISBN (Print)978-1-4244-4148-8
    Publication statusPublished - 2009
    Event2009 IEEE Global Telecommunications Conference - Honolulu, United States
    Duration: 30 Nov 20094 Dec 2009


    Conference2009 IEEE Global Telecommunications Conference
    Country/TerritoryUnited States
    Internet address

    Bibliographical note

    Copyright 2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.


    Dive into the research topics of 'Near-Optimal Detection in MIMO Systems using Gibbs Sampling'. Together they form a unique fingerprint.

    Cite this