# On the Best Lattice Quantizers

Erik Agrell, , and Bruce Allen The work of E. Agrell was supported by a
Collaborating Scientist Grant from the Max Planck Institute for Gravitational
Physics, Germany, which is gratefully acknowledged.E. Agrell is with the
Department of Electrical Engineering, Chalmers University of Technology, 41296
Gothenburg, Sweden (e-mail: agrell@chalmers.se).B. Allen is with the Max
Planck Institute for Gravitational Physics, 30167 Hannover, Germany, and
Leibniz Universität Hannover (e-mail: bruce.allen@aei.mpg.de).

###### Abstract

A lattice quantizer approximates an arbitrary real-valued source vector with a
vector taken from a specific discrete lattice. The quantization error is the
difference between the source vector and the lattice vector. In a classic 1996
paper, Zamir and Feder show that the globally optimal lattice quantizer (which
minimizes the mean square error) has white quantization noise: for a uniformly
distributed source, the covariance of the error is the identity matrix,
multiplied by a positive real factor. We generalize the theorem, showing that
the same property holds (i) for any locally optimal lattice quantizer and (ii)
for an optimal product lattice, if the component lattices are themselves
locally optimal. We derive an upper bound on the normalized second moment
(NSM) of the optimal lattice in any dimension, by proving that any lower- or
upper-triangular modification to the generator matrix of a product lattice
reduces the NSM. Using these tools and employing the best currently known
lattice quantizers to build product lattices, we construct improved lattice
quantizers in dimensions 13 to 15, 17 to 23, and 25 to 48. In some dimensions,
these are the first reported lattices with normalized second moments below the
Zador upper bound.

###### Index Terms:

Dither autocorrelation, laminated lattice, lattice theory, mean square error,
moment of inertia, normalized second moment, product lattice, quantization
constant, quantization noise, vector quantization, Voronoi region, white
noise.

##  I Introduction

Lattices are regular arrays of points in ${\mathbb{R}}^{n}$. They are obtained
as arbitrary linear combinations of (at most $n$) linearly independent basis
vectors, with integer coefficients. Hence, lattices are a countably infinite
set of vectors, closed under addition. The remarkable book by Conway and
Sloane [1] provides a comprehensive review of lattices and their properties.

As fundamental geometric structures, lattices have found applications in a
variety of disciplines, including digital communications [2], experimental
design [3], data analysis [4], and particle physics [5]. In each application,
the problem of designing the best lattice for a given purpose arises. Such
optimization challenges often reduce to familiar mathematical problems such as
sphere-packing, sphere-covering, or quantization [1, Ch. 1–2].

In this paper, we are concerned with the _quantization problem_ , which can be
defined as follows. Random vectors in ${\mathbb{R}}^{n}$ are drawn from some
(source) probability distribution, and approximated by their closest lattice
points. This approximation (or quantization) process creates a round-off (or
quantization) error: the difference between the vector and its closest lattice
point. Among all lattices having the same number of lattice points per unit
volume, the optimal lattice quantizer is the lattice with the minimum mean
square error. This is equivalent to minimizing the _normalized second moment_
(NSM), which is a scale-invariant measure of this mean square error.

As in most work on lattice quantization, we assume that the source
distribution is smooth on the scale of the lattice spacing, and that its
support is much larger than that scale. In this case, the optimal lattice does
not depend upon the source probability distribution of the random vectors.

Tables of the NSM, showing the best known lattices for quantization in various
dimensions are listed in [6, 7], [1, p. 61], and the quantization performance
of some additional lattices is computed in [8, 9, 10, 11, 12, 13]. Yet, proofs
of optimality are known only in dimensions up to three [6, 14].

In a pioneering 1996 paper [15], Zamir and Feder show that the optimal lattice
quantizer in any dimension has a _white_ quantization error. More precisely,
the error defined above (vector difference between a random source vector and
its closest lattice vector) has a covariance matrix which is the identity
matrix, scaled by a positive real constant.

In this paper, we extend the Zamir and Feder result to _locally optimal_
lattices. These are lattices whose NSM cannot be reduced by a small
perturbation of the lattice generator matrix. We also consider _product
lattices_ , which are the Cartesian product of two or more lower-dimensional
lattices. The NSM of a product lattice depends on the relative scaling between
the component lattices. If each of the lower-dimensional lattices is locally
optimal, then we prove that the scaling which minimizes the NSM of the product
is the one for which the quantization error is white.

Lastly, we apply these methods to explicitly design some product lattices and
analytically optimize their scale factors. These provide constructive upper
bounds on the quantization performance of the optimal lattices in their
respective dimensions. This simple construction yields better lattice
quantizers than previously reported in all dimensions above $12$ except for
$16$ and $24$. We also prove that further optimization is possible: the NSM of
such product lattices is a saddle point in the space of generator matrices,
and can be further reduced by certain perturbations of the generator matrix.

##  II Mathematical Preliminaries and Method

_Notation:_ Bold lowercase letters ${\boldsymbol{x}}$ denote row vectors,
while bold uppercase letters ${\boldsymbol{X}}$ denote either matrices or
random vectors. An all-zero vector or matrix of an arbitrary size (inferred
from the context) is denoted by ${\boldsymbol{0}}$, and identity matrices are
denoted by ${\boldsymbol{I}}$. Sets are denoted by uppercase Greek letters
$\Omega$, apart from the integers ${\mathbb{Z}}$ and real numbers
${\mathbb{R}}$. Arithmetical operations on sets should be understood as
operating per element, e.g.,
$\Omega+{\boldsymbol{\lambda}}\triangleq\\{{\boldsymbol{x}}+{\boldsymbol{\lambda}}:{\boldsymbol{x}}\in\Omega$}.
Definitions are indicated by $\triangleq$.

Without loss of generality, we consider $n$-dimensional lattices $\Lambda$
that are generated by square invertible $n\times n$ _generator matrices_
${\boldsymbol{B}}$. The lattice consists of the set of points
${\boldsymbol{u}}{\boldsymbol{B}}$ for all row vectors ${\boldsymbol{u}}$ with
integer components. The all-zero row vector ${\boldsymbol{0}}$ belongs to all
lattices. The cubic lattice ${\mathbb{Z}}^{n}$ is the special case for which
${\boldsymbol{B}}$ is the identity matrix.

Until now, we have used “quantization” to denote the map from a vector in
${\mathbb{R}}^{n}$ to the closest lattice point. However, for the proofs in
this paper, we consider more general mappings. A _quantization rule_ or
_quantizer_ for a lattice $\Lambda$ is a function
$Q_{\Lambda}({\boldsymbol{x}})$ such that (i)
$Q_{\Lambda}({\boldsymbol{x}})\in\Lambda$ for all
${\boldsymbol{x}}\in{\mathbb{R}}^{n}$ and (ii)
$Q_{\Lambda}({\boldsymbol{x}}+{\boldsymbol{\lambda}})=Q_{\Lambda}({\boldsymbol{x}})+{\boldsymbol{\lambda}}$
for all ${\boldsymbol{\lambda}}\in\Lambda$ and all
${\boldsymbol{x}}\in{\mathbb{R}}^{n}$. The quantizer’s properties are
completely determined by its behavior in the _fundamental decision region_

$\displaystyle\Omega(Q_{\Lambda})\triangleq\\{{\boldsymbol{x}}\in{\mathbb{R}}^{n}:Q_{\Lambda}({\boldsymbol{x}})={\boldsymbol{0}}\\},$
(1)

since condition (ii) may then be used to determine the action anywhere. The
translate $\Omega(Q_{\Lambda})+{\boldsymbol{\lambda}}$ of the fundamental
decision region is called the decision region of the lattice point
${\boldsymbol{\lambda}}$. All have the same volume [2, Prop. 2.2.1]

$\displaystyle
V_{\Lambda}\triangleq\int_{\Omega(Q_{\Lambda})}\\!\\!\\!\,\mathrm{d}^{n}{\boldsymbol{x}}=|\\!\det\\!{\boldsymbol{B}}|.$
(2)

As indicated by the notation $V_{\Lambda}$, this volume depends upon the
lattice $\Lambda$, but is independent of the quantization rule. Taken
together, the decision regions of all lattice points cover ${\mathbb{R}}^{n}$
without overlap.

As mentioned in the Introduction, the performance of lattice quantizers does
not depend upon the source distribution if this distribution is smooth on the
scale of the lattice. To prove this, consider a source probability density
function (pdf) $p_{\boldsymbol{X}}({\boldsymbol{x}})$, normalized by $\int
p_{\boldsymbol{X}}({\boldsymbol{x}})\,\mathrm{d}^{n}{\boldsymbol{x}}=1$. The
mean square quantization error of the quantization rule is

$\displaystyle{\mathbb{E}}[\|{\boldsymbol{x}}-Q_{\Lambda}({\boldsymbol{x}})\|^{2}]$
$\displaystyle=\int_{{\mathbb{R}}^{n}}\\!\\!\\!p_{\boldsymbol{X}}({\boldsymbol{x}})\|{\boldsymbol{x}}-Q_{\Lambda}({\boldsymbol{x}})\|^{2}\,\mathrm{d}^{n}{\boldsymbol{x}}.$
(3)

Since the translates
$\Omega(Q_{\Lambda})+{\boldsymbol{\lambda}},\forall{\boldsymbol{\lambda}}\in\Lambda$
cover ${\mathbb{R}}^{n}$ without overlap, the mean square error can be written
as

$\displaystyle{\mathbb{E}}[\|{\boldsymbol{x}}-Q_{\Lambda}({\boldsymbol{x}})\|^{2}]=\int_{\Omega(Q_{\Lambda})}\\!\sum_{{\boldsymbol{\lambda}}\in\Lambda}p_{\boldsymbol{X}}({\boldsymbol{\lambda}}+{\boldsymbol{x}})\|{\boldsymbol{x}}\|^{2}\,\mathrm{d}^{n}{\boldsymbol{x}},$
(4)

where we use condition (ii) to write this as an integral over the fundamental
decision region and condition (i) to set
$Q_{\Lambda}({\boldsymbol{x}})={\boldsymbol{0}}$ inside that region. If now
$p_{\boldsymbol{X}}$ varies slowly over the scale of the lattice, then
$\sum_{{\boldsymbol{\lambda}}\in\Lambda}p_{\boldsymbol{X}}({\boldsymbol{\lambda}}+{\boldsymbol{\xi}})$
is approximately constant, independent of ${\boldsymbol{\xi}}$. Such a
probability distribution can be obtained by rescaling a smooth base pdf
$\tilde{p}$ of compact support, for example as
$p_{\boldsymbol{X}}({\boldsymbol{x}})=\alpha^{n}\tilde{p}(\alpha{\boldsymbol{x}})$
in the limit as $\alpha\rightarrow 0$. In such a limit,
$\sum_{{\boldsymbol{\lambda}}\in\Lambda}p_{\boldsymbol{X}}({\boldsymbol{\lambda}}+{\boldsymbol{\xi}})=1/V_{\Lambda}$
for any ${\boldsymbol{\xi}}$,111This can be proved by writing
$\int\tilde{p}({\boldsymbol{x}})\,\mathrm{d}^{n}{\boldsymbol{x}}=1$ as a
Riemann sum over a shifted and scaled lattice
${\boldsymbol{x}}\in\alpha(\Lambda+{\boldsymbol{\xi}})$. and the mean square
error (4) approaches [16]

