Note

$$\text{optimal quantizer}\implies \text{NNC}+\text{CC}$$

First we define the Lloyd Iteration:

Lloyd Iteration

1. Given $\mathcal{C}_{m}=\{ y_{1}^{(m)},\dots,y_{N}^{(m)} \}$, use the NN condition to form the optimal partition $$\tag{*}R_{i}^{(m)}=\{ x:d(x,y_{i}^{(m)})\le d(x,y_{j}^{m}), \ j=1,\dots,N \} \ \ i=1,\dots,N$$

2. Determine $\mathcal{C}_{m+1}=\{ y_{1}^{(m+1)},\dots,y_{N}^{(m+1)} \}$ using the centroid condition $$y_{i}^{(m+1)}=\underset{y\in\mathbb{R}}{\arg\min} \ E[d(X,y)|X\in R_{i}^{(m)}], \ i=1,\dots,N$$ Now we have enough to state the Lloyd-Max algorithm

   Algorithm

3. Inputs: pdf $f(x)$, initial codebook $\mathcal{C}_{1}=\{ y_{1}^{(1)},\dots,y_{N}^{(1)} \}$, threshold $\epsilon>0$. Set $m=1$ and $D_{1}=E[d(X,Q^{(1)(X)})]$.

4. Given $\mathcal{C}_{m}$, perform the Lloyd Iteration to get $\mathcal{C}_{m+1}$

5. Compute $D_{m+1}=E[d(X,Q^{(m+1)}(X))]$ If $$\frac{D_{m}-D_{m+1}}{D_{m}}<\epsilon$$then output $\mathcal{C}_{m+1}$ and stop. Otherwise $m:=m+1$ and go step $2$.

Remarks

• Lloyd iteration either reduces distortion or leaves it unchanged, i.e. it is non-increasing, and $D_{m}$ converges to a limit as $m\to \infty$. Hence $$\lim_{ m \to \infty } \frac{D_{m}-D_{m+1}}{D_{m}}=0$$
• It is not guaranteed $\mathcal{C}_{m}$ converges.
• If $\mathcal{C}_{m}$ converges it is not guaranteed that our “limit quantizer” will be optimal.