{
  "id": "1501.05757",
  "version": "v1",
  "published": "2015-01-23T09:58:20.000Z",
  "updated": "2015-01-23T09:58:20.000Z",
  "title": "Independent Metropolis-Hastings-Klein Algorithm for Lattice Gaussian Sampling",
  "authors": [
    "Zheng Wang",
    "Cong Ling"
  ],
  "categories": [
    "cs.IT",
    "math.IT"
  ],
  "abstract": "Sampling from the lattice Gaussian distribution is emerging as an important problem in coding and cryptography. In this paper, a Markov chain Monte Carlo (MCMC) algorithm referred to as the independent Metropolis-Hastings-Klein (MHK) algorithm is proposed for lattice Gaussian sampling, which overcomes the restriction on the standard deviation confronted by the Klein algorithm. It is proven that the Markov chain arising from the proposed MHK algorithm is uniformly ergodic, namely, it converges to the stationary distribution exponentially fast. Moreover, the rate of convergence is explicitly calculated in terms of the theta series, making it possible to predict the mixing time of the underlying Markov chain.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-01-23T09:58:20.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "lattice gaussian sampling",
      "independent metropolis-hastings-klein algorithm",
      "markov chain monte carlo",
      "stationary distribution exponentially fast",
      "lattice gaussian distribution"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150105757W"
    }
  }
}