Parametric Lattices Are Better Quantizers in Dimensions 13 and 14

arXiv:2411.19250 · cs.IT, math-ph, math.IT, math.MG, math.MP · Submitted 2024-11-28 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Parametric Lattices Are Better Quantizers in Dimensions 13 and 14".

Jane: Here's the gist of the paper. New lattice quantizers with lower normalized second moments than previously reported are constructed in 13 and 14 dimensions and conjectured to be optimal.

Tom: The paper presents new lattices in dimensions 13 and 14 that achieve lower normalized second moments than previously reported, combining numerical optimization with analytical optimization of families of lattices whose Voronoi regions are constructed exactly.

Jane: Lattice Construction Methods The new lattices are constructed from glued products of previously known lattices by scaling the component lattices and then optimizing the scale factors.

Tom: The work employs both numerical approximation methods and exact analytic ones.

Paper summary: Tom: So to summarize this paper, they claim these new lattice quantizers in dimensions thirteen and fourteen have lower normalized second moments than previously reported ones, and they conjecture that these are the optimal ones for those dimensions.

Jane: That sounds like a big claim because finding an optimal packing structure is usually incredibly hard; so what makes this construction different from just randomly searching for a better lattice?

Lu: The paper says their construction combines numerical optimization with an analytical optimization of families of lattices whose Voronoi regions are constructed exactly, which is how they systematically search for the best parameters.

Meng: So they’re not just guessing; they’re using this structure where the Voronoi regions are exact, which suggests a more rigorous way to find that lower second moment.

Lalam: And what makes these new lattices interesting is that they are built by gluing products of previously known lattices, scaling them up, and then optimizing those scale factors to get the best fit.

Tom: It’s about using this gluing idea to build a family of lattices, and then analytically optimizing the scale factors for those families in dimensions thirteen and fourteen.

Jane: So if this works out as they suggest, it means we have a concrete way to find better quantizers where we previously only had estimates or less structured methods.

Conclusion: Tom: Looking at the title, "Parametric Lattices Are Better Quantizers in Dimensions thirteen and fourteen" it points directly to the specific dimensions thirteen and fourteen where this better performance was found <ref:2411.19250#pg1,Parametric Lattices Are Better Quantizers in Dimensions 13 and 14>.

Jane: So what does this actually mean for us outside of just the math? It means that for these particular high dimensions, we have a more efficient way to represent or quantize data using lattices.

Lu: The implication is that for applications in those specific dimensions, we can expect better performance from the quantization process because the underlying structure is proven to be near optimal.

Meng: From an engineering standpoint, if this construction is robust and scalable, it could translate into faster or smaller models when we eventually use these lattice methods for things like compressed data representation.

Lalam: The paper suggests that by using this parametric lattice approach, we can find quantizers that are closer to the theoretical best in those dimensions than before.

Tom: So the authors Daniel Pook-Kolb, Erik Agrell, and Bruce Allen have put forward a method where they use gluing theory and optimization to construct these superior lattices for those specific dimensions.

Daniel Pook-Kolb, Erik Agrell, Bruce Allen

Max Planck Institute for Gravitational Physics · Chalmers University of Technology

cs.IT, math-ph, math.IT, math.MG, math.MP

Submitted: 2024-11-28

Updated: 2024-11-28

Comments: 16 pages, 7 figures

DOI: 10.1109/TIT.2026.3721285

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 82/100

The gist: New lattice quantizers with lower normalized second moments than previously reported are constructed in 13 and 14 dimensions and conjectured to be optimal.

Key concepts

Normalized Second Moments (NSMs)
These are a measure used to assess how well a lattice quantizer approximates the optimal structure. Lower NSMs indicate a better, more efficient approximation of the ideal lattice in that dimension.
Lattice Construction Methods
New lattices were built by combining known lattices through scaling and 'gluing' operations. This process involved defining product lattices as special cases and using gluing to connect a lattice to its dual, resulting in new structures between the original and its dual.
Optimality Condition
A lattice quantizer is considered optimal if its second moment matrix (U) is proportional to the identity matrix (In). The paper uses this condition, along with analyzing the Voronoi region's topological changes, to determine the best possible parameters for a lattice in each dimension.

Terminology

Summary

New lattice quantizers with lower normalized second moments than previously reported are constructed in 13 and 14 dimensions and conjectured to be optimal. p. 0

Where the paper says it

