Greedy vector quantization

Abstract

We investigate the greedy version of the $L^p$-optimal vector quantization problem for an ${\mathbb{R}}^d$-valued random vector $X\in L^p$. We show the existence of a sequence $(a_N{)}_{N\ge 1}$ such that $a_N$ minimizes $a\mapsto \Vert {\min }_{1\le i\le N-1}|X-a_i|\wedge |X-a|{\Vert }_{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.e.$ 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.

31 pages, 4 figures, few typos corrected (now an extended version of an eponym paper to appear in Journal of Approximation)