On the Geometric Ergodicity of Metropolis-Hastings Algorithms for Lattice Gaussian Sampling

Zheng Wang; Cong Ling

Paper 2019/666

On the Geometric Ergodicity of Metropolis-Hastings Algorithms for Lattice Gaussian Sampling

Zheng Wang and Cong Ling

Abstract

Sampling from the lattice Gaussian distribution has emerged as an important problem in coding, decoding and cryptography. In this paper, the classic Metropolis-Hastings (MH) algorithm in Markov chain Monte Carlo (MCMC) methods is adopted for lattice Gaussian sampling. Two MH-based algorithms are proposed, which overcome the limitation of Klein's algorithm. The first one, referred to as the independent Metropolis-Hastings-Klein (MHK) algorithm, establishes a Markov chain via an independent proposal distribution. We show that the Markov chain arising from this independent MHK algorithm is uniformly ergodic, namely, it converges to the stationary distribution exponentially fast regardless of the initial state. Moreover, the rate of convergence is analyzed in terms of the theta series, leading to predictable mixing time. A symmetric Metropolis-Klein (SMK) algorithm is also proposed, which is proven to be geometrically ergodic.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. IEEE Trans. Inform. Theory, vol. 64, no. 2, pp. 738–751, Feb. 2018.
Keywords: Lattice Gaussian sampling MCMC methods Metropolis-Hastings algorithm closest vector problem.
Contact author(s): c ling @ imperial ac uk
History: 2019-06-06: received
Short URL: https://ia.cr/2019/666
License: CC BY

BibTeX

@misc{cryptoeprint:2019/666,
      author = {Zheng Wang and Cong Ling},
      title = {On the Geometric Ergodicity of Metropolis-Hastings Algorithms for Lattice Gaussian Sampling},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/666},
      year = {2019},
      url = {https://eprint.iacr.org/2019/666}
}