PREPRINT, NOVEMBER 28, 2024 1 Parametric Lattices Are Better Quantizers in Dimensions 13 and 14 Daniel Pook-Kolb, Erik Agrell, Fellow, IEEE, and Bruce Allen, Member, IEEE Abstract—New lattice quantizers with lower normalized second moments than previously reported are constructed in 13 and 14 dimensions and conjectured to be optimal. Our construction combines an initial numerical optimization with a subsequent analytical optimization of families of lattices, whose Voronoi regions are constructed exactly.

The paper presents new lattices in dimensions 13 and 14 that achieve lower normalized second moments than previously reported, combining numerical optimization with analytical optimization of families of lattices whose Voronoi regions are constructed exactly. p. 0
Where the paper says it

PREPRINT, NOVEMBER 28, 2024 1 Parametric Lattices Are Better Quantizers in Dimensions 13 and 14 Daniel Pook-Kolb, Erik Agrell, Fellow, IEEE, and Bruce Allen, Member, IEEE Abstract—New lattice quantizers with lower normalized second moments than previously reported are constructed in 13 and 14 dimensions and conjectured to be optimal. Our construction combines an initial numerical optimization with a subsequent analytical optimization of families of lattices, whose Voronoi regions are constructed exactly.

Lattice Construction Methods

The new lattices are constructed from glued products of previously known lattices by scaling the component lattices and then optimizing the scale factors. The work employs both numerical approximation methods and exact analytic ones. p. 0

Where the paper says it

We call such lattices, which are exact functions of a small number of real parameters, parametric lattices. The work reported here employs both numerical approximation methods and exact analytic ones.

The construction involves defining product lattices as a special case of a parametric lattice where the dimension is the sum of the dimensions of the component lattices. p. 1
Where the paper says it

, Lk the (possibly scaled) component lattices. It is a special case of a parametric lattice with k parameters a1, .

Gluing is used to interpolate between a lattice L and its dual L∗, creating a glued lattice L′ such that L ⊆ L′ ⊆ L∗. p. 1
Where the paper says it

It becomes especially useful when applied to product lattices, where it has led to two different 12- dimensional lattice quantizers with a lower NSM than the Coxeter–Todd lattice K12. Intuitively, gluing interpolates between a lattice L and its dual L ∗ , L ⊆ L ′ ⊆ L ∗ , (7) where L ′ is the glued lattice.

Optimization and Identification

The optimization process involves iteratively updating the generator matrix towards lower NSMs, guided by stochastic gradient descent. A heuristic method is proposed to identify the exact form of a lattice whose generator or Gram matrix is known only numerically by exploiting the regular structure where lattice points are arranged on separated, spherical shells. p. 3

Where the paper says it

Therefore, a heuristic method to identify the exact form of a lattice whose generator or Gram matrix is known only numerically was also proposed in [18]. It exploits the regular structure that almost all locally optimal lattices exhibit, specifically the arrangement of lattice points on a discrete set of separated, spherical shells.

The identification technique involves solving systems of equations derived from the theta images of the numerically found lattices. p. 0
Where the paper says it

That is the purpose of the present paper. First, the lattices found numerically in dimensions 13 and 14 are identified using the technique described in [18]: solving systems of equations derived from their theta images.

Optimality and Phase Analysis

The optimality of a lattice quantizer is related to its second moment matrix U being proportional to the n-dimensional identity matrix In. The analysis involves constructing the full Voronoi region up to symmetry and identifying the phase Pa where the Voronoi region has no topological changes. p. 2

Where the paper says it

PARAMETRIC VORONOI REGIONS We analyze lattices using the methods described in [13] with the optimizations in [22]. This is done by exactly constructing the full Voronoi region of the lattice up to symmetry.

The optimal parameters are determined via the common root of two polynomials of degree 14 (in dimension 13) and a root of a single polynomial of degree 15 (in dimension 14). p. 7
Where the paper says it

It has its minimum at the only root of G′ (a) in this phase. We define f(a 2 ) ≜ 3 − 9 14 a 67 7 G ′ (a) (40) and v ≜ a 2 to obtain a polynomial of degree 15 with rational coefficients, namely f(v) = 1 2 24 · 3 15 · 5 5 · 7 6 · 112 · 13 − 1018103123715692435v 15 + 17231830904837964816v 14 − 50384128456897156089v 13 − 1298484357790911467904v 12 + 18853052319918661538421v 11 − 134210060479957033956384v 10 + 618613960836724635966183v 9 − 1974707405188629201419472v 8 + 4363698900317368804089183v 7 − 6221111401101448657037232v 6 + 5275022790841652128092813v 5 − 813004897455917734617504v 4 − 3663147939360699042433089v 3 + 2857169704323149848334016v 2 − 1078908260599455294925179v + 167989606592059669887216 .