$\displaystyle E(Q_{\Lambda})$ $\displaystyle\triangleq\lim_{\alpha\rightarrow
0}{\mathbb{E}}[\|{\boldsymbol{x}}-Q_{\Lambda}({\boldsymbol{x}})\|^{2}]$ (5)
$\displaystyle=\frac{1}{V_{\Lambda}}\int_{\Omega(Q_{\Lambda})}\\!\\!\\!\|{\boldsymbol{x}}\|^{2}\,\mathrm{d}^{n}{\boldsymbol{x}}.$
(6)

Hence, in what follows, the pdf of the source does not appear.

Important quantities that are closely related to the mean square error are the
NSM or quantizer constant $G(Q_{\Lambda})$ and the _correlation matrix_
${\boldsymbol{R}}(Q_{\Lambda})$, which are [6], [2, pp. 48, 71]

$\displaystyle G(Q_{\Lambda})$
$\displaystyle\triangleq\frac{E(Q_{\Lambda})}{nV_{\Lambda}^{2/n}},$ (7)
$\displaystyle{\boldsymbol{R}}(Q_{\Lambda})$
$\displaystyle\triangleq\frac{1}{V_{\Lambda}}\int_{\Omega(Q_{\Lambda})}\\!\\!\\!{\boldsymbol{x}}^{\mathrm{T}}{\boldsymbol{x}}\,\mathrm{d}^{n}{\boldsymbol{x}}.$
(8)

Note that the NSM $G(Q_{\Lambda})$ is “dimensionless” in the sense that it is
invariant under uniform rescaling of the lattice. From (6) and (8), it follows
that

$\displaystyle
E(Q_{\Lambda})=\operatorname{tr}\\!{{\boldsymbol{R}}(Q_{\Lambda})},$ (9)

so the trace of the correlation matrix gives the mean square error.

It follows immediately from the definition (8) that the correlation matrix
${\boldsymbol{R}}$ is real, symmetric, and positive definite. If the
quantization noise is not white, then ${\boldsymbol{R}}$ provides “preferred
directions” in the space, for example corresponding to the eigenvector with
the largest or the smallest eigenvalue. In the case of white quantization
noise, however, ${\boldsymbol{R}}$ is proportional to the identity, and does
not generate preferred directions, since every vector is an eigenvector with
the same positive real eigenvalue.

For a given lattice $\Lambda$, the most important quantization rule is the
_minimum-distance quantization rule_ , denoted by a hat:

$\displaystyle
Q_{\Lambda}({\boldsymbol{x}})={\hat{Q}}_{\Lambda}({\boldsymbol{x}})\triangleq\operatorname*{arg\,min}_{{\boldsymbol{\lambda}}\in\Lambda}\|{\boldsymbol{x}}-{\boldsymbol{\lambda}}\|^{2}.$
(10)

For any vector ${\boldsymbol{x}}$, it returns the closest vector in the
lattice (with ties broken arbitrarily). This quantization rule is special
because, for a given lattice $\Lambda$, it minimizes $E(Q_{\Lambda})$ and
$G(Q_{\Lambda})$. This follows immediately from (5), because the expectation
${\mathbb{E}}[\|{\boldsymbol{x}}-Q_{\Lambda}({\boldsymbol{x}})\|^{2}]$ is
minimal if $\|{\boldsymbol{x}}-Q_{\Lambda}({\boldsymbol{x}})\|^{2}$ is
minimized for every ${\boldsymbol{x}}$. Hence, ${\hat{Q}}_{\Lambda}$ is the
_optimal decision rule_ for a given lattice.

For this rule, the fundamental decision region (1) is the _Voronoi region_

$\displaystyle\Omega({\hat{Q}}_{\Lambda})$
$\displaystyle\triangleq\\{{\boldsymbol{x}}\in{\mathbb{R}}^{n}:\|{\boldsymbol{x}}\|^{2}\leq\|{\boldsymbol{x}}-{\boldsymbol{\lambda}}\|^{2},\;\forall{\boldsymbol{\lambda}}\in\Lambda\\},$
(11)

which geometrically consists of all points in ${\mathbb{R}}^{n}$ whose closest
lattice point is the origin.222More precisely, the interiors of (1) and (11)
are equal under the rule (10). With a slight abuse of notation, we disregard
their boundaries, which have zero $n$-volume and do not contribute to any
integral over a finite integrand. An important property of the Voronoi region
of any lattice is that it is symmetric about ${\boldsymbol{0}}$: the center of
gravity
$\int_{\Omega({\hat{Q}}_{\Lambda})}{\boldsymbol{x}}\,\mathrm{d}^{n}{\boldsymbol{x}}={\boldsymbol{0}}$.
Hence, the correlation matrix ${\boldsymbol{R}}(Q_{\Lambda})$ is equal to the
_covariance matrix_ whenever $Q_{\Lambda}={\hat{Q}}_{\Lambda}$ (but not for
arbitrary quantization rules $Q_{\Lambda}$).

Throughout this paper, the word “optimal” is used in several senses. For a
given lattice, the optimal decision rule is the one which minimizes the NSM,
i.e., (10). Among all lattices of given dimension, the optimal lattice is the
one with the smallest NSM. The optimal product of given lattices is the one
that minimizes the NSM among all Cartesian products of those lattices, by
varying the relative scales between them.

Our main theorem-proving technique is, as in [2, Sec. 4.3], to construct
different decision rules for a given lattice, exploiting the fact that their
NSMs are equal to or greater than the NSM of the optimal decision rule
${\hat{Q}}$. For example, in Sec. III, if the quantization noise of a lattice
$\Lambda$ is not white, then ${\boldsymbol{R}}$ provides preferred directions
(say, the eigenvectors with the largest eigenvalue)333 A similar argument
leads to [17, Eq. 5.1.1]. . With these, we construct a family of lattices
${\tilde{\Lambda}}$ with nonoptimal decision rules, whose NSM is smaller than
that of the original lattice $\Lambda$. Since the NSM of ${\tilde{\Lambda}}$
with an optimal decision rule cannot be larger, we have thus shown that the
original lattice is not optimal. A similar proof technique is applied in Sec.
V. Starting with a product lattice, we generate a new non-product lattice,
with a nonoptimal decision rule, but whose NSM is equal to that of the
original starting lattice. Hence, the optimal decision rule on the new non-
product lattice must yield a smaller NSM than that of the original product.

##  III Locally Optimal Lattices

Our starting point is the following theorem, which states that the globally
optimal quantizer lattice has a white quantization error: a covariance matrix
proportional to the identity.

######  Theorem 1 (Zamir–Feder [15], [2, Sec. 4.3])

For the optimal lattice $\Lambda$ in any dimension $n$,

$\displaystyle{\boldsymbol{R}}({\hat{Q}}_{\Lambda})=\frac{E({\hat{Q}}_{\Lambda})}{n}{\boldsymbol{I}}.$
(12)

We now generalize this to the locally optimal case.

A _locally optimal lattice_ is a lattice $\Lambda$ whose NSM
$G({\hat{Q}}_{\Lambda})$ cannot be decreased by an infinitesimal perturbation
of the generator matrix ${\boldsymbol{B}}$ [14]. The extension to Theorem 1
is:

###### Theorem 2

Any locally optimal lattice satisfies (12).

###### Proof:

Our proof is constructive. If the covariance matrix of $\Lambda$ is not
proportional to the identity matrix, we use it to build a nearby lattice
${\tilde{\Lambda}}$ with a smaller NSM than the NSM of $\Lambda$.

Let ${\tilde{\Lambda}}=\Lambda{\boldsymbol{A}}_{\beta}$, where
${\boldsymbol{A}}_{\beta}$ is an invertible $n\times n$ matrix and $\beta$ is
a real parameter to be defined later. As in [15], we consider the minimum-
distance quantizer ${\hat{Q}}_{\Lambda}({\boldsymbol{x}})$ on $\Lambda$ and
the suboptimal quantizer
${\tilde{Q}}_{\tilde{\Lambda}}({\boldsymbol{x}})\triangleq{\hat{Q}}_{\Lambda}({\boldsymbol{x}}{\boldsymbol{A}}_{\beta}^{-1}){\boldsymbol{A}}_{\beta}$
on ${\tilde{\Lambda}}$.

It is straightforward to show that
${\tilde{Q}}_{\tilde{\Lambda}}({\boldsymbol{x}})$ satisfies the two conditions
in Sec. II and has a fundamental decision region
$\Omega({\tilde{Q}}_{\tilde{\Lambda}})=\Omega({\hat{Q}}_{\Lambda}){\boldsymbol{A}}_{\beta}$.
Note that while $\Omega({\hat{Q}}_{\Lambda})$ is the Voronoi region of
$\Lambda$, the fundamental decision region
$\Omega({\tilde{Q}}_{\tilde{\Lambda}})$ is generally _not_ the Voronoi region
of ${\tilde{\Lambda}}$. By (2), it has volume
$V_{\tilde{\Lambda}}=V_{\Lambda}\,|\\!\det\\!{\boldsymbol{A}}_{\beta}|$.

The covariance matrices of the two quantization rules are easily related using
the change of variables (mapping) provided by ${\boldsymbol{A}}_{\beta}$. From
(8), the covariance matrix of ${\tilde{Q}}_{\tilde{\Lambda}}$ is
${\boldsymbol{R}}({\tilde{Q}}_{\tilde{\Lambda}})={\boldsymbol{A}}_{\beta}^{\mathrm{T}}{\boldsymbol{R}}({\hat{Q}}_{\Lambda}){\boldsymbol{A}}_{\beta}$
[15, Eq. (15)]. Hence, the NSM is

$\displaystyle
G({\tilde{Q}}_{\tilde{\Lambda}})=\frac{E({\tilde{Q}}_{\tilde{\Lambda}})}{nV_{\tilde{\Lambda}}^{2/n}}=\frac{\operatorname{tr}\\!{\boldsymbol{A}}_{\beta}\\!{\boldsymbol{A}}_{\beta}^{T}\\!{\boldsymbol{R}}({\hat{Q}}_{\Lambda})}{n(V_{\Lambda}\,|\\!\det\\!{\boldsymbol{A}}_{\beta}|)^{2/n}},$
(13)

where we have used the cyclic property of the trace.

To select ${\boldsymbol{A}}_{\beta}$, we follow the approach described
earlier, using ${\boldsymbol{R}}({\hat{Q}}_{\Lambda})$ to obtain preferred
directions.444From here on, our proof deviates from the corresponding proof in
[15] for _globally_ optimal lattices. Let $\bar{\boldsymbol{R}}$ denote the
traceless part, which by assumption is nonzero:

$\displaystyle\bar{\boldsymbol{R}}\triangleq{\boldsymbol{R}}({\hat{Q}}_{\Lambda})-\frac{\operatorname{tr}\\!{\boldsymbol{R}}({\hat{Q}}_{\Lambda})}{n}{\boldsymbol{I}},$
(14)

and let ${\boldsymbol{A}}_{\beta}\triangleq\exp(\beta\bar{\boldsymbol{R}})$.
This choice of mapping is volume-preserving, since for any square matrix
${\boldsymbol{M}}$,
$\det(\exp({\boldsymbol{M}}))=\exp(\operatorname{tr}{\boldsymbol{M}})$ [18, p.
16]. Thus,
$\det\\!{\boldsymbol{A}}_{\beta}=\exp(\beta\operatorname{tr}\bar{\boldsymbol{R}})=1$.
Note that because the covariance matrix is symmetric and real, both
$\bar{\boldsymbol{R}}$ and ${\boldsymbol{A}}_{\beta}$ are symmetric and real.

