0
$\begingroup$

Gaussian distribution on lattices generally seems esoteric (at least for me, for now). My question is:

Does Gaussian distribution on a lattice mean to add a Gaussian noise on a single point of a lattice (or its span) or adding Gaussian noise on all points of a lattice?

When we are reading a paper,

  • in some part of the paper seems that authors consider a single point of a lattice (or its span) and then mount a Gaussian noise on that point. As the authors use some lemmas or theorems which say that if you sample a point far enough from the center, then the probability of that sampling is exponentially small.
  • On the other hand, sometime it is emphasized that when we add Gaussian noises, the shape of the lattice will be like a flat page, I mean close to uniform distribution.

Do I confuse two distinct concepts?

An image of [Oded Regev, Noah Stephens-Davidowitz. "An Inequality for Gaussians on Lattices," In SIAM Journal On Discrete Mathematics, Vol 31, No 2, 2017. arXiv:1502.04796v3]:


enter image description here


$\endgroup$

1 Answer 1

1
$\begingroup$

The excerpt looks pretty clear to me, so I'm not sure this will help, but let's try with a slightly different perspective.

If we formulate things in terms of lattices as opposed to lattice cosets, and if we consider discrete Gaussian distributions with arbitrary center, the definition is as follows: the discrete Gaussian distribution $D_{L,s,\mathbf{c}}$ on a full-rank lattice $L\subset\mathbb{R}^n$ with parameter $s$ and center $\mathbf{c}\in\mathbb{R}^n$ is the unique probability distribution on $L$ that selects the lattice point $\mathbf{x}\in L$ with probability proportional to $\rho_s(\mathbf{x}-\mathbf{c}) = \exp(-\pi\|\mathbf{x}-\mathbf{c}\|^2/s^2)$ (sometimes a different convention is used for the parameter $s$ that makes it closer to a standard deviation, but that's besides the point here). Clearly, this distribution is not at all close to uniform (and in fact, there is not such thing as a uniform distribution on an infinite countable set like $L$ to begin with).

On the other hand, if we have two lattices $L' \subset L$ of the same rank, then one can look at the distribution $D_{L,s,\mathbf{c}}$ modulo the sublattice $L'$ (in other words, we identify two lattice points in $L$ if their difference is in $L'$). This is a well-defined distribution on the finite quotient set $L/L'$. It only depends on the center $\mathbf{c}$ up to translation by a vector of $L'$, so one could even see $\mathbf{c}\mapsto D_{L,s,\mathbf{c}}$ as an $L'$-periodic function from $\mathbf{R}^n$ to the (affine) space of probability distributions on $L/L'$.

Now if $s$ is large enough (specifically, larger than the smoothing parameter of $L'$), then $D_{L,s,\mathbf{c}}$ becomes statistically close to the uniform distribution, and it particular it becomes essentially independent of the chosen center $\mathbf{c}$.

(This is a discrete version of the result that a continuous normal distribution modulo $L'$ with large enough parameter and arbitrary center induces a distribution close to uniform on the compact space $\mathbf{R}^n/L'$.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.