Greedy vector quantization

We investigate the greedy version of the Lp-optimal vector quantization problem for an Rd-valued random vector X ∈ Lp. We show the existence of a sequence (aN)N≥1 such that aN minimizes a 7 → ∥∥min1≤i≤N−1 |X−ai | ∧ |X−a|∥∥Lp (Lp-mean quantization error at level N induced by (a1,..., aN−1, a)). We show that this sequence produces Lp-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− 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 Lq-norms, p ≤ 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