An MCMC Method to Sample from Lattice Distributions

2021/01/16 by George, Anand Jerry, Kashyap, Navin
#Computation (stat.CO) #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2101.06453

Abstract

We introduce a Markov Chain Monte Carlo (MCMC) algorithm to generate samples from probability distributions supported on a d-dimensional lattice Λ= Bℤ^d, where B is a full-rank matrix. Specifically, we consider lattice distributions P_Λ in which the probability at a lattice point is proportional to a given probability density function, f, evaluated at that point. To generate samples from P_Λ, it suffices to draw samples from a pull-back measure P_ℤ^d defined on the integer lattice. The probability of an integer lattice point under P_ℤ^d is proportional to the density function π= |det(B)|f∘ B. The algorithm we present in this paper for sampling from P_ℤ^d is based on the Metropolis-Hastings framework. In particular, we use π as the proposal distribution and calculate the Metropolis-Hastings acceptance ratio for a well-chosen target distribution. We can use any method, denoted by ALG, that ideally draws samples from the probability density π, to generate a proposed state. The target distribution is a piecewise sigmoidal distribution, chosen such that the coordinate-wise rounding of a sample drawn from the target distribution gives a sample from P_ℤ^d. When ALG is ideal, we show that our algorithm is uniformly ergodic if -log(π) satisfies a gradient Lipschitz condition.

Related

• Lattice Gaussian Sampling by Markov Chain Monte Carlo: Bounded Distance Decoding and Trapdoor Sampling
• Markov chain Monte Carlo Methods For Lattice Gaussian Sampling:Convergence Analysis and Enhancement
• A Common Derivation for Markov Chain Monte Carlo Algorithms with Tractable and Intractable Targets
• Multiple projection MCMC algorithms on submanifolds
• Coupled coarse graining and Markov Chain Monte Carlo for lattice systems