For the proof, we only need ${\boldsymbol{A}}_{\beta}$ for small values of
$\beta$:

$\displaystyle{\boldsymbol{A}}_{\beta}={\boldsymbol{I}}+\beta\bar{\boldsymbol{R}}+O(\beta^{2}).$
(15)

Substituting ${\boldsymbol{A}}_{\beta}$ from (15) and
${\boldsymbol{R}}({\hat{Q}}_{\Lambda})={\boldsymbol{I}}\operatorname{tr}\\!{\boldsymbol{R}}({\hat{Q}}_{\Lambda})/n+\bar{\boldsymbol{R}}$
from (14) into (13), the NSM becomes

$\displaystyle G({\tilde{Q}}_{\tilde{\Lambda}})$
$\displaystyle=\frac{1}{nV_{\Lambda}^{2/n}}\operatorname{tr}\\!\left(({\boldsymbol{I}}+\beta\bar{\boldsymbol{R}})^{2}\left[\frac{\operatorname{tr}\\!{\boldsymbol{R}}({\hat{Q}}_{\Lambda})}{n}{\boldsymbol{I}}+\bar{{\boldsymbol{R}}}\right]\right)$
$\displaystyle=G({\hat{Q}}_{\Lambda})+2\beta\frac{\operatorname{tr}\bar{{\boldsymbol{R}}}^{2}}{nV_{\Lambda}^{2/n}},$
(16)

where we have distributed the trace over additions, used
$\operatorname{tr}\\!\bar{\boldsymbol{R}}=0$, and dropped terms of order
$\beta^{2}$ or higher.

It is clear from (III) that for $\beta$ negative, we have
$G({\tilde{Q}}_{\tilde{\Lambda}})<G({\hat{Q}}_{\Lambda})$. This follows
because, since $\bar{\boldsymbol{R}}$ is a non-vanishing real symmetric
matrix, $\operatorname{tr}\bar{\boldsymbol{R}}^{2}$ must be positive555To
prove this, write
$\bar{\boldsymbol{R}}={\boldsymbol{U}}{\boldsymbol{D}}{\boldsymbol{U}}^{-1}$
where ${\boldsymbol{U}}$ is orthogonal and ${\boldsymbol{D}}$ is real and
diagonal, then use the cyclic property of the trace.. Since the NSM of the
minimum distance quantizer on ${\tilde{\Lambda}}$ satisfies666 We have no way
to directly analyze the performance of ${\hat{Q}}_{\tilde{\Lambda}}$ because
we have no simple expression for the Voronoi region
$\Omega({\hat{Q}}_{\tilde{\Lambda}})$. $G({\hat{Q}}_{\tilde{\Lambda}})\leq
G({\tilde{Q}}_{\tilde{\Lambda}})$, we have established that for $\beta$ small
and negative, $G({\hat{Q}}_{\tilde{\Lambda}})<G({\hat{Q}}_{\Lambda})$. ∎

To test Theorem 2, we examine a large number of numerically optimized lattice
quantizers. These were designed in 1996 using an iterative algorithm, which
converges to different locally optimal lattices [11]. A total of $90$ locally
optimal lattices are available as online supplementary material to the 1998
article [19]; we estimate the covariance matrices
${\boldsymbol{R}}({\hat{Q}}_{\Lambda})$ of their quantization errors using
Monte Carlo integration. In all cases, consistent with the theorem, the
obtained covariance matrices are proportional to the identity matrix, apart
from minor round-off errors.

##  IV Product Lattices

In this section, we study lattices that are formed as the Cartesian products
of two lower-dimensional lattices.777The extension to products of more than
two component lattices is straightforward. Gersho applied this technique to
obtain upper bounds on the optimal NSM for $n=5$ and $n=100$, without
formalizing the expressions [6, Sec. VII].

Let two lattices in dimensions $n_{1}$ and $n_{2}$ be denoted by $\Lambda_{1}$
and $\Lambda_{2}$, and consider their product
${\Lambda_{\mathrm{p}}}=\Lambda_{1}\times\Lambda_{2}$, whose dimension is
$n=n_{1}+n_{2}$. A generator matrix for ${\Lambda_{\mathrm{p}}}$ is

$\displaystyle{{\boldsymbol{B}}_{\mathrm{p}}}=\begin{bmatrix}{\boldsymbol{B}}_{1}&{\boldsymbol{0}}\\\
{\boldsymbol{0}}&{\boldsymbol{B}}_{2}\end{bmatrix},$ (17)

where ${\boldsymbol{B}}_{1}$ and ${\boldsymbol{B}}_{2}$ are generator matrices
of $\Lambda_{1}$ and $\Lambda_{2}$. Relevant quantities associated with the
two component lattices, and with their product, are denoted by

$\displaystyle\Omega_{1}$
$\displaystyle\triangleq\Omega({\hat{Q}}_{\Lambda_{1}}),$
$\displaystyle\Omega_{2}$
$\displaystyle\triangleq\Omega({\hat{Q}}_{\Lambda_{2}}),$
$\displaystyle\Omega$
$\displaystyle\triangleq\Omega({\hat{Q}}_{{\Lambda_{\mathrm{p}}}}),$
$\displaystyle V_{1}$ $\displaystyle\triangleq V_{\Lambda_{1}},$
$\displaystyle V_{2}$ $\displaystyle\triangleq V_{\Lambda_{2}},$
$\displaystyle V$ $\displaystyle\triangleq V_{{\Lambda_{\mathrm{p}}}},$
$\displaystyle E_{1}$ $\displaystyle\triangleq E({\hat{Q}}_{\Lambda_{1}}),$
$\displaystyle E_{2}$ $\displaystyle\triangleq E({\hat{Q}}_{\Lambda_{2}}),$
$\displaystyle E$ $\displaystyle\triangleq
E({\hat{Q}}_{{\Lambda_{\mathrm{p}}}}),$ $\displaystyle G_{1}$
$\displaystyle\triangleq G({\hat{Q}}_{\Lambda_{1}}),$ $\displaystyle G_{2}$
$\displaystyle\triangleq G({\hat{Q}}_{\Lambda_{2}}),$ $\displaystyle G$
$\displaystyle\triangleq G({\hat{Q}}_{{\Lambda_{\mathrm{p}}}}),$
$\displaystyle{\boldsymbol{R}}_{1}$
$\displaystyle\triangleq{\boldsymbol{R}}({\hat{Q}}_{\Lambda_{1}}),$
$\displaystyle{\boldsymbol{R}}_{2}$
$\displaystyle\triangleq{\boldsymbol{R}}({\hat{Q}}_{\Lambda_{2}}),$
$\displaystyle{\boldsymbol{R}}$
$\displaystyle\triangleq{\boldsymbol{R}}({\hat{Q}}_{{\Lambda_{\mathrm{p}}}})$

and are related as follows.

###### Theorem 3

For the product lattice ${\Lambda_{\mathrm{p}}}=\Lambda_{1}\times\Lambda_{2}$,

$\displaystyle\Omega$ $\displaystyle=\Omega_{1}\times\Omega_{2},$ (18)
$\displaystyle V$ $\displaystyle=V_{1}V_{2},$ (19) $\displaystyle E$
$\displaystyle=E_{1}+E_{2},$ (20) $\displaystyle G$
$\displaystyle=\frac{n_{1}}{n}V_{1}^{\frac{2n_{2}}{nn_{1}}}V_{2}^{-\frac{2}{n}}G_{1}+\frac{n_{2}}{n}V_{1}^{-\frac{2}{n}}V_{2}^{\frac{2n_{1}}{nn_{2}}}G_{2},$
(21) $\displaystyle{\boldsymbol{R}}$
$\displaystyle=\begin{bmatrix}{\boldsymbol{R}}_{1}&{\boldsymbol{0}}\\\
{\boldsymbol{0}}&{\boldsymbol{R}}_{2}\end{bmatrix}.$ (22)

An example of a $3$-dimensional Voronoi region $\Omega$, constructed according
to Theorem 3 as the Cartesian product of two lower-dimensional Voronoi regions
$\Omega_{1}$ and $\Omega_{2}$, is illustrated in Fig. 1.

$\Omega$$\Omega_{1}$$\Omega_{2}$${\boldsymbol{0}}$ Figure 1:  The Voronoi
region $\Omega$ of the product lattice
${\Lambda_{\mathrm{p}}}=\Lambda_{1}\times\Lambda_{2}$, where $\Lambda_{1}$ is
the two-dimensional hexagonal lattice $A_{2}$ and $\Lambda_{2}$ is the one-
dimensional integer lattice ${\mathbb{Z}}$. The origin ${\boldsymbol{0}}$
belongs to all three lattices and is the centroid of all three Voronoi
regions. The top and bottom facets of $\Omega$ are shifted copies of
$\Omega_{1}$, and the six vertical edges are shifted copies of $\Omega_{2}$.

###### Proof:

To prove (18), let
${\boldsymbol{x}}=[{\boldsymbol{x}}_{1}\;\;{\boldsymbol{x}}_{2}]$ and
${\boldsymbol{\lambda}}=[{\boldsymbol{\lambda}}_{1}\;\;{\boldsymbol{\lambda}}_{2}]$.
By definition, $\Omega$ in (11) is formed by all vectors
${\boldsymbol{x}}_{1}\in{\mathbb{R}}^{n_{1}}$ and
${\boldsymbol{x}}_{2}\in{\mathbb{R}}^{n_{2}}$ such that

$\displaystyle\|{\boldsymbol{x}}_{1}\|^{2}+\|{\boldsymbol{x}}_{2}\|^{2}$
$\displaystyle\leq\|{\boldsymbol{x}}_{1}-{\boldsymbol{\lambda}}_{1}\|^{2}+\|{\boldsymbol{x}}_{2}-{\boldsymbol{\lambda}}_{2}\|^{2},$
(23)

for all ${\boldsymbol{\lambda}}_{1}\in\Lambda_{1}$ and
${\boldsymbol{\lambda}}_{2}\in\Lambda_{2}$.

If ${\boldsymbol{x}}_{1}\in\Omega_{1}$ and
${\boldsymbol{x}}_{2}\in\Omega_{2}$, then
$\|{\boldsymbol{x}}_{1}\|^{2}\leq\|{\boldsymbol{x}}_{1}-{\boldsymbol{\lambda}}_{1}\|^{2}$
and
$\|{\boldsymbol{x}}_{2}\|^{2}\leq\|{\boldsymbol{x}}_{2}-{\boldsymbol{\lambda}}_{2}\|^{2}$.
Summing these implies (23), so $\Omega_{1}\times\Omega_{2}\subseteq\Omega$.

Conversely, if ${\boldsymbol{x}}\in\Omega$, then setting
${\boldsymbol{\lambda}}_{2}={\boldsymbol{0}}$ in (23) implies
$\|{\boldsymbol{x}}_{1}\|^{2}\leq\|{\boldsymbol{x}}_{1}-{\boldsymbol{\lambda}}_{1}\|^{2}$
for all ${\boldsymbol{\lambda}}_{1}\in\Lambda_{1}$, so that
${\boldsymbol{x}}_{1}\in\Omega_{1}$. Similarly, setting
${\boldsymbol{\lambda}}_{1}={\boldsymbol{0}}$ in (23) implies that
${\boldsymbol{x}}_{2}\in\Omega_{2}$. This shows that
$\Omega\subseteq\Omega_{1}\times\Omega_{2}$.