Results in Dimensions 13 and 14

In dimension 13, the optimal lattice is conjectured to be generated by B13(a) in (60), where [v2,0, v3,0] is the common root of the polynomials fB2 and fB3 closest to [1, 1]. In dimension 14, the conjectured optimal lattice quantizer is generated by B14(v0) in (23), where v0 is the second positive root of f(v) in (41). p. 0

Where the paper says it

In two dimensions, the optimal lattice quantizer is the hexagonal lattice [7] and in three dimensions it is the body-centered cubic lattice [8]. Together with these proven results, the lattices with the lowest known normalized second moments in dimensions 4–8, 12, 16, and 24 were listed in 1984 by Conway and Sloane [9] and conjectured optimal by the same authors in 1999 [1, p.

The resulting NSMs are conjectured to be lower than previously reported values. p. 8
Where the paper says it

The resulting NSM of G = 264643025208158502912098205658743146287 2 81 · 3 9 · 5 3 · 7 4 · 112 · 133 ≈ 0. 069 698 255 940 (47) is lower than all previously reported NSMs in 13 dimensions (most recently 0.

Voronoi Region Properties

The Voronoi region of the lattice (60) in phase B has 960,828,340 vertices and 5,454 facets in dimension 13. The kissing number for the lattice (60) is 98 when a = [a1 = a2 = a3]. p. 7

Where the paper says it

Under its automorphism group the individual number of classes of faces in dimensions 0 through 14 is, respectively, 747, 6 211, 24 871, 60 135, 94 264, 100 782, 76 698, 42 880, 17 739, 5 345, 1 166, 195, 31, 5, and 1, making in total 431 070 equivalence classes of faces across all dimensions. The lattice has only 24 shortest nonzero vectors, which is its kissing number.

The covering radius and thickness at the optimal point in phase B are approximately 2. p. 7
Where the paper says it

929 297 and 0. The covering radius and thickness are p (a 2 + 3)(3a 2 + 1)/(6a 2) and √ 3π 7 (a 2 + 3)7 (3a 2 + 1)7/(38 093 690 880a 18), which are approximately 2.

819,748 and 18. p. 7
Where the paper says it

The covering radius and thickness are p (a 2 + 3)(3a 2 + 1)/(6a 2) and √ 3π 7 (a 2 + 3)7 (3a 2 + 1)7/(38 093 690 880a 18), which are approximately 2. 819 748 and 18.

264,550 respectively. p. 7
Where the paper says it

819 748 and 18. 264 550 at aopt, respectively.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Parametric Lattice Construction for Optimization: AI systems can utilize a two-step construction process combining initial numerical optimization with subsequent analytical optimization of families of lattices whose Voronoi regions are constructed exactly, as described in the abstract. This allows for the construction of new lattice quantizers with lower normalized second moments than previously reported in dimensions 13 and 14.

  2. Identification of Optimal Lattices: AI systems can employ a deterministic algorithm to fine-tune and exactly identify a locally optimal lattice from a close approximation, even when initial identification methods fail, by exploiting the regular structure where almost all locally optimal lattices exhibit, specifically the arrangement of lattice points on a discrete set of separated, spherical shells.

  3. Phase Boundary Analysis: AI systems can analyze the phase structure of parametric lattices by building a hierarchy of faces and testing topological changes using tests such as checking if the set of parametric facets is the same throughout P'a to determine the region Pa where the Voronoi region has a consistent topology.

  4. Parameter Optimization Strategy: The AI system can follow an iterative strategy to find minima in the NSM function G(a) by considering neighboring phases, using GA2 and GA3 as search directions, rather than assuming a single minimum exists within one phase.

  5. Optimal Lattice Generation: The system can conjecture the globally optimal lattice quantizer by finding the common root of two polynomials of degree 14 (in dimension 13) or a root of a single polynomial of degree 15 (in dimension 14), as derived from the analysis in Appendix A and Appendix C.

Abstract

New lattice quantizers with lower normalized second moments than previously reported are constructed in 13 and 14 dimensions and conjectured to be optimal. Our construction combines an initial numerical optimization with a subsequent analytical optimization of families of lattices, whose Voronoi regions are constructed exactly. The new lattices are constructed from glued products of previously known lattices, by scaling the component lattices and then optimizing the scale factors. A two-parameter family of lattices in 13 dimensions reveals an intricate landscape of phase changes as the parameters are varied.

Sources

Related papers