ℹ

High-Resolution Optimal Vector Quantizer

Lemma

The integral ∫Rkf(x)λ(x)2/k dx\int\limits _{\mathbb{R}^{k}} \frac{f(\mathbf{x})}{\lambda(\mathbf{x})^{2/k}} \, d\mathbf{x} is minimized over all choices of the pdf λ\lambda if and only if λ(x)=f(x)k/(2+k)∫Rkf(y)k/(2+k) dy\lambda(\mathbf{x})= \frac{f(\mathbf{x})^{k/(2+k)}}{\int\limits _{\mathbb{R}^{k}}f(\mathbf{y})^{k/(2+k)} \, d\mathbf{y} }

Cnj (Gersho’s Conjecture)

For large NN, the quantization cells of the optimal kk-dimensional VQ are (approximately) the scaled, rotated, and translated copies of Rk∗R_{k}^{*}, the convex polytope that tessellates Rk\mathbb{R}^{k} with minimum normalized moment of inertia, i.e., G(Ri)≈min⁡R tessellates RkG(R)=G(Rk∗)≜Ck∗G(R_{i})\approx\min_{R\text{ tessellates }\mathbb{R}^{k}}G(R)=G(R_{k}^{*})\triangleq C_{k}^{*}

Theorem

Under high-resolution conditions the optimal VQ QQ has distortion 1kD(Q)≈N−2/kCk∗∥f∥k(2+k)\frac{1}{k} D(Q)\approx N^{-2/k}C^{*}_{k}\lVert f \rVert _{\frac{k}{(2+k)}}

\begin{proof} 1kD(Q)=1k∑i=1N∫Ri∥x−ci∥2f(x) dx(1)≈1N2/k∑i=1NG(Ri)f(ci)λ(ci)2/kV(Ri)(2)≈G(Rk∗)N2/k∑i=1Nf(ci)λ(ci)2/kV(Ri)(3)≈Ck∗N2/k∫Rkf(x)λ(x)2/k dx(4)≈N−2/kCk∗∥f∥k2+k(5)\begin{align*} \frac{1}{k}D(Q)&=\frac{1}{k}\sum_{i=1}^{N}\int\limits _{R_{i}}\lVert \mathbf{x}-\mathbf{c}_{i} \rVert ^{2}f(\mathbf{x}) \, d\mathbf{x}&(1)\\ &\approx \frac{1}{N^{2/k}}\sum_{i=1}^{N}G(R_{i}) \frac{f(\mathbf{c}_{i})}{\lambda(\mathbf{c}_{i})^{2/k}}V(R_{i})&(2)\\ &\approx \frac{G(R_{k}^{*})}{N^{2/k}}\sum_{i=1}^{N} \frac{f(\mathbf{c}_{i})}{\lambda(\mathbf{c}_{i})^{2/k}}V(R_{i})&(3)\\ &\approx \frac{C_{k}^{*}}{N^{2/k}}\int\limits _{\mathbb{R}^{k}}\frac{f(\mathbf{x})}{\lambda(\mathbf{x})^{2/k}} \, d\mathbf{x}&(4)\\ &\approx N^{-2/k}C_{k}^{*}\lVert f \rVert _{\frac{k}{2+k}}&(5) \end{align*}With (1) being by definition. With (2) we have that λ\lambda is the point density of the sequence of quantizers that satisfies: For any reasonable R⊂RkR\subset \mathbb{R}^{k}, lim⁡N→∞1N(# of codevectors in R)=∫Rλ(x) dx\lim_{ N \to \infty } \frac{1}{N}(\text{\# of codevectors in }R)=\int\limits _{R}\lambda(\mathbf{x}) \, d\mathbf{x} where λ\lambda is a pdf. and: ∫Ri dx≈G(Ri)V(Ri)\int\limits _{R_{i}} \, d\mathbf{x}\approx G(R_{i})V(R_{i}) With (3) and (4) we apply
With (5) we apply lemma 4. Where optimal λ\lambda satisfies: λ(x)=f(x)k/(2+k)∥f∥k/(2+k)k/(2+k)\lambda(\mathbf{x})=\frac{f(\mathbf{x})^{k/(2+k)}}{\lVert f \rVert _{{k}/{(2+k)}}^{k/(2+k)}} \end{proof}