Downloads & Free Reading Options - Results

Sampling from the lattice Gaussian distribution is an efficient way for solving the closest vector problem (CVP) in lattice decoding. In this paper, decoding by MCMC-based lattice Gaussian sampling is investigated in full details. First of all, the spectral gap of the transition matrix of the Markov chain induced by the independent Metropolis-Hastings-Klein (MHK) algorithm is derived, dictating an exponential convergence rate to the target lattice Gaussian distribution. Then, the decoding complexity of CVP is derived as $O(e^{d^2(\Lambda, \mathbf{c})/\min_i^2\|\widehat{\mathbf{b}}_i\|})$, where $d(\Lambda, \mathbf{c})$ represents the Euclidean distance between the query point $\mathbf{c}$ and the lattice $\Lambda$, and $\mathbf{\widehat{b}}_i$ is the $i$th Gram-Schmidt vector of the lattice basis $\mathbf{B}$. Furthermore, the decoding radius from the perspective of bounded distance decoding (BDD) given a fixed number of Markov moves $t$ is also derived, revealing a flexible trade-off between the decoding performance and complexity. Finally, by taking advantages of $k$ trial samples from the proposal distribution, the independent multiple-try Metropolis-Klein (MTMK) algorithm is proposed to further enhance the exponential convergence rate. By adjusting $k$, the independent MTMK sampler enjoys a flexible decoding performance, where the independent MHK algorithm is just a case with $k=1$. Additionally, the proposed decoding allows a fully parallel implementation, which is beneficial for the practical interest.