Greedy vector quantization

TitleGreedy vector quantization
Publication TypeJournal Article
Year of Publication2014
AuthorsHarald Luschgy, and Gilles Pagès
JournalPreprint
Abstract

We investigate the greedy version of the $ L^p $-optimal vector quantization problem for an $ R^d $-valued random vector $ X \in L^p $. We show the existence of a sequence $ (a_N)_{N \geq 1} $ such that $ a_N $ minimizes $ a \to \| \min_{1 \leq i \leq N−1} |X −a_i| \wedge |X −a| \| _{L^p} $
($ L^p $-mean quantization error at level $ N $ induced by $ (a_1, ... , a_{N−1}, a) $). We show that this sequence produces $ L^p $-rate optimal $ N $-tuples $ a^{(N)} = (a1, ... , aN ) $ (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 \leq 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.