Vector Quantization

Notes on Vector Quantization from ELEC 461 Digital Communications

• Instead of quantizing the input samples one-by-one, we take $n$ input samples: $\mathbf{X}=[x_1,x_2,\dots ,x_n]\in {\mathbb{R}}^n$
  • in other words: we quantize vectors, not scalars
  • the rate of the source code is $R=\frac{lo{g}_{2}K}{n}$ bits / source sample
• ${\mathbb{R}}^n$ is partitioned into $K$ regions, $\{{\mathcal{R}}_i{\}}_{i=1}^K$ and $Q(\mathbf{X})={\hat{\mathbf{X}}}_i,\forall \mathbf{X}\in {\mathcal{R}}_i$
  • $\{{\mathcal{R}}_i{\}}_{i=1}^K$ is the set of Voronoi regions
  • The Voronoi regions comprise the (Euclidean) space wherein a given vector, $\mathbf{X}$ is closer to a specific codeword / centroid, $i$, than any other, $j\ne i$ ${\Re }_i=\left\{\mathbf{X}\in {\mathbb{R}}^n\mid \Vert \mathbf{X}-{\hat{\mathbf{X}}}_i\Vert <\Vert \mathbf{X}-{\hat{\mathbf{X}}}_j\Vert \text{, for all }i\ne j\right\}$
• Optimal VQ: ${\hat{\mathbf{X}}}_i$ is the centroid of the Voronoi region, ${\mathcal{R}}_i$:
  • ${\hat{\mathbf{X}}}_i:=\mathbb{E}[\mathbf{X}|\mathbf{X}\in {\mathcal{R}}_i]$
• A vector quantizing maps $n$-dimensional vectors $\mathbf{X}\in {\mathbb{R}}^n$ to a finite set of vectors
• Each vector is called a code vector or codeword, and the set of all codewords, $\mathcal{X}$ is called a codebook
• Associated with each codeword, ${\hat{\mathbf{X}}}_i$
• Can obtain codewords via e.g. K-means clustering (Lloyd’s algorithm)