FIND ME ON

GitHub

LinkedIn

High-Resolution Conditions LVQ

🌱

Definition
InfoTheory

Assume RR is a kk-dimensional polytope with finite volume V(R)V(R) with centroid at origin minyRxy2dx=Rx2dx\min_{\mathbf{y}}\int\limits _{R}\lVert \mathbf{x}-\mathbf{y} \rVert ^{2} \, d\mathbf{x}=\int\limits _{R}\lVert \mathbf{x} \rVert ^{2} \, d\mathbf{x} The dimensionless normalized second moment of RR (a basic cell) is G(R)1k1V(R)1+2/kRx2dxG(R)\triangleq \frac{1}{k} \frac{1}{V(R)^{1+2/k}}\int\limits _{R}\lVert \mathbf{x} \rVert ^{2} \, d\mathbf{x}

Let α>0\alpha>0 and RRkR\subset \mathbb{R}^{k}, let αR={αx:xR}\alpha R=\{ \alpha \mathbf{x}:\mathbf{x}\in R \}. Our quantity G(R)G(R) is scale-invariant; i.e. α>0\forall\alpha>0 G(αR)=G(R)G(\alpha R)=G(R)

Intuition

This is a scale-invariant quantity that depends on the shape of our cell RR and characterizes how good our Lattice Vector Quantizer is.

Assuming High-Resolution Conditions (i.e. Xf\mathbf{X}\sim f where ff smooth and basic cell R0R_{0} small enough) we have that the Lattice Vector Quantizer can be approximated as D(QΛ)1V(R0)R0x2dxD(Q_{\Lambda})\approx \frac{1}{V(R_{0})}\int\limits _{R_{0}}\lVert \mathbf{x} \rVert ^{2} \, d\mathbf{x} and using the dimensionless second moment of R0R_{0} we can redefine it as D(QΛ)V(R0)2/kG(R0)D(Q_{\Lambda})\approx V(R_{0})^{2/k}G(R_{0})

H(R0)1V(R0)R0x2dxH(R_{0})\triangleq \frac{1}{V(R_{0})}\int\limits _{R_{0}}\lVert \mathbf{x} \rVert ^{2} \, d\mathbf{x} is the moment of inertia of the kk-dimensional convex polytope R0R_{0}.

Under high-resolution conditions the dimensionless normalized second moment of R0R_{0} (i.e. G(R0)G(R_{0})) is the appropriate measure for comparing LVQs.

We define the minimum normalized second moment for kk-dimensional lattices as Gk=minΛRkG(R0)G_{k}=\min_{\Lambda \subset \mathbb{R}^{k}}G(R_{0})

The minimum normalized second moment, GkG_{k} is lower bounded by the normalized second moment of a sphere GkG(Sk)G_{k}\ge G(S_{k})where Sk={xRk:x1}S_{k}=\{ \mathbf{x}\in\mathbb{R}^{k}:\lVert \mathbf{x} \rVert\le 1 \}.

We can show that limkG(Sk)=12πe\lim_{ k \to \infty }G(S_{k})=\frac{1}{2\pi e} and limkGk=infk1Gk=12πe\lim_{ k \to \infty }G_{k}=\inf_{k\ge 1}G_{k}=\frac{1}{2\pi e} hence in large dimension, optimal lattice cells are nearly spherical.

Linked from