Greedy vector quantization (extended version) - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... (Working Paper) Year :

Greedy vector quantization (extended version)

Quantification vectorielle gloutonne (version longue)



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.
Fichier principal
Vignette du fichier
Greedy_Longrev.pdf (533.27 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-03890821 , version 1 (08-12-2022)


  • HAL Id : hal-03890821 , version 1


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


Gmail Facebook Twitter LinkedIn More