CaltechAUTHORS
  A Caltech Library Service

On the Mixing Time of Markov Chain Monte Carlo for Integer Least-Square Problems

Xu, Weiyu and Dimakis, Alexandros G. and Hassibi, Babak (2012) On the Mixing Time of Markov Chain Monte Carlo for Integer Least-Square Problems. In: 2012 IEEE 51st Annual Conference on Decision and Control (CDC),. IEEE , Piscataway, NJ, pp. 2545-2550. http://resolver.caltech.edu/CaltechAUTHORS:20150126-074841944

[img] PDF - Submitted Version
See Usage Policy.

157Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150126-074841944

Abstract

In this paper, we study the mixing time of Markov Chain Monte Carlo (MCMC) for integer least-square (LS) optimization problems. It is found that the mixing time of MCMC for integer LS problems depends on the structure of the underlying lattice. More specifically, the mixing time of MCMC is closely related to whether there is a local minimum in the lattice structure. For some lattices, the mixing time of the Markov chain is independent of the signal-to-noise ratio (SNR) and grows polynomially in the problem dimension; while for some lattices, the mixing time grows unboundedly as SNR grows. Both theoretical and empirical results suggest that to ensure fast mixing, the temperature for MCMC should often grow positively as the SNR increases. We also derive the probability that there exist local minima in an integer least-square problem, which can be as high as 1/3 - 1/√5 + (2 arctan(√(5/3))/(√5Π).


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/CDC.2012.6425890 DOIArticle
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6425890PublisherArticle
http://arxiv.org/abs/1203.2213v1arXivDiscussion Paper
Additional Information:©2012 IEEE.
Record Number:CaltechAUTHORS:20150126-074841944
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150126-074841944
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54052
Collection:CaltechAUTHORS
Deposited By: Shirley Slattery
Deposited On:26 Jan 2015 23:59
Last Modified:26 Jan 2015 23:59

Repository Staff Only: item control page