Faster Closest-Point Algorithms for the $E_6^*$ and $E_7^*$ Lattices
2026-07-12 • Information Theory
Information Theory
AI summaryⓘ
The authors study the lattices E6* and E7*, which are important for data compression because they reduce quantization errors. Previously, decoding these lattices required checking multiple separate parts (cosets), which was slow. They show that using a method involving "glue vectors" and an existing algorithm (MCQ) allows all parts to be checked at once efficiently. This new approach speeds up decoding by about 3 to 6 times compared to the old method. They also mention potential further speed improvements and pose an open problem about even faster decoding without sorting.
latticeE6* latticeE7* latticequantization errornearest-lattice-point algorithmcoset decodingroot latticeglue vectorA_n* latticedata compression
Authors
Yuriy A. Reznik
Abstract
The dual lattices $E_6^*$ and $E_7^*$ are of particular interest in source coding and data compression applications. Among all known lattices in dimensions six and seven they attain the smallest normalized second moments, i.e., the smallest average quantization error. Their use in practice requires fast closest-point (nearest-lattice-point) algorithms. The known approach, due to Conway and Sloane and completed for $E_6$ and $E_6^*$ by Takizawa, Yagi, and Kawabata (TYK), decodes these lattices as unions of cosets of root lattices $A_n$: each coset is decoded separately, and the best result is kept. This requires four coset decodings for $E_7^*$ and six for $E_6^*$, together with explicit distance computations. This paper shows that all these coset decodings can be collapsed into a single sweep. Reformulated in terms of glue vectors, the TYK decompositions state that $E_7^*$ is the union of the even glue classes of $A_7^*$, and that $E_6^*$ is a parity-matched sublattice of $A_1^*\oplus A_5^*$. The candidate chain constructed by the closest-point algorithm of McKilliam, Clarkson, and Quinn (MCQ) for $A_n^*$ visits every glue class of $A_n$ exactly once and is optimal within each class. Consequently, one sorted sweep per coordinate block yields the closest points of all glue cosets simultaneously, and $E_6^*$ and $E_7^*$ are decoded at roughly the cost of a single $A_5^*$ or $A_7^*$ quantization. Rough operation counts indicate a $4$--$6\times$ reduction for $E_6^*$ and $3$--$4\times$ for $E_7^*$ relative to coset-by-coset decoding. We also discuss further constant-factor improvements available from recent refinements of the $A_n^*$ algorithms, and an open question concerning sort-free linear-time decoding.