Taken together, $\Omega_{1}\times\Omega_{2}\subseteq\Omega$ and
$\Omega\subseteq\Omega_{1}\times\Omega_{2}$ prove (18), which in turn proves
(19).

The definition (6), applied to a product lattice using (18) and (19), implies
that

$\displaystyle E$
$\displaystyle=\frac{1}{V_{1}V_{2}}\int_{\Omega_{1}\times\Omega_{2}}\\!\\!\\!\left(\|{\boldsymbol{x}}_{1}\|^{2}+\|{\boldsymbol{x}}_{2}\|^{2}\right)\,\mathrm{d}^{n_{1}}{\boldsymbol{x}}_{1}\,\mathrm{d}^{n_{2}}{\boldsymbol{x}}_{2}$
$\displaystyle=\frac{1}{V_{1}V_{2}}\biggl{(}\int_{\Omega_{1}}\\!\\!\\!\|{\boldsymbol{x}}_{1}\|^{2}\,\mathrm{d}^{n_{1}}{\boldsymbol{x}}_{1}\int_{\Omega_{2}}\\!\\!\\!\,\mathrm{d}^{n_{2}}{\boldsymbol{x}}_{2}$
$\displaystyle\qquad+\int_{\Omega_{1}}\\!\\!\\!\,\mathrm{d}^{n_{1}}{\boldsymbol{x}}_{1}\int_{\Omega_{2}}\\!\\!\\!\|{\boldsymbol{x}}_{2}\|^{2}\,\mathrm{d}^{n_{2}}{\boldsymbol{x}}_{2}\biggr{)}$
$\displaystyle=\frac{1}{V_{1}V_{2}}\left(V_{1}E_{1}V_{2}+V_{1}V_{2}E_{2}\right).$
(24)

This proves (20).

Equation (21) follows by substituting $E=G/(nV^{2/n})$ and the corresponding
expressions for $E_{1}$ and $E_{2}$ into (20), and simplifying using (19) and
$n=n_{1}+n_{2}$.

Lastly, to prove (22), we use (18) and (19) in (8) to obtain

$\displaystyle{\boldsymbol{R}}$
$\displaystyle=\frac{1}{V_{1}V_{2}}\int_{\Omega_{1}}\\!\int_{\Omega_{2}}\\!\begin{bmatrix}{\boldsymbol{x}}_{1}^{\mathrm{T}}{\boldsymbol{x}}_{1}&{\boldsymbol{x}}_{1}^{\mathrm{T}}{\boldsymbol{x}}_{2}\\\
{\boldsymbol{x}}_{2}^{\mathrm{T}}{\boldsymbol{x}}_{1}&{\boldsymbol{x}}_{2}^{\mathrm{T}}{\boldsymbol{x}}_{2}\end{bmatrix}\,\mathrm{d}^{n_{1}}{\boldsymbol{x}}_{1}\,\mathrm{d}^{n_{2}}{\boldsymbol{x}}_{2}$
$\displaystyle=\begin{bmatrix}{\boldsymbol{R}}_{1}&{\boldsymbol{R}}_{12}\\\
{\boldsymbol{R}}_{12}^{\mathrm{T}}&{\boldsymbol{R}}_{2}\end{bmatrix},$ (25)

where

$\displaystyle{\boldsymbol{R}}_{12}$
$\displaystyle\triangleq\frac{1}{V_{1}V_{2}}\int_{\Omega_{1}}\\!\int_{\Omega_{2}}\\!\\!\\!{\boldsymbol{x}}_{1}^{\mathrm{T}}{\boldsymbol{x}}_{2}\,\mathrm{d}^{n_{1}}{\boldsymbol{x}}_{1}\,\mathrm{d}^{n_{2}}{\boldsymbol{x}}_{2}$
$\displaystyle=\frac{1}{V_{1}V_{2}}\left(\int_{\Omega_{1}}\\!\\!\\!{\boldsymbol{x}}_{1}\,\mathrm{d}^{n_{1}}{\boldsymbol{x}}_{1}\right)^{\mathrm{T}}\int_{\Omega_{2}}\\!\\!\\!{\boldsymbol{x}}_{2}\,\mathrm{d}^{n_{2}}{\boldsymbol{x}}_{2}$
(26) $\displaystyle={\boldsymbol{0}}.$

These vanish because (as pointed out after (11)) the Voronoi regions
$\Omega_{1}$ and $\Omega_{2}$ are symmetric about zero and thus have their
center of gravity at the origin. ∎

We now generalize the product construction by introducing an explicit real
scale factor $a>0$ to build a one-parameter family of product lattices
$\Lambda(a)=\Lambda_{1}\times a\Lambda_{2}$. A generator matrix for
$\Lambda(a)$ is

$\displaystyle{\boldsymbol{B}}(a)=\begin{bmatrix}{\boldsymbol{B}}_{1}&{\boldsymbol{0}}\\\
{\boldsymbol{0}}&a{\boldsymbol{B}}_{2}\end{bmatrix}.$ (27)

Denoting the parameters of $\Lambda(a)$ by $\Omega(a)$, $V(a)$, $E(a)$,
$G(a)$, and ${\boldsymbol{R}}(a)$, Theorem 3 generalizes as follows.

###### Corollary 4

For the product lattice $\Lambda(a)=\Lambda_{1}\times a\Lambda_{2}$,

$\displaystyle\Omega(a)$ $\displaystyle=\Omega_{1}\times a\Omega_{2},$ (28)
$\displaystyle V(a)$ $\displaystyle=a^{n_{2}}V_{1}V_{2},$ (29) $\displaystyle
E(a)$ $\displaystyle=E_{1}+a^{2}E_{2},$ (30) $\displaystyle G(a)$
$\displaystyle=\frac{n_{1}}{n}a^{-\frac{2n_{2}}{n}}V_{1}^{\frac{2n_{2}}{nn_{1}}}V_{2}^{-\frac{2}{n}}G_{1}$
$\displaystyle\quad+\frac{n_{2}}{n}a^{\frac{2n_{1}}{n}}V_{1}^{-\frac{2}{n}}V_{2}^{\frac{2n_{1}}{nn_{2}}}G_{2},$
(31) $\displaystyle{\boldsymbol{R}}(a)$
$\displaystyle=\begin{bmatrix}{\boldsymbol{R}}_{1}&{\boldsymbol{0}}\\\
{\boldsymbol{0}}&a^{2}{\boldsymbol{R}}_{2}\end{bmatrix}.$ (32)

###### Proof:

In Theorem 3, replace $\Omega_{2}$ by $a\Omega_{2}$, $V_{2}$ by
$a^{n_{2}}V_{2}$, $E_{2}$ by $a^{2}E_{2}$, and ${\boldsymbol{R}}_{2}$ by
$a^{2}{\boldsymbol{R}}_{2}$, while the scale-invariant $G_{2}$ remains
unchanged. ∎

For given $\Lambda_{1}$ and $\Lambda_{2}$, what scale factor
$a={a_{\mathrm{opt}}}$ produces the _optimal product lattice_ $\Lambda(a)$, in
the sense of minimizing $G(a)$? Since (31) diverges in the positive direction
as $a\rightarrow 0$ and as $a\rightarrow\infty$, it has at least one minimum
for a finite $a>0$. This minimum is unique, and has a closed form as follows.

###### Corollary 5

For given lattices $\Lambda_{1}$ and $\Lambda_{2}$, the optimal product
lattice
$\Lambda({a_{\mathrm{opt}}})=\Lambda_{1}\times{a_{\mathrm{opt}}}\Lambda_{2}$
is obtained for

$\displaystyle{a_{\mathrm{opt}}}$
$\displaystyle=\frac{V_{1}^{\frac{1}{n_{1}}}}{V_{2}^{\frac{1}{n_{2}}}}\sqrt{\frac{G_{1}}{G_{2}}}$
(33) $\displaystyle=\sqrt{\frac{n_{2}E_{1}}{n_{1}E_{2}}}.$ (34)

The optimal NSM is

$\displaystyle
G({a_{\mathrm{opt}}})=G_{1}^{\frac{n_{1}}{n}}G_{2}^{\frac{n_{2}}{n}}.$ (35)

###### Proof:

Let

$\displaystyle
C_{1}=V_{1}^{\frac{2n_{2}}{nn_{1}}}V_{2}^{-\frac{2}{n}}G_{1}\text{ and
}C_{2}=V_{1}^{-\frac{2}{n}}V_{2}^{\frac{2n_{1}}{nn_{2}}}G_{2}.$ (36)

The NSM $G(a)$ in (31) may be written as

$\displaystyle
G(a)=\frac{n_{1}}{n}a^{-\frac{2n_{2}}{n}}C_{1}+\frac{n_{2}}{n}a^{\frac{2n_{1}}{n}}C_{2}.$
(37)

Its derivative with respect to $a$ is

$\displaystyle G^{\prime}(a)$
$\displaystyle=-\frac{2n_{1}n_{2}}{n^{2}}a^{-\frac{2n_{2}}{n}-1}C_{1}+\frac{2n_{1}n_{2}}{n^{2}}a^{\frac{2n_{1}}{n}-1}C_{2}$
$\displaystyle=\frac{2n_{1}n_{2}}{n^{2}}a^{\frac{2n_{1}}{n}-3}\left(a^{2}C_{2}-C_{1}\right),$
(38)

where to obtain the final line we use
${-\tfrac{2n_{2}}{n}-1}={\tfrac{2n_{1}}{n}-3}$ for the $C_{1}$ term. The
unique positive solution to $G^{\prime}({a_{\mathrm{opt}}})=0$ is

$\displaystyle{a_{\mathrm{opt}}}=\sqrt{\frac{C_{1}}{C_{2}}}.$ (39)

Substituting this back into (37) and again using $n_{1}+n_{2}=n$ gives the
optimal product NSM

$\displaystyle
G({a_{\mathrm{opt}}})=C_{1}^{\frac{n_{1}}{n}}C_{2}^{\frac{n_{2}}{n}}.$ (40)

Substituting (36) into (39) and (40) now yields (33) and (35), respectively.
Finally, (34) follows from (33) and (7). ∎

The minimum $G(a)$ in (35) depends only on $G_{1}$, $G_{2}$, and the lattice
dimensions, but not on $V_{1}$ or $V_{2}$. It satisfies the elegant
relationship

$\displaystyle G^{n}({a_{\mathrm{opt}}})=G_{1}^{n_{1}}G_{2}^{n_{2}},$ (41)

which is useful and easy to recall.

We are now ready to calculate the covariance matrix. Consider the case where
${\boldsymbol{R}}_{1}=\rho_{1}{\boldsymbol{I}}$ and
${\boldsymbol{R}}_{2}=\rho_{2}{\boldsymbol{I}}$ are each proportional to the
identity matrix, with different constants of proportionality. Because of (9)
and (34), the optimal scale factor satisfies
${a_{\mathrm{opt}}}^{2}\rho_{2}=\rho_{1}$, ensuring that
${\boldsymbol{R}}({a_{\mathrm{opt}}})=\rho_{1}{\boldsymbol{I}}$ is
proportional to the identity matrix. We state this in a way similar to
Theorems 1 and 2, but with different conditions.

###### Corollary 6

If $\Lambda_{1}$ and $\Lambda_{2}$ are locally optimal lattices and
$\Lambda({a_{\mathrm{opt}}})=\Lambda_{1}\times{a_{\mathrm{opt}}}\Lambda_{2}$,
then

