Centroid Condition

Theorem (Centroid Condition (Scalar))

Consider all $N$ -level scalar quantizers with a given partition $\{ R_{1},\dots,R_{N} \}$ . Among these, the quantizer $Q$ with output levels $y_{i}=\underset{y\in\mathbb{R}}{\arg\min} \ E[d(X,y)|X\in R_{i}], \ i=1,\dots,N$ has minimum distortion.

Theorem (CC for MSE)

The $y_{i}$ ’s minimizing the MSE distortion given a partition $\{ R_{1},\dots,R_{N} \}$ are uniquely given by $y_{i}=E[X|X\in R_{i}], \ i=1,\dots,N$

Theorem (Centroid Condition (Vector))

Consider all $N$ -point vector quantizers with a given partition $\{ R_{1},\dots,R_{N} \}$ . Among these, the quantizer $Q$ with output levels $\mathbf{c}_{i}=\underset{\mathbf{c}\in\mathbb{R}^{k}}{\arg\min} \ E[d(\mathbf{X},\mathbf{c})|\mathbf{X}\in R_{i}], \ i=1,\dots,N$ has minimum distortion.

Intuition

Here we update each centroid, or each $y_{i}$ by finding the $y\in\mathbb{R}$ that creates minimum average distance of each $x\in R_{i}$ .

Theorem (CC for MSE for vectors)

The $y_{i}$ ’s minimizing the MSE VQ Distortion given a partition $\{ R_{1},\dots,R_{N} \}$ are uniquely given by $\mathbf{c}_{i}=E[\mathbf{X}|\mathbf{X}\in R_{i}], \ i=1,\dots,N$

Remark

If we have that $X\sim f$ , then $f_{X|R_{i}}(x)=\begin{cases} \frac{f(x)}{P(X\in R_{i})} & \text{if }x\in R_{i} \\ 0 & \text{otherwise} \end{cases}$ so $E[X|X\in R_{i}]=\int\limits _{-\infty}^{\infty}xf_{X|R_{i}}(x) \, dx =\frac{ \int\limits _{R_{i}}xf(x) \, dx }{\int\limits_{R_{i}} f(x) \, dx }=\frac{ \int\limits _{R_{i}}xf(x) \, dx }{P(X\in R_{i})}$

Linked from

Lloyd-Max Algorithm