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:
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') # needs sage.plot 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
, oran 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 # needs sage.symbolic 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: # needs sage.symbolic ....: 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: # needs sage.symbolic ....: 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 # needs sage.symbolic 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() # needs sage.symbolic 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: mean_L = sum(L) / len(L) sage: norm(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: mean_L = sum(L) / len(L) # long time sage: norm(mean_L.n() - D.c) < 0.25 # long time True
- property 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\) norNone
.sigma
- ifprecision
isNone
then the precision ofsigma
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
- property 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