$\displaystyle{\boldsymbol{R}}({a_{\mathrm{opt}}})=\frac{E({a_{\mathrm{opt}}})}{n}{\boldsymbol{I}}.$
(42)

###### Proof:

From Theorem 2, ${\boldsymbol{R}}_{1}=(E_{1}/n_{1}){\boldsymbol{I}}$ and
${\boldsymbol{R}}_{2}=(E_{2}/n_{2}){\boldsymbol{I}}$. Using these together
with (34) in (32) yields

$\displaystyle{\boldsymbol{R}}({a_{\mathrm{opt}}})=\begin{bmatrix}\frac{E_{1}}{n_{1}}{\boldsymbol{I}}&{\boldsymbol{0}}\\\
{\boldsymbol{0}}&\frac{n_{2}E_{1}}{n_{1}E_{2}}\frac{E_{2}}{n_{2}}{\boldsymbol{I}}\end{bmatrix}=\frac{E_{1}}{n_{1}}{\boldsymbol{I}}.$
(43)

To complete the proof of (42), we conclude from (30) and (34) that

$\displaystyle
E({a_{\mathrm{opt}}})=E_{1}+\frac{n_{2}E_{1}}{n_{1}E_{2}}E_{2}=\frac{n}{n_{1}}E_{1},$
(44)

or equivalently $E({a_{\mathrm{opt}}})/n=E_{1}/n_{1}$. ∎

Theorem 2 and Corollary 6 are curiously related to each other: both give
sufficient (but not necessary) conditions for white quantization error. Is
Corollary 6 perhaps a special case of Theorem 2? In other words, is the
optimal product lattice $\Lambda({a_{\mathrm{opt}}})$, to which Corollaries 5
and 6 apply, also a locally optimal lattice, as defined in Sec. III? We will
see that the answer is “no”. To say this more precisely, consider the
generator matrix ${\boldsymbol{B}}(a)$ in (27) for $a={a_{\mathrm{opt}}}$. By
the assumptions in Corollary 6, the NSM $G(a)$ is locally minimal with respect
to small variations in ${\boldsymbol{B}}_{1}$ or ${\boldsymbol{B}}_{2}$, and
also minimal with respect to $a={a_{\mathrm{opt}}}$. However, the behavior of
$G(a)$ as a function of the bottom-left or top-right submatrices of
${\boldsymbol{B}}(a)$, which vanish in (27), remains to be studied. In the
next section, we show that setting either of these submatrices nonzero will
decrease the NSM.

${\boldsymbol{0}}$ (a) ${\hat{Q}}_{\Lambda_{\mathrm{p}}}$

${\boldsymbol{0}}$ (b) ${\tilde{Q}}_{\Lambda}$

${\boldsymbol{0}}$ (c) ${\hat{Q}}_{\Lambda}$

Figure 2: An example of Theorem 7 with $n_{1}=n_{2}=1$. Each cell is the
decision region of the lattice point it contains, and the shaded cells are the
fundamental decision regions. Comparing (a) and (b) shows that the NSMs of
${\hat{Q}}_{\Lambda_{\mathrm{p}}}$ and ${\tilde{Q}}_{\Lambda}$ are equal,
because their fundamental decision regions are identical. Comparing (b) and
(c) shows that ${\tilde{Q}}_{\Lambda}$ cannot have a smaller NSM than
${\hat{Q}}_{\Lambda}$, because the lattices are identical and
${\hat{Q}}_{\Lambda}({\boldsymbol{x}})$ minimizes the quantization error for
every ${\boldsymbol{x}}$.

##  V Upper bound

In this section, we show that the NSM of any lattice is upper-bounded by that
of a product lattice, which is given by Theorem 3 or Corollaries 4 or 5.

Consider a square generator matrix of the form

$\displaystyle{\boldsymbol{B}}=\begin{bmatrix}{\boldsymbol{B}}_{1}&{\boldsymbol{0}}\\\
{\boldsymbol{H}}&{\boldsymbol{B}}_{2}\end{bmatrix},$ (45)

where ${\boldsymbol{B}}_{1}$ is $n_{1}\times n_{1}$ and ${\boldsymbol{B}}_{2}$
is $n_{2}\times n_{2}$. Let $\Lambda_{1}$, $\Lambda_{2}$, and $\Lambda$ be the
lattices generated by ${\boldsymbol{B}}_{1}$, ${\boldsymbol{B}}_{2}$, and
${\boldsymbol{B}}$, respectively, and let
${\Lambda_{\mathrm{p}}}=\Lambda_{1}\times\Lambda_{2}$ as in Sec. IV.

###### Theorem 7

For any ${\boldsymbol{H}}$, $G({\hat{Q}}_{\Lambda})\leq
G({\hat{Q}}_{\Lambda_{\mathrm{p}}})$, with equality if
${\boldsymbol{H}}={\boldsymbol{0}}$.

###### Proof:

The method of proof is to define a suboptimal quantizer
${\tilde{Q}}_{\Lambda}$ for which
$G({\tilde{Q}}_{\Lambda})=G({\hat{Q}}_{\Lambda_{\mathrm{p}}})$. The theorem
then follows, because by the definition of ${\hat{Q}}_{\Lambda}$,
$G({\hat{Q}}_{\Lambda})\leq G({\tilde{Q}}_{\Lambda})$. The decision regions
for the three different quantizers are illustrated in Fig. 2.

We construct the suboptimal quantization rule from the optimal quantization
rules for $\Lambda_{1}$ and $\Lambda_{2}$. As earlier, write the source vector
as ${\boldsymbol{x}}=[{\boldsymbol{x}}_{1}\;\;{\boldsymbol{x}}_{2}]$, where
${\boldsymbol{x}}_{1}$ and ${\boldsymbol{x}}_{2}$ have respective dimensions
$n_{1}$ and $n_{2}$. Our suboptimal quantization rule is defined by the
following four-step algorithm:

$\displaystyle\hat{{\boldsymbol{x}}}_{2}$
$\displaystyle\triangleq{\hat{Q}}_{\Lambda_{2}}({\boldsymbol{x}}_{2}),$ (46)
$\displaystyle{\boldsymbol{z}}_{1}$
$\displaystyle\triangleq\hat{{\boldsymbol{x}}}_{2}{\boldsymbol{B}}_{2}^{-1}{\boldsymbol{H}},$
(47) $\displaystyle\hat{{\boldsymbol{x}}}_{1}$
$\displaystyle\triangleq{\hat{Q}}_{\Lambda_{1}}({\boldsymbol{x}}_{1}-{\boldsymbol{z}}_{1}),$
(48) $\displaystyle{\tilde{Q}}_{\Lambda}({\boldsymbol{x}})$
$\displaystyle\triangleq[\hat{{\boldsymbol{x}}}_{1}+{\boldsymbol{z}}_{1}\quad\hat{{\boldsymbol{x}}}_{2}].$
(49)

Quantities with subscript “1” lie in the subspace spanned by the first $n_{1}$
coordinates (horizontal in Fig. 2) and the quantities with subscript “2” lie
in the subspace spanned by the final $n_{2}$ coordinates (vertical in Fig. 2).
We first show that this is a quantization rule: it satisfies the two
conditions given at the start of Sec. II.

Condition (i): Since
${\hat{Q}}_{\Lambda_{1}}({\boldsymbol{x}}_{1}-{\boldsymbol{z}}_{1})\in\Lambda_{1}$
and ${\hat{Q}}_{\Lambda_{2}}({\boldsymbol{x}}_{2})\in\Lambda_{2}$, there exist
integer vectors ${\boldsymbol{u}}_{1}$ and ${\boldsymbol{u}}_{2}$ such that
$\hat{{\boldsymbol{x}}}_{1}={\boldsymbol{u}}_{1}{\boldsymbol{B}}_{1}$ and
$\hat{{\boldsymbol{x}}}_{2}={\boldsymbol{u}}_{2}{\boldsymbol{B}}_{2}$. Then by
(47), ${\boldsymbol{z}}_{1}={\boldsymbol{u}}_{2}{\boldsymbol{H}}$ and by (49),
${\tilde{Q}}_{\Lambda}({\boldsymbol{x}})=[{\boldsymbol{u}}_{1}{\boldsymbol{B}}_{1}+{\boldsymbol{u}}_{2}{\boldsymbol{H}}\;\;{\boldsymbol{u}}_{2}{\boldsymbol{B}}_{2}]=[{\boldsymbol{u}}_{1}\;\;{\boldsymbol{u}}_{2}]{\boldsymbol{B}}$,
which shows that ${\tilde{Q}}_{\Lambda}({\boldsymbol{x}})\in\Lambda$.

Condition (ii): Consider
${\tilde{Q}}_{\Lambda}({\boldsymbol{x}}+{\boldsymbol{\lambda}})$ for an
arbitrary ${\boldsymbol{\lambda}}\in\Lambda$. Let
${\boldsymbol{\lambda}}\triangleq[{\boldsymbol{v}}_{1}\;\;{\boldsymbol{v}}_{2}]{\boldsymbol{B}}=[{\boldsymbol{v}}_{1}{\boldsymbol{B}}_{1}+{\boldsymbol{v}}_{2}{\boldsymbol{H}}\;\;{\boldsymbol{v}}_{2}{\boldsymbol{B}}_{2}]$,
where ${\boldsymbol{v}}_{1}$ and ${\boldsymbol{v}}_{2}$ are integer vectors.
Let
${\boldsymbol{x}}^{\prime}\triangleq[{\boldsymbol{x}}^{\prime}_{1}\;\;{\boldsymbol{x}}^{\prime}_{2}]\triangleq{\boldsymbol{x}}+{\boldsymbol{\lambda}}$,
and let $\hat{{\boldsymbol{x}}}^{\prime}_{2}$,
${\boldsymbol{z}}_{1}^{\prime}$, $\hat{{\boldsymbol{x}}}^{\prime}_{1}$, and
${\tilde{Q}}_{\Lambda}({\boldsymbol{x}}^{\prime})$ denote the quantities
obtained via the algorithm (46)–(49) when ${\boldsymbol{x}}$ is replaced by
${\boldsymbol{x}}^{\prime}$. Since condition (ii) applies to
${\hat{Q}}_{\Lambda_{1}}$ and ${\hat{Q}}_{\Lambda_{2}}$, one finds

