2017/04/09 by Zheng Wang, Wang, Zheng, Cong Ling +1
Computer Science · Mathematics · #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #Information Theory (cs.IT) #Markov Chains and Monte Carlo Methods #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.1704.02673
openalex publication_date 2017/04/09 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28
Sampling from the lattice Gaussian distribution plays an important role in various research fields. In this paper, the Markov chain Monte Carlo (MCMC)-based sampling technique is advanced in several fronts. Firstly, the spectral gap for the independent Metropolis-Hastings-Klein (MHK) algorithm is derived, which is then extended to Peikert's algorithm and rejection sampling; we show that independent MHK exhibits faster convergence. Then, the performance of bounded distance decoding using MCMC is analyzed, revealing a flexible trade-off between the decoding radius and complexity. MCMC is further applied to trapdoor sampling, again offering a trade-off between security and complexity. Finally, the independent multiple-try Metropolis-Klein (MTMK) algorithm is proposed to enhance the convergence rate. The proposed algorithms allow parallel implementation, which is beneficial for practical applications.