Theorem

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 (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}$.