Nearest Neighbour Condition

🌱

Theorem

InfoTheory

Consider all $N$ -level scalar quantizers with codebook $\mathcal{C}=\{ y_{1},\dots,y_{N} \}$ . Among these, any quantizer with quantizer cells satisfying $\tag{*}R_{i}=\{ x:d(x,y_{i})\le d(x,y_{j}), \ j=1,\dots,N \} \ \ i=1,\dots,N$ has minimum distortion.

Consider all $N$ -level vector quantizers with codebook $\mathcal{C}=\{ \mathbf{c}_{1},\dots,\mathbf{c}_{N} \}$ . Among these, any quantizer with quantizer cells satisfying $\tag{*}R_{i}=\{ \mathbf{x}:d(\mathbf{x},\mathbf{c}_{i})\le d(\mathbf{x},\mathbf{x}_{j}), \ j=1,\dots,N \} \ \ i=1,\dots,N$ has minimum distortion.

Intuition

This idea is pretty straightforward, for each $x_{j}$ to the closest $y_{i}$ and put it in that $R_{i}$ . >[!cor] > $Q$ with codebook $\mathcal{C}$ satisfies ( $*$ ) if and only if $\forall x\in\mathbb{R}$ $Q(x)=y_{i}\implies d(x,y_{i})\le d(x,y_{j}) \ \forall j$ or equivalently $\forall x\in\mathbb{R}$ $d(x,Q(x))=\min_{y_{j}\in\mathcal{C}}d(x,y_{j})$ or $Q(x)=\underset{y_{j}\in\mathcal{C}}{\mathrm{arg \ min}} \ d(x,y_{j})$

Linked from

Lloyd-Max Algorithm

Lloyd-Max Quantizer

Nearest Neighbour Vector Quantizer (NNVQ)