FIND ME ON

GitHub

LinkedIn

High-Resolution Optimal Vector Quantizer

🌱

Theorem
InfoTheory

The integral Rkf(x)λ(x)2/kdx\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} }

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

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

\begin{proof} 1kD(Q)=1ki=1NRixci2f(x)dx(1)1N2/ki=1NG(Ri)f(ci)λ(ci)2/kV(Ri)(2)G(Rk)N2/ki=1Nf(ci)λ(ci)2/kV(Ri)(3)CkN2/kRkf(x)λ(x)2/kdx(4)N2/kCkfk2+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 RRkR\subset \mathbb{R}^{k}, limN1N(# 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: RidxG(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)fk/(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}