Greedy vector quantization (extended version)

Quantification vectorielle gloutonne (version longue)

Gilles Pagès (1)

1 LPSM (UMR_8001) - Laboratoire de Probabilités, Statistique et Modélisation

We investigate the greedy version of the L p-optimal vector quantization problem for an R dvalued random vector X ∈ L p. We show the existence of a sequence (a N) N ≥1 such that a N minimizes a → min 1≤i≤N −1 |X − a i | ∧ |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) = (a 1 ,. .. , a N) (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 L q-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.

Mots clés: Optimal Vector Quantization greedy optimization distortion mismatch Lloyd's I procedure Competitive Learning Vector Quantization 60G15; 60G35; 41A25; Optimal Vector Quantization; greedy optimization; distortion mismatch; Lloyd's I procedure; Competitive Learning Vector Quantization 60G15

Domaines: Probabilités [math.PR]

Gilles Pagès. Greedy vector quantization (extended version). 2022. ⟨hal-03890821⟩