$\displaystyle\hat{{\boldsymbol{x}}}^{\prime}_{2}$
$\displaystyle={\hat{Q}}_{\Lambda_{2}}({\boldsymbol{x}}^{\prime}_{2})$
$\displaystyle={\hat{Q}}_{\Lambda_{2}}({\boldsymbol{x}}_{2}+{\boldsymbol{v}}_{2}{\boldsymbol{B}}_{2})$
$\displaystyle={\hat{Q}}_{\Lambda_{2}}({\boldsymbol{x}}_{2})+{\boldsymbol{v}}_{2}{\boldsymbol{B}}_{2}$
$\displaystyle=\hat{{\boldsymbol{x}}}_{2}+{\boldsymbol{v}}_{2}{\boldsymbol{B}}_{2},$
(50) $\displaystyle{\boldsymbol{z}}_{1}^{\prime}$
$\displaystyle=\hat{{\boldsymbol{x}}}^{\prime}_{2}{\boldsymbol{B}}_{2}^{-1}{\boldsymbol{H}}$
$\displaystyle=(\hat{{\boldsymbol{x}}}_{2}+{\boldsymbol{v}}_{2}{\boldsymbol{B}}_{2}){\boldsymbol{B}}_{2}^{-1}{\boldsymbol{H}}$
$\displaystyle=\hat{{\boldsymbol{x}}}_{2}{\boldsymbol{B}}_{2}^{-1}{\boldsymbol{H}}+{\boldsymbol{v}}_{2}{\boldsymbol{H}}$
$\displaystyle={\boldsymbol{z}}_{1}+{\boldsymbol{v}}_{2}{\boldsymbol{H}},$
(51) $\displaystyle\hat{{\boldsymbol{x}}}^{\prime}_{1}$
$\displaystyle={\hat{Q}}_{\Lambda_{1}}({\boldsymbol{x}}^{\prime}_{1}-{\boldsymbol{z}}_{1}^{\prime})$
$\displaystyle={\hat{Q}}_{\Lambda_{1}}({\boldsymbol{x}}_{1}+{\boldsymbol{v}}_{1}{\boldsymbol{B}}_{1}+{\boldsymbol{v}}_{2}{\boldsymbol{H}}-{\boldsymbol{z}}_{1}-{\boldsymbol{v}}_{2}{\boldsymbol{H}})$
$\displaystyle={\hat{Q}}_{\Lambda_{1}}({\boldsymbol{x}}_{1}-{\boldsymbol{z}}_{1})+{\boldsymbol{v}}_{1}{\boldsymbol{B}}_{1}$
$\displaystyle=\hat{{\boldsymbol{x}}}_{1}+{\boldsymbol{v}}_{1}{\boldsymbol{B}}_{1},$
(52) $\displaystyle{\tilde{Q}}_{\Lambda}({\boldsymbol{x}}^{\prime})$
$\displaystyle=[\hat{{\boldsymbol{x}}}^{\prime}_{1}+{\boldsymbol{z}}_{1}^{\prime}\quad\hat{{\boldsymbol{x}}}^{\prime}_{2}]$
$\displaystyle=[\hat{{\boldsymbol{x}}}_{1}+{\boldsymbol{v}}_{1}{\boldsymbol{B}}_{1}+{\boldsymbol{z}}_{1}+{\boldsymbol{v}}_{2}{\boldsymbol{H}}\quad\hat{{\boldsymbol{x}}}_{2}+{\boldsymbol{v}}_{2}{\boldsymbol{B}}_{2}]$
$\displaystyle=[\hat{{\boldsymbol{x}}}_{1}+{\boldsymbol{z}}_{1}\quad\hat{{\boldsymbol{x}}}_{2}]+[{\boldsymbol{v}}_{1}{\boldsymbol{B}}_{1}+{\boldsymbol{v}}_{2}{\boldsymbol{H}}\quad{\boldsymbol{v}}_{2}{\boldsymbol{B}}_{2}]$
$\displaystyle={\tilde{Q}}_{\Lambda}({\boldsymbol{x}})+{\boldsymbol{\lambda}}.$
(53)

Thus, since it satisfies both conditions, ${\tilde{Q}}_{\Lambda}$ is a valid
quantization rule.

The NSM of ${\tilde{Q}}_{\Lambda}$ is determined by its fundamental decision
region, defined by (1). From (49) and (47),
${\tilde{Q}}_{\Lambda}({\boldsymbol{x}})={\boldsymbol{0}}$ if and only if
$\hat{{\boldsymbol{x}}}_{1}={\boldsymbol{0}}$ and
$\hat{{\boldsymbol{x}}}_{2}={\boldsymbol{0}}$. Hence, (1) yields

$\displaystyle\Omega({\tilde{Q}}_{\Lambda})$
$\displaystyle=\\{{\boldsymbol{x}}\in{\mathbb{R}}^{n}:{\hat{Q}}_{\Lambda_{1}}({\boldsymbol{x}}_{1})={\boldsymbol{0}}\text{
and }{\hat{Q}}_{\Lambda_{2}}({\boldsymbol{x}}_{2})={\boldsymbol{0}}\\}$
$\displaystyle=\Omega({\hat{Q}}_{\Lambda_{1}})\times\Omega({\hat{Q}}_{\Lambda_{2}})$
$\displaystyle=\Omega({\hat{Q}}_{\Lambda_{\mathrm{p}}}).$ (54)

Thus, the fundamental decision region of the (suboptimal) quantization rule
for $\Lambda$ is identical to the fundamental decision region of the optimal
quantization rule for ${\Lambda_{\mathrm{p}}}$. This can be intuitively
understood by comparing Figs. 2(a) and 2(b).

Since the fundamental decision regions of ${\tilde{Q}}_{\Lambda}$ and
${\hat{Q}}_{\Lambda_{\mathrm{p}}}$ are identical, so are all parameters
derived from these regions, e.g.,
$E({\tilde{Q}}_{\Lambda})=E({\hat{Q}}_{\Lambda_{\mathrm{p}}})$,
${\boldsymbol{R}}({\tilde{Q}}_{\Lambda})={\boldsymbol{R}}({\hat{Q}}_{\Lambda_{\mathrm{p}}})$,
and $G({\tilde{Q}}_{\Lambda})=G({\hat{Q}}_{\Lambda_{\mathrm{p}}})$. But since
the optimal decision rule for $\Lambda$ satisfies $G({\hat{Q}}_{\Lambda})\leq
G({\tilde{Q}}_{\Lambda})$, our proof is complete: $G({\hat{Q}}_{\Lambda})\leq
G({\hat{Q}}_{\Lambda_{\mathrm{p}}})$. Equality if and only if
${\boldsymbol{H}}={\boldsymbol{0}}$ follows, since ${\boldsymbol{B}}$ in (45)
and ${{\boldsymbol{B}}_{\mathrm{p}}}$ in (17) are equal if and only if
${\boldsymbol{H}}={\boldsymbol{0}}$. ∎

Like Theorem 3, Theorem 7 can also be extended by a scale factor $a$.
Specifically, if ${\boldsymbol{B}}_{2}$ in (45) is multiplied by a scale
factor $a$, then the NSM of the resulting lattice is upper-bounded by $G(a)$
in Corollary 4 or for $a={a_{\mathrm{opt}}}$ by $G({a_{\mathrm{opt}}})$ in
Corollary 5.

We now return to the question of whether the lattice generated by
${\boldsymbol{B}}(a)$ in (27) is locally optimal at $a={a_{\mathrm{opt}}}$. It
was observed at the end of Sec. IV that under the assumptions of Corollary 6,
$G({a_{\mathrm{opt}}})$ is locally _minimal_ with respect to variations in
${\boldsymbol{B}}_{1}$ and ${a_{\mathrm{opt}}}{\boldsymbol{B}}_{2}$, which are
the upper-left and bottom-right submatrices of
${\boldsymbol{B}}({a_{\mathrm{opt}}})$. On the other hand, it follows from
Theorem 7 that $G({a_{\mathrm{opt}}})$ is locally _maximal_ with respect to
variations about ${\boldsymbol{0}}$ in the bottom-left submatrix of
${\boldsymbol{B}}({a_{\mathrm{opt}}})$. By analogy, it can also be shown that
$G({a_{\mathrm{opt}}})$ is locally maximal with respect to variations in the
top-right submatrix of ${\boldsymbol{B}}({a_{\mathrm{opt}}})$.

Since the NSM must decrease for any variations of either the top-right or
bottom-left blocks of ${\boldsymbol{B}}$, the first derivative of $G$ with
respect to these entries must vanish. If the product lattice
${\Lambda_{\mathrm{p}}}$ is locally or globally optimal, then the NSM must
increase for any variations of ${\boldsymbol{B}}_{1}$ or
${\boldsymbol{B}}_{2}$, and hence the first derivative of $G$ with respect to
those entries must also vanish. Since all first derivatives vanish, and the
NSM increases in some directions and decreases in others, we conclude that the
NSM has a _saddle point_ at ${\boldsymbol{B}}({a_{\mathrm{opt}}})$.

##  VI Laminated lattices

One way to construct lattices is by lamination of a lower-dimensional lattice.
To build an $n$-dimensional laminated lattice $\Lambda$, take a generator
matrix ${\boldsymbol{B}}_{1}$ for an $(n-1)$-dimensional lattice $\Lambda_{1}$
and an arbitrary $(n-1)$-dimensional vector ${\boldsymbol{h}}$. Then construct
the $n\times n$ generator matrix

${\boldsymbol{B}}=\begin{bmatrix}{\boldsymbol{B}}_{1}&{\boldsymbol{0}}\\\
{\boldsymbol{h}}&a\end{bmatrix}.$ (55)

Here $a>0$ is a real number, which is the distance between the shifted lattice
copies in the direction orthogonal to their subspace, and the vector
${\boldsymbol{h}}$ is the stacking offset in the $(n-1)$-plane. Fig. 1
illustrates the Voronoi region of a laminated lattice with $n=3$ and
${\boldsymbol{h}}={\boldsymbol{0}}$.

In the classical lattice literature, “laminated lattices” are built
recursively in this way, to maximize the packing density, starting from
${\mathbb{Z}}$. So ${\boldsymbol{B}}_{1}$ is itself the generator for a
laminated lattice, and in each recursive iteration, ${\boldsymbol{h}}$ and $a$
in (55) are selected to maximize the packing density. This construction gives
rise to the well-studied $\Lambda$ and $K$ series in [20, 21], [1, Sec. 4 of
Ch. 5 and Ch. 6].

In this paper, our focus is the NSM rather than the packing density, so we use
“laminated lattice” more broadly for _any_ lattice generated via (55). This
broader meaning is consistent with [22, 13]. Note that to maximize the packing
density, the optimal choice of ${\boldsymbol{h}}$ is a “deep hole” in
$\Lambda_{1}$ (a vertex of the Voronoi region most distant from the origin).
This is also (intuitively) a good choice to minimize the NSM, although it may
not be optimal.

An upper bound on the quantization performance of a laminated lattice follows
directly from the results of Secs. IV and V, as follows.

###### Corollary 8

An $n$-dimensional lattice $\Lambda$ obtained by lamination of an
$(n-1)$-dimensional lattice $\Lambda_{1}$ satisfies, for an arbitrary offset
${\boldsymbol{h}}$ and the optimal layer separation $a$,

$\displaystyle
G({\hat{Q}}_{\Lambda})\leq\frac{G({\hat{Q}}_{\Lambda_{1}})^{1-\frac{1}{n}}}{12^{\frac{1}{n}}}.$
(56)

###### Proof:

Setting $n_{2}=1$, $\Lambda_{2}=a{\mathbb{Z}}$, and
${\boldsymbol{H}}={\boldsymbol{h}}$ in Theorem 7 yields

$\displaystyle G({\hat{Q}}_{\Lambda})\leq
G({\hat{Q}}_{\Lambda_{\mathrm{p}}}),$ (57)

where ${\Lambda_{\mathrm{p}}}=\Lambda_{1}\times a{\mathbb{Z}}$. Furthermore,
setting $n_{2}=1$, $\Lambda_{2}=a{\mathbb{Z}}$,
$G_{1}=G({\hat{Q}}_{\Lambda_{1}})$, and $G_{2}=G({\hat{Q}}_{\mathbb{Z}})=1/12$
in Corollary 5 yields

$\displaystyle
G({\hat{Q}}_{\Lambda_{\mathrm{p}}})\leq\frac{G({\hat{Q}}_{\Lambda_{1}})^{1-\frac{1}{n}}}{12^{\frac{1}{n}}}.$
(58)

