The Optimal Lattice Quantizer in Nine Dimensions. Issue 12 (24th October 2021) - Allen, Bruce; Agrell, Erik
Abstract: The optimal lattice quantizer is the lattice that minimizes the (dimensionless) second moment G . In dimensions 1 to 3, it has been proven that the optimal lattice quantizer is one of the classical lattices, and there is good numerical evidence for this in dimensions 4 to 8. In contrast, in 9 dimensions, more than two decades ago, the same numerical studies found the smallest known value of G for a non‐classical lattice. The structure and properties of this conjectured optimal lattice quantizer depend upon a real parameter a > 0, whose value was only known approximately. Here, a full description of this one‐parameter family of lattices and their Voronoi cells is given, and their (scalar and tensor) second moments are calculated analytically as a function of a . The value of a which minimizes G is an algebraic number, defined by the root of a 9th order polynomial, with a ≈ 0.573223794 . For this value of a, the covariance matrix (second moment tensor) is proportional to the identity, consistent with a theorem of Zamir and Feder for optimal quantizers. The structure of the Voronoi cell depends upon a, and undergoes phase transitions at a 2 = 1 / 2, 1, and 2, where its geometry changes abruptly. At each transition, the analytic formula for the second moment changes in a very simple way. The methods can be used for arbitrary one‐parameter families of laminated lattices, and may thus provide a useful tool to identify optimal quantizers in other dimensions as well. Abstract : Lattices are periodic arrangements of points in n ‐dimensional space. How should the grid be arranged, to minimize the average squared distance to the closest point? Lattices studied during the past century appear to provide the best solutions for n ≤ 8 . In this work, in n = 9 dimensions, a non‐classical "laminated" lattice is found, shown to be better, and conjectured to be optimal.