Discrete Gaussian Samplers over Lattices

This file implements oracles which return samples from a lattice following a discrete Gaussian distribution. That is, if \(σ\) is big enough relative to the provided basis, then vectors are returned with a probability proportional to \(\exp(-|x-c|_2^2/(2σ^2))\). More precisely lattice vectors in \(x ∈ Λ\) are returned with probability:

\(\exp(-|x-c|_2^2/(2σ²))/(∑_{x ∈ Λ} \exp(-|x|_2^2/(2σ²)))\)

AUTHORS:

  • Martin Albrecht (2014-06-28): initial version

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^10, 3.0)
sage: D(), D(), D()  # random
((3, 0, -5, 0, -1, -3, 3, 3, -7, 2), (4, 0, 1, -2, -4, -4, 4, 0, 1, -4), (-3, 0, 4, 5, 0, 1, 3, 2, 0, -1))
sage: a = D()
sage: a.parent()
Ambient free module of rank 10 over the principal ideal domain Integer Ring
class sage.stats.distributions.discrete_gaussian_lattice.DiscreteGaussianDistributionLatticeSampler(B, sigma=1, c=None, precision=None)

Bases: sage.structure.sage_object.SageObject

GPV sampler for Discrete Gaussians over Lattices.

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^10, 3.0); D
Discrete Gaussian sampler with σ = 3.000000, c=(0, 0, 0, 0, 0, 0, 0, 0, 0, 0) over lattice with basis

[1 0 0 0 0 0 0 0 0 0]
[0 1 0 0 0 0 0 0 0 0]
[0 0 1 0 0 0 0 0 0 0]
[0 0 0 1 0 0 0 0 0 0]
[0 0 0 0 1 0 0 0 0 0]
[0 0 0 0 0 1 0 0 0 0]
[0 0 0 0 0 0 1 0 0 0]
[0 0 0 0 0 0 0 1 0 0]
[0 0 0 0 0 0 0 0 1 0]
[0 0 0 0 0 0 0 0 0 1]

We plot a histogram:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: import warnings
sage: warnings.simplefilter('ignore', UserWarning)
sage: D = DiscreteGaussianDistributionLatticeSampler(identity_matrix(2), 3.0)
sage: S = [D() for _ in range(2^12)]
sage: l = [vector(v.list() + [S.count(v)]) for v in set(S)]
sage: list_plot3d(l, point_list=True, interpolation='nn')
Graphics3d Object

REFERENCES:

__init__(B, sigma=1, c=None, precision=None)

Construct a discrete Gaussian sampler over the lattice \(Λ(B)\) with parameter sigma and center \(c\).

INPUT:

  • B – a basis for the lattice, one of the following:

    • an integer matrix,

    • an object with a matrix() method, e.g. ZZ^n, or

    • an object where matrix(B) succeeds, e.g. a list of vectors.

  • sigma – Gaussian parameter \(σ>0\).

  • c – center \(c\), any vector in \(\ZZ^n\) is supported, but \(c ∈ Λ(B)\) is faster.

  • precision – bit precision \(≥ 53\).

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: n = 2; sigma = 3.0
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^n, sigma)
sage: f = D.f
sage: c = D._normalisation_factor_zz(); c
56.2162803067524

sage: from collections import defaultdict
sage: counter = defaultdict(Integer)
sage: m = 0
sage: def add_samples(i):
....:     global counter, m
....:     for _ in range(i):
....:         counter[D()] += 1
....:         m += 1

sage: v = vector(ZZ, n, (-3, -3))
sage: v.set_immutable()
sage: while v not in counter: add_samples(1000)
sage: while abs(m*f(v)*1.0/c/counter[v] - 1.0) >= 0.1: add_samples(1000)

sage: v = vector(ZZ, n, (0, 0))
sage: v.set_immutable()
sage: while v not in counter: add_samples(1000)
sage: while abs(m*f(v)*1.0/c/counter[v] - 1.0) >= 0.1: add_samples(1000)

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: qf = QuadraticForm(matrix(3, [2, 1, 1,  1, 2, 1,  1, 1, 2]))
sage: D = DiscreteGaussianDistributionLatticeSampler(qf, 3.0); D
Discrete Gaussian sampler with σ = 3.000000, c=(0, 0, 0) over lattice with basis

[2 1 1]
[1 2 1]
[1 1 2]
sage: D().parent() is D.c.parent()
True
__call__()

Return a new sample.

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1,0,0))
sage: L = [D() for _ in range(2^12)]
sage: abs(mean(L).n() - D.c) < 0.25
True

sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1/2,0,0))
sage: L = [D() for _ in range(2^12)]  # long time
sage: abs(mean(L).n() - D.c) < 0.25   # long time
True
c

Center \(c\).

Samples from this sampler will be centered at \(c\).

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1,0,0)); D
Discrete Gaussian sampler with σ = 3.000000, c=(1, 0, 0) over lattice with basis

[1 0 0]
[0 1 0]
[0 0 1]

sage: D.c
(1, 0, 0)
static compute_precision(precision, sigma)

Compute precision to use.

INPUT:

  • precision - an integer \(> 53\) nor None.

  • sigma - if precision is None then the precision of sigma is used.

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(100, RR(3))
100
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(100, RealField(200)(3))
100
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(100, 3)
100
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(None, RR(3))
53
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(None, RealField(200)(3))
200
sage: DiscreteGaussianDistributionLatticeSampler.compute_precision(None, 3)
53
sigma

Gaussian parameter \(σ\).

Samples from this sampler will have expected norm \(\sqrt{n}σ\) where \(n\) is the dimension of the lattice.

EXAMPLES:

sage: from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler
sage: D = DiscreteGaussianDistributionLatticeSampler(ZZ^3, 3.0, c=(1,0,0))
sage: D.sigma
3.00000000000000