Combining (57) and (58) completes the proof. ∎

As a curiosity, we observe that (56) can be elegantly cast as

$\displaystyle\bigl{(}12G({\hat{Q}}_{\Lambda})\bigr{)}^{n}\leq\bigl{(}12G({\hat{Q}}_{\Lambda_{1}})\bigr{)}^{n-1}.$
(59)

The relation would have been even more appealing if $G$ had been defined a
factor of $12$ larger than the standard definition (7). With that alternative
definition, the factors of 12 disappear from (59), and ${\mathbb{Z}}^{n}$
would have an NSM of $1$ in any dimension.

TABLE I: The best known lattice quantizers. Columns 2–3 list the smallest normalized second moments (NSM) $G$ previously reported in dimension $n$, while columns 4–5 list the conjectured lower and upper bounds, respectively. Columns 6–7 list our best product lattices. Columns 8–9 indicate if the product lattice in Column 7 provides a smaller NSM than previously reported in Column 2 ($<$G) and/or is below the upper bound of Column 5 ($<$U). NSMs that are are known exactly are listed with nine decimals, whereas NSMs with five decimals are derived from numerical estimates in [8]. | Best previously reported | Generic bounds | Best product
---|---|---|---
$n$ |  NSM | Lattice | Lower [23] | Upper [16] |  NSM |  Lattice | Better?
$1$ | $0.083333333$ | ${\mathbb{Z}}$ | $0.083333333$ | $0.500000000$ |  |  |  |
$2$ | $0.080187537$ | $A_{2}$ | $0.080187537$ | $0.159154943$ | $0.083333333$ | ${\mathbb{Z}}\otimes{\mathbb{Z}}$ |  |  $<$U
$3$ | $0.078543281$ | $A^{*}_{3}$ | $0.077874985$ | $0.115802581$ | $0.081222715$ | $A_{2}\otimes{\mathbb{Z}}$ |  |  $<$U
$4$ | $0.076603235$ | $D_{4}$ | $0.076087080$ | $0.099735570$ | $0.079714343$ | $A^{*}_{3}\otimes{\mathbb{Z}}$ |  |  $<$U
$5$ | $0.075625443$ | $D^{*}_{5}$ | $0.074654327$ | $0.091319469$ |  $0.077904301$88footnotemark: 8 | $D_{4}\otimes{\mathbb{Z}}$ |  |  $<$U
$6$ | $0.074243697$ | $E^{*}_{6}$ | $0.073474906$ | $0.086084334$ | $0.076858706$ | $D^{*}_{5}\otimes{\mathbb{Z}}$ |  |  $<$U
$7$ | $0.073116493$ | $E^{*}_{7}$ | $0.072483503$ | $0.082478806$ | $0.075478834$ | $E^{*}_{6}\otimes{\mathbb{Z}}$ |  |  $<$U
$8$ | $0.071682099$ | $E_{8}$ | $0.071636064$ | $0.079824101$ | $0.074321725$ | $E^{*}_{7}\otimes{\mathbb{Z}}$ |  |  $<$U
$9$ | $0.071622594$ | $\mathit{AE}_{9}$ | $0.070901661$ | $0.077775626$ | $0.072891732$ | $E_{8}\otimes{\mathbb{Z}}$ |  |  $<$U
$10$ | $0.070813818$ | $D^{+}_{10}$ | $0.070257874$ | $0.076139300$ | $0.072715487$ | $\mathit{AE}_{9}\otimes{\mathbb{Z}}$ |  |  $<$U
$11$ | $0.070426259$ | $A_{11}^{3}$ | $0.069688002$ | $0.074797093$ | $0.071869620$ | $D^{+}_{10}\otimes{\mathbb{Z}}$ |  |  $<$U
$12$ | $0.070095600$ | $K_{12}$ | $0.069179323$ | $0.073672867$ | $0.071420842$ | $A_{11}^{3}\otimes{\mathbb{Z}}$ |  |  $<$U
$13$ | $0.074873919$ | $D^{*}_{13}$ | $0.068721956$ | $0.072715163$ | $0.071034583$ | $K_{12}\otimes{\mathbb{Z}}$ |  $<$G |  $<$U
$14$ | $0.074954492$ | $D^{*}_{14}$ | $0.068308096$ | $0.071887858$ | $0.071455542$ | $K_{12}\otimes A_{2}$ |  $<$G |  $<$U
$15$ | $0.075039738$ | $D^{*}_{15}$ | $0.067931488$ | $0.071164794$ | $0.071709124$ | $K_{12}\otimes A^{*}_{3}$ |  $<$G |
$16$ | $0.06830$ | $\Lambda_{16}$ | $0.067587055$ | $0.070526523$ | $0.071668753$ | $K_{12}\otimes D_{4}$ |  |
$17$ | $0.075216213$ | $D^{*}_{17}$ | $0.067270625$ | $0.069958259$ | $0.06910$ | $\Lambda_{16}\otimes{\mathbb{Z}}$ |  $<$G |  $<$U
$18$ | $0.075304924$ | $D^{*}_{18}$ | $0.066978741$ | $0.069448546$ | $0.06953$ | $\Lambda_{16}\otimes A_{2}$ |  $<$G |
$19$ | $0.075392902$ | $D^{*}_{19}$ | $0.066708503$ | $0.068988355$ | $0.06982$ | $\Lambda_{16}\otimes A^{*}_{3}$ |  $<$G |
$20$ | $0.075479665$ | $D^{*}_{20}$ | $0.066457468$ | $0.068570467$ | $0.06988$ | $\Lambda_{16}\otimes D_{4}$ |  $<$G |
$21$ | $0.075554858$ | $A^{*}_{21}$ | $0.066223553$ | $0.068189035$ | $0.06998$ | $\Lambda_{16}\otimes D^{*}_{5}$ |  $<$G |
$22$ | $0.075577414$ | $A^{*}_{22}$ | $0.066004976$ | $0.067839266$ | $0.06987$ | $\Lambda_{16}\otimes E^{*}_{6}$ |  $<$G |
$23$ | $0.075601888$ | $A^{*}_{23}$ | $0.065800200$ | $0.067517194$ | $0.06973$ | $\Lambda_{16}\otimes E^{*}_{7}$ |  $<$G |
$24$ | $0.06577$ | $\Lambda_{24}$ | $0.065607893$ | $0.067219503$ | $0.06941$ | $\Lambda_{16}\otimes E_{8}$ |  |
$25$ | $0.075655156$ | $A^{*}_{25}$ | $0.065426891$ | $0.066943400$ | $0.06640$ | $\Lambda_{24}\otimes{\mathbb{Z}}$ |  $<$G |  $<$U
$26$ | $0.075683386$ | $A^{*}_{26}$ | $0.065256179$ | $0.066686513$ | $0.06678$ | $\Lambda_{24}\otimes A_{2}$ |  $<$G |
$27$ | $0.075712385$ | $A^{*}_{27}$ | $0.065094858$ | $0.066446812$ | $0.06708$ | $\Lambda_{24}\otimes A^{*}_{3}$ |  $<$G |
$28$ | $0.075741975$ | $A^{*}_{28}$ | $0.064942137$ | $0.066222551$ | $0.06722$ | $\Lambda_{24}\otimes D_{4}$ |  $<$G |
$29$ | $0.075772009$ | $A^{*}_{29}$ | $0.064797312$ | $0.066012219$ | $0.06737$ | $\Lambda_{24}\otimes D^{*}_{5}$ |  $<$G |
$30$ | $0.075802366$ | $A^{*}_{30}$ | $0.064659756$ | $0.065814499$ | $0.06738$ | $\Lambda_{24}\otimes E^{*}_{6}$ |  $<$G |
$31$ | $0.075832940$ | $A^{*}_{31}$ | $0.064528911$ | $0.065628241$ | $0.06736$ | $\Lambda_{24}\otimes E^{*}_{7}$ |  $<$G |
$32$ | $0.075863646$ | $A^{*}_{32}$ | $0.064404271$ | $0.065452432$ | $0.06720$ | $\Lambda_{24}\otimes E_{8}$ |  $<$G |
$33$ | $0.075894409$ | $A^{*}_{33}$ | $0.064285386$ | $0.065286178$ | $0.06732$ | $\Lambda_{24}\otimes\mathit{AE}_{9}$ |  $<$G |
$34$ | $0.075925169$ | $A^{*}_{34}$ | $0.064171846$ | $0.065128688$ | $0.06722$ | $\Lambda_{24}\otimes D^{+}_{10}$ |  $<$G |
$35$ | $0.075955874$ | $A^{*}_{35}$ | $0.064063282$ | $0.064979257$ | $0.06720$ | $\Lambda_{24}\otimes A_{11}^{3}$ |  $<$G |
$36$ | $0.075986480$ | $A^{*}_{36}$ | $0.063959359$ | $0.064837254$ | $0.06718$ | $\Lambda_{24}\otimes K_{12}$ |  $<$G |
$37$ | $0.076016949$ | $A^{*}_{37}$ | $0.063859771$ | $0.064702116$ | $0.06757$ | $\Lambda_{24}\otimes K_{12}\otimes{\mathbb{Z}}$ |  $<$G |
$38$ | $0.076047252$ | $A^{*}_{38}$ | $0.063764240$ | $0.064573336$ | $0.06781$ | $\Lambda_{24}\otimes K_{12}\otimes A_{2}$ |  $<$G |
$39$ | $0.076077363$ | $A^{*}_{39}$ | $0.063672511$ | $0.064450456$ | $0.06799$ | $\Lambda_{24}\otimes K_{12}\otimes A^{*}_{3}$ |  $<$G |
$40$ | $0.076107259$ | $A^{*}_{40}$ | $0.063584352$ | $0.064333062$ | $0.06677$ | $\Lambda_{24}\otimes\Lambda_{16}$ |  $<$G |
$41$ | $0.076136923$ | $A^{*}_{41}$ | $0.063499548$ | $0.064220781$ | $0.06713$ | $\Lambda_{24}\otimes\Lambda_{16}\otimes{\mathbb{Z}}$ |  $<$G |
$42$ | $0.076166341$ | $A^{*}_{42}$ | $0.063417902$ | $0.064113272$ | $0.06736$ | $\Lambda_{24}\otimes\Lambda_{16}\otimes A_{2}$ |  $<$G |
$43$ | $0.076195500$ | $A^{*}_{43}$ | $0.063339234$ | $0.064010223$ | $0.06753$ | $\Lambda_{24}\otimes\Lambda_{16}\otimes A^{*}_{3}$ |  $<$G |
$44$ | $0.076224390$ | $A^{*}_{44}$ | $0.063263376$ | $0.063911352$ | $0.06761$ | $\Lambda_{24}\otimes\Lambda_{16}\otimes D_{4}$ |  $<$G |
$45$ | $0.076253004$ | $A^{*}_{45}$ | $0.063190174$ | $0.063816399$ | $0.06770$ | $\Lambda_{24}\otimes\Lambda_{16}\otimes D^{*}_{5}$ |  $<$G |
$46$ | $0.076281336$ | $A^{*}_{46}$ | $0.063119483$ | $0.063725126$ | $0.06770$ | $\Lambda_{24}\otimes\Lambda_{16}\otimes E^{*}_{6}$ |  $<$G |
$47$ | $0.076309381$ | $A^{*}_{47}$ | $0.063051171$ | $0.063637315$ | $0.06768$ | $\Lambda_{24}\otimes\Lambda_{16}\otimes E^{*}_{7}$ |  $<$G |
$48$ | $0.076337136$ | $A^{*}_{48}$ | $0.062985115$ | $0.063552764$ | $0.06577$ | $\Lambda_{24}\otimes\Lambda_{24}$ |  $<$G |
††footnotemark: Proposed as an upper bound in [6, Tab. I].  |  |

