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

## Quantification vectorielle gloutonne (version longue)

(1)
1
Gilles Pagès
• Function : Author
• PersonId : 856726
• IdHAL : gilpag

#### Abstract

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.

#### Domains

Mathematics [math] Probability [math.PR]

### Dates and versions

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

### Identifiers

• HAL Id : hal-03890821 , version 1

### Cite

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

### Export

BibTeX TEI Dublin Core DC Terms EndNote Datacite

0 View