Greedy vector quantization

We investigate the greedy version of the $L^p$-optimal vector quantization problem for an ${\mathbb{R}}^d$-valued random vector $X\text{\hspace{0.17em}⁣}\in L^p$. We show the existence of a sequence $(a_N{)}_{N\ge 1}$ such that $a_N$ minimizes $a\mapsto \parallel {\min }_{1\le i\le N-1}\mathrm{\mid }X-a_i\mathrm{\mid }\wedge \mathrm{\mid }X-a\mathrm{\mid }{\parallel }_{L^p}$ ($L^p$-mean quantization error at level $N$ induced by $(a_1,\dots ,a_{N-1},a)$). We show that this sequence produces $L^p$-rate optimal $N$-tuples $a^{(N)}=(a_1,\dots ,a_{{}_N})$ ($i\mathrm{.}e\mathrm{.}$ the $L^p$-mean quantization error at level $N$ induced by $a^{(N)}$ goes to $0$ at rate $N^{-\frac{1}{d}}$). Greedy optimal sequences also satisfy, under natural additional assumptions, the distortion mismatch property: the $N$-tuples $a^{(N)}$ remain rate optimal with respect to the $L^q$-norms, $p\le q<p+d$. Finally, we propose optimization methods to compute greedy sequences, adapted from usual Lloyd’s I and Competitive Learning Vector Quantization procedures, either in their deterministic (implementable when $d=1$) or stochastic versions.