##  VII Best Known Lattice Quantizers

The upper bound in Corollary 8 has interesting implications. These call to
mind an observation made by Cohn in the context of sphere packing [24].
Referring to a plot of sphere-packing density as a function of dimension, he
comments that “ _Certain dimensions, most notably 24, have packings so good
that they seem to pull the entire curve in their direction. The fact that this
occurs is not so surprising, since one expects cross sections and stackings of
great packings to be at least good, but the effect is surprisingly large._ ”
Here, in the context of lattice quantizers, Corollary 8 does precisely this
for NSMs. A lattice with particularly small NSM $G$ in dimension $n-1$ makes
it possible to also obtain a small NSM in dimension $n$, and hence “pulls down
the NSM curve” for larger dimensions. More generally, Theorem 7 can pull down
the curve over intervals of more than one dimension.

We designed product lattices in dimension $n$ by applying Corollary 5 to the
best known lattices in dimensions $n_{1}$ and $n-n_{1}$, constructing product
lattices for $n_{1}$ ranging from $1$ to $n-1$. The minimal NSM obtained in
each dimension provides a constructive upper bound on the optimal NSM. It
follows from Theorem 7 that better lattice quantizers can be found among
lattices of the form (45), where ${\boldsymbol{B}}_{1}$ and
${\boldsymbol{B}}_{2}$ are the best known lattices in dimensions $n_{1}$ and
$n-n_{1}$, respectively, for example by lamination if $n_{1}=1$ or
$n_{1}=n-1$.

Tab. I summarizes the best known lattice quantizers in dimensions $n\leq 48$.
The first such list was compiled in 1979 for $n=1$ to $5$ [6]. It was extended
to $n\leq 10$ in 1982 [7], which also analytically calculated the NSMs of the
classical lattices $A_{n}$, $A^{*}_{n}$, $D_{n}$, and $D^{*}_{n}$ for any $n$.
Since then, progress has been much slower. Better lattices were reported for
$n=6$ and $7$ in [8] and for $n=9$ and $10$ in [11], although the NSMs of
these lattices were only computed numerically. Reference [8] also gave the
best known lattice quantizers for $n=12$, $16$, and $24$ with numerically
computed NSMs. Later, the corresponding exact NSMs were calculated for $n=6$
[9], $n=7$ [10], $n=9$ [13], and $n=10$ and $12$ [12]. In the latter
reference, a new best known lattice quantizer was identified for $n=11$. NSM
results for $n\leq 15$ were summarized in [4].

The upper bound of Zador [16, Lemma 5] and the conjectured lower bound from
Conway and Sloane [23], which we evaluated numerically by high-resolution
trapezoidal integration, are also shown in Tab. I. The Zador upper bound is
for arbitrary quantizers; we conjecture that there is always at least one
lattice quantizer satisfying this bound. Taken together, these two results
provide conjectured lower and upper bounds on the NSM of optimal lattice
quantizers. While intuitively plausible, these remain unproven.

For each dimension, the last four columns of Tab. I list the best product
lattice that can be constructed from the lattices given on the preceding rows
of the table. While Theorem 7 establishes that these lattices are not even
locally optimal, they nevertheless improve significantly on the previously
lowest reported NSMs. For brevity, we use $\otimes$ to denote the Cartesian
product of two lattices with the optimal choice of relative scale. More
precisely,
$\Lambda_{1}\otimes\Lambda_{2}\triangleq\Lambda_{1}\times{a_{\mathrm{opt}}}\Lambda_{2}$
with ${a_{\mathrm{opt}}}$ given by Corollary 5. Thus,
$\Lambda_{1}\otimes\Lambda_{2}$ and $\Lambda_{2}\otimes\Lambda_{1}$ are
equivalent up to scaling, and have the same NSM.

The first dimension in which this construction provides a better lattice
quantizer than previously reported is $n=13$, where our best product lattice
is $K_{12}\otimes{\mathbb{Z}}$. With an NSM of $0.0710$, it is the first
reported $13$-dimensional lattice whose NSM falls below the generic upper
bound $0.0727$. It is significantly better than the currently best known
$13$-dimensional lattice quantizer $D^{*}_{13}$, whose NSM is $0.0749$. Our
optimized product lattices are also the first reported lattices which lie
below the Zador upper bound in dimensions $n=14$, $17$, and $25$.

##  VIII Conclusion

As far as we know, Table I is currently the most extensive published table of
record NSM lattices. Previous tables have not gone beyond $n=16$, apart from a
numerical estimate for $n=24$. It is disconcerting that in many dimensions the
smallest known NSMs are for product lattices, since we have proven that these
cannot be optimal. This reflects the complexity of designing good lattices and
of evaluating their NSMs. The theoretical results in this paper provide some
properties of optimal lattice quantizers, which in combination with the
tabulated product lattices may hopefully provide guidance and benchmarks for
further progress in lattice quantization.

## References

  * [1] J. H. Conway and N. J. A. Sloane, _Sphere Packings, Lattices and Groups_ , 3rd ed. New York, NY: Springer, 1999. [Online]. Available: https://doi.org/10.1007/978-1-4757-6568-7
  * [2] R. Zamir, _Lattice Coding for Signals and Networks_. Cambridge, UK: Cambridge University Press, 2014. [Online]. Available: https://doi.org/10.1017/CBO9781139045520
  * [3] F. A. Hamprecht and E. Agrell, “Exploring a space of materials: Spatial sampling design and subset selection,” in _Experimental Design for Combinatorial and High Throughput Materials Development_ , J. N. Cawse, Ed. New York, NY: Wiley, 2003, ch. 13. [Online]. Available: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.20.6178&rep=rep1&type=pdf
  * [4] B. Allen, “Optimal template banks,” _Phys. Rev. D_ , vol. 104, p. 042005, Aug 2021. [Online]. Available: https://doi.org/10.1103/PhysRevD.104.042005
  * [5] W. Lerche, A. N. Schellekens, and N. P. Warner, “Lattices and strings,” _Physics Reports_ , vol. 177, no. 1–2, pp. 1–140, May 1989. [Online]. Available: https://doi.org/10.1016/0370-1573(89)90077-X
  * [6] A. Gersho, “Asymptotically optimal block quantization,” _IEEE Trans. Inf. Theory_ , vol. IT-25, no. 4, pp. 373–380, July 1979. [Online]. Available: https://doi.org/10.1109/TIT.1979.1056067
  * [7] J. H. Conway and N. J. A. Sloane, “Voronoi regions of lattices, second moments of polytopes, and quantization,” _IEEE Trans. Inf. Theory_ , vol. IT-28, no. 2, pp. 211–226, Mar. 1982. [Online]. Available: https://doi.org/10.1109/TIT.1982.1056483
  * [8] ——, “On the Voronoi regions of certain lattices,” _SIAM J. Alg. Disc. Meth._ , vol. 5, no. 3, pp. 294–305, Sept. 1984. [Online]. Available: https://doi.org/10.1137/0605031
  * [9] R. T. Worley, “The Voronoi region of $E^{*}_{6}$,” _J. Austral. Math. Soc. (Series A)_ , vol. 43, no. 2, pp. 268–278, Oct. 1987. [Online]. Available: https://doi.org/10.1017/S1446788700029402
  * [10] ——, “The Voronoi region of $E^{*}_{7}$,” _SIAM J. Disc. Math._ , vol. 1, no. 1, pp. 134–141, Feb. 1988. [Online]. Available: https://doi.org/10.1137/0401015
  * [11] E. Agrell and T. Eriksson, “Optimization of lattices for quantization,” _IEEE Trans. Inf. Theory_ , vol. 44, no. 5, pp. 1814–1828, Sept. 1998. [Online]. Available: https://doi.org/10.1109/18.705561
  * [12] M. Dutour Sikirić, A. Schürmann, and F. Vallentin, “Complexity and algorithms for computing Voronoi cells of lattices,” _Mathematics of Computation_ , vol. 78, no. 267, pp. 1713–1731, July 2009. [Online]. Available: https://doi.org/10.1090/S0025-5718-09-02224-8
  * [13] B. Allen and E. Agrell, “The optimal lattice quantizer in nine dimensions,” _Annalen der Physik_ , vol. 533, no. 12, p. 2100259, Dec. 2021. [Online]. Available: https://doi.org/10.1002/andp.202100259
  * [14] E. S. Barnes and N. J. A. Sloane, “The optimal lattice quantizer in three dimensions,” _SIAM J. Alg. Disc. Meth._ , vol. 4, no. 1, pp. 30–41, Mar. 1983. [Online]. Available: https://doi.org/10.1137/0604005
  * [15] R. Zamir and M. Feder, “On lattice quantization noise,” _IEEE Trans. Inf. Theory_ , vol. 42, no. 4, pp. 1152–1159, July 1996. [Online]. Available: https://doi.org/10.1109/18.508838
  * [16] P. L. Zador, “Asymptotic quantization error of continuous signals and the quantization dimension,” _IEEE Trans. Inf. Theory_ , vol. IT-82, no. 2, pp. 139–149, Mar. 1982. [Online]. Available: https://doi.org/10.1109/TIT.1982.1056490
  * [17] R. M. Wald, _General Relativity_. Chicago: Chicago University Press, 1984. [Online]. Available: https://doi.org/10.7208/chicago/9780226870373.001.0001
  * [18] L. Perko, _Differential Equations and Dynamical Systems_ , 3rd ed. New York, NY: Springer, 2001. [Online]. Available: https://doi.org/10.1007/978-1-4613-0003-8
  * [19] E. Agrell  _et al._ , “Online supplements.” [Online]. Available: https://codes.se/supplements
  * [20] J. H. Conway and N. J. A. Sloane, “Laminated lattices,” _Annals of Mathematics_ , vol. 116, no. 3, pp. 593–620, Nov. 1982. [Online]. Available: https://doi.org/10.2307/2007025
  * [21] W. Plesken and M. Pohst, “Constructing integral lattices with prescribed minimum. II,” _Mathematics of Computation_ , vol. 60, no. 202, pp. 817–825, Apr. 1993. [Online]. Available: https://doi.org/10.1090/S0025-5718-1993-1176715-1
  * [22] M. Dutour Sikirić, A. Schürmann, and F. Vallentin, “A generalization of Voronoi’s reduction theory and its application,” _Duke Mathematical Journal_ , vol. 142, no. 1, pp. 127–164, Mar. 2008. [Online]. Available: https://doi.org/10.1215/00127094-2008-003
  * [23] J. H. Conway and N. J. A. Sloane, “A lower bound on the average error of vector quantizers,” _IEEE Trans. Inf. Theory_ , vol. IT-31, no. 1, pp. 106–109, Jan. 1985. [Online]. Available: https://doi.org/10.1109/TIT.1985.1056993
  * [24] H. Cohn, “A conceptual breakthrough in sphere packing,” _Notices Amer. Math. Soc._ , vol. 64, no. 2, pp. 102–115, Feb. 2017. [Online]. Available: https://doi.org/10.1090/noti1474