Harald Luschgy
email: luschgy@uni-trier.de

Gilles Pagès
email: gilles.pages@upmc.fr

Greedy vector quantization

Keywords: Optimal Vector Quantization, greedy optimization, distortion mismatch, Lloyd's I procedure, Competitive Learning Vector Quantization. 2010 AMS Classification: 60G15, 60G35, 41A25

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 |Xa 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.

Introduction and definition of greedy quantization sequences

Let p ∈ (0, +∞). We consider X : (Ω, A, P) → R d an L p -integrable random vector. For every Γ ⊂ R d , we define the L p -mean quantization error induced by Γ as the L p -mean of the distance of the random vector X to the subset Γ (with respect to a norm | . | on R d ) e p (Γ, X) = d(X, Γ) p . This quantity is always finite when X ∈ L p (P) since e p (Γ, X) ≤ X p + min a∈Γ |a| < +∞ owing to Minkowski's inequality. The usual L p -optimal quantization problem at level N ≥ 1 is to solve the following minimization problem e p,N (X) = min

Γ⊂R d ,|Γ|≤N e p (Γ, X)
where |Γ| denotes the cardinality of the subset Γ, sometimes called grid in Numerical Probability or codebook in Signal processing. The use of "min" instead of "inf" is justified by the fact (see Proposition 4.12 in [START_REF] Graf | Foundations of Quantization for Probability Distributions[END_REF], p.47 or [START_REF] Pagès | A space vector quantization method for numerical integration[END_REF]) that this infimum is always attained by an optimal quantization grid Γ (N ) (of full size N if the support of the distribution µ = P X of X has at least N elements).

The most celebrated result in Optimal (Vector) Quantization Theory is undoubtedly Zador's Theorem which rules the sharp asymptotic rate of convergence of e p,N (X) as the quantization level N (or grid size) goes to infinity. this quantization tree may exceed the storage capacity of the computing device. Using the induced grids a (N 0 ) , a (N 1 ) . . . , a (Nn) induced by a greedy optimal sequence (a N ) N ≥1 will dramatically reduce this drawback, provided that, on the other hand, their rate of decay of their mean quantization rates remain comparable to those of optimal quantizers. The paper is organized as follows: in Section 2, the existence of (L p , µ)-optimal greedy sequences and their first properties are established for general and Euclidean norms. In Section 3, (L p , µ)optimal greedy sequences are shown to be rate optimal in terms of mean quantization error, compared to sequences of L p (µ)-optimal N -quantizers. We also solve -positively -the so-called distortion mismatch problem i.e. the property that the above rate optimal decay property remains true for the L q (µ)-mean quantization error when q ∈ [p, p + d) in a d-dimensional setting (and sometimes for q = p + d). In Section 4, easy-to-check criterions, mostly borrowed from [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF], are adapted to our greedy framework. Section 5 is devoted to some further questions about the asymptotic behaviour of L p -greedy sequences, compared to L p -optimal N -quantizers or non-greedy L p -rate optimal sequences. In Section 6, we propose numerical procedures to compute quadratic optimal greedy sequences in both 1 and higher dimensional settings, either by deterministic means or by simulation. Finally, we propose in Section 7, when X is uniformly distributed on the unit hypercube [0, 1] d , a comparison between optimal greedy sequences and the sequences with low discrepancy popularized by the Quasi-Monte Carlo method. 2 Existence of optimal greedy quantization sequences Proposition 2.1. (a) Existence: If X ∈ L p (P), then the sequence of optimization problems (1.1) admits at least one solution (a N ) N ≥1 where a 1 is the L p -median of the distribution µ. Moreover, the finite sequence e p (a (n) , X) 1≤n≤N is (strictly) decreasing as long as N ≤ card supp(µ) . In particular, a n / ∈ a (n-1) , for n ∈ {1, . . . , N }. Any such a solution is called an L p -optimal greedy quantization sequence. (b) Local optimality: As long as N ≤ card supp(µ)

µ C a N (a (N ) ) > 0 where C a N (a (N ) ) = ξ ∈ R d | |ξ -a N | < min 1≤i≤N -1 |ξ -a i | and for any Borel set C such that C a N (a (N ) ) ⊂ C ⊂ W a N (a (N ) ) = ξ ∈ R d | |ξ -a N | ≤ min 1≤i≤N -1 |ξ - a i | , a N is solution to the local optimization problem a N ∈ argmin a∈R d E |X -a| p | X ∈ C .
(c) Space filling: Assume X ∈ L q R d (P) for some q ≥ p. Then, any L p -optimal greedy quantization sequence (a N ) N ≥1 satisfies lim N e q (a (N ) , X) = 0

i.e., equivalently, lim

N →+∞ R d min 1≤i≤N
|ξa i | q µ(dξ) = 0. In particular lim N e p (a (N ) , X) = 0.

Proof. (a) We proceed by induction. When N = 1, the existence of a 1 is obvious once noticed that ξ → E |X -ξ| p is continuous and goes to infinity as |ξ| → +∞. Assume there exists a 1 , . . . a N such that e p (a (k) , X) = min a∈R d e p (a (k-1) ∪ {a}, X) for every k ∈ {1, . . . , N }.

If supp(µ) ⊂ {a 1 , . . . , a N } then for every a ∈ R d , e p (a (N ) ∪ {a}, X) = e p (a (N ) , X). Otherwise, let ξ * ∈ supp(µ) \ {a 1 , . . . , a N }. It is clear that |ξξ * | < d(ξ, a (N ) ) on the ball B ξ * , 1 4 d(ξ * , a (N ) ) which satisfies µ B ξ * , 1 4 d(ξ * , a (N ) ) > 0. Consequently, e p (a (N ) ∪ {ξ * }, X) < e p (a (N ) , X). Now let

K 0 N +1 = ξ ∈ R d | e p (a (N ) ∪ {ξ}, X) ≤ e p (a (N ) ∪ {ξ * }, X) .
This is a closed non-empty set. Now let (ξ k ) k≥1 be a sequence of elements of K 0 N +1 such that |ξ k | → +∞. It follows from Fatou's Lemma that lim inf k e p (a (N )

∪ {ξ k }) p ≥ R d lim inf k d(ξ, a (N ) ) p ∧ |ξ -ξ k | p µ(dξ) = R d d(ξ, a (N ) ) p µ(dξ)
= e p (a (N ) , X) p > e p (a (N ) ∪ {ξ * }, X) p . This yields a contradiction which in turn implies that K 0 N +1 is a compact set. On the other hand ξ → e p (a (N ) ∪ {ξ}, X) is clearly Lipschitz continuous on R d , hence it attains its minimum on K 0 N +1 which is clearly its absolute minimum.

(b) If µ C a N (a (N ) ) = 0, then one checks that e p (a (N -1) , X) -e p (a (N ) , X) = Ca N (a (N ) ) d(ξ, a (N -1) ) p -|x -a N | p µ(dξ) = 0 which contradicts the strict decreasing monotony of e p (a (N ) , X). Let (C i ) 1≤i≤N be a Borel Voronoi partition of R d induced by a (N ) , i.e. satisfying C i ⊂ W a i (a (N ) ) = ξ ∈ R d | |ξ-a i | = min 1≤j≤N |ξ-a j | , and such that C N = C. Assume there exists b ∈ C such that C |ξ -a N | p µ(dξ) > C |ξ -b| p µ(dξ). Then e p (a (N ) , X) p = N -1 i=1 C i |ξ -a i | p µ(dξ) + C |ξ -a N | p µ(dξ) ≥ N -1 i=1 C i d ξ, a (N -1) ∪ {b} p µ(dξ) + C |ξ -a N | p µ(dξ) > N -1 i=1 C i d ξ, a (N -1) ∪ {b} p µ(dξ) + C |ξ -b| p µ(dξ) since µ(C) > 0 ≥ N -1 i=1 C i d ξ, a (N -1) ∪ {b} p µ(dξ) + C d ξ, a (N -1) ∪ {b} p µ(dξ) = e p (a (N -1) ∪ {b}, X) p
which contradicts the minimality of a N .

(c) Let p ∈ (0, +∞). It is clear that, for every ξ ∈ R d , min 1≤i≤N |ξa i | is non-increasing and converges toward inf

N ≥1
|ξa N | so that by the monotone convergence theorem, one has

e p (a (N ) , X) p ↓ ℓ ∞ := R d inf i≥1 |ξ -a i | p µ(dξ). Let a (∞) = {a N , N ≥ 1}. If ℓ ∞ = 0, then there exists ξ 0 ∈ supp(µ) such that ε 0 = d(ξ 0 , a (∞) ) > 0. Then, for every ξ ∈ B(ξ 0 , ε 0 4 ), d(ξ, a (∞) ) ≥ 3 4 ε 0 so that B(ξ 0 , ε 0 4 ) d ξ, a (∞) p µ(dξ) ≥ η 0 with η 0 = 3ε 0 4 p µ B ξ 0 , ε 0 4 .
Now, let N 0 be a positive integer such that,

R d d ξ, a (N 0 ) p µ(dξ) ≤ ℓ ∞ + η 0 2 1 - 1 3 p .
We consider the (N 0 + 1)-quantizer a (N 0 ) ∪ {ξ 0 }. On the one hand,

B(ξ 0 , ε 0 4 ) d ξ, {a 1 , . . . , a N 0 , ξ 0 } p µ(dξ) ≤ ε 0 4 p µ B ξ 0 , ε 0 4 = η 0 3 p
and, on the other hand

c B(ξ 0 , ε 0 4 ) d ξ, a (N 0 ) ∪ {ξ 0 } p µ(dξ) ≤ c B(ξ 0 , ε 0 4 ) d ξ, a (N 0 ) p µ(dξ) ≤ R d d ξ, a (N 0 ) p µ(dξ) - B(ξ 0 , ε 0 4 ) d ξ, a (N 0 ) p µ(dξ) ≤ ℓ ∞ + η 0 2 1 - 1 3 p -η 0 so that R d d ξ, a (N 0 ) ∪ {ξ 0 } p µ(dξ) ≤ ℓ ∞ + η 0 2 1 - 1 3 p -η 0 + η 0 3 p < ℓ ∞
which yields a contradiction. Hence ℓ ∞ = 0 which completes the proof for q = p.

Finally, we derive from what precedes that lim

N min 1≤i≤N |X -a i | = inf N ≥1 |X -a N | = 0 P-a.s.. As X ∈ L q (P), min 1≤i≤N |X -a i | ≤ |X -a 1 | ∈ L q ,
the conclusion follows from the Lebesgue dominated convergence theorem.

Remark on uniqueness. Uniqueness of L p -optimal greedy quantization sequence turns out to be quite different problem from its counterpart for regular L p -optimal quantization. Thus, for 1dimensional log-concave distributions, it is well-known that uniqueness of L p -optimal quantizers holds true (up to a reordering of the components in an increasing order) holds true. For L p -optimal greedy quantization, this uniqueness may fail. Basically, greedy quantization is more influenced by the symmetry properties of the distributions: thus for the N (0; 1)-distribution (whose density is log-concave), its is clear that a 1 = 0 (unique L p -median) but then we have that if a 2 is the (unique, see Proposition A.1 in Appendix A) solution to the the problem

min a≥0 E |X| p ∧ |X -a| p
where X has distribution µ = N (0; 1) then both a 2 and -a 2 are solutions to the greedy problem (1.1) at level N = 2 by symmetry of (the distribution of) X. In fact, one derives in turn that (0, a 2 , -a 2 ) and (0, -a 2 , a 2 ) are both the first three terms of (L p , N (0; 1)-optimal greedy quantization sequences.

2.1 About L p -optimal greedy quantization in an Euclidean framework Proof. We proceed by induction. Let a 1 ∈ argmin a∈R d E|X -a| p and let Π 1 (a 1 ) it projection on H µ .

If a 1 = π 1 (a 1 ), the pseudo-Pythagorus Theorem implies

∀ ξ ∈ H µ , |ξ -a 1 | 2 ≥ |ξ -π 1 (a 1 )| 2 + |a 1 -π 1 (a 1 )| 2 so that E |X -a| 2 ≥ E|X -π 1 (a 1 )| 2 + |a 1 -π 1 (a 1 )| 2 which yields a contradiction to the definition of a 1 . Hence a 1 ∈ H µ . Let a N ∈ argmin a∈R d e p (a (N -1) ∪{a}, X). It follows from Proposition 2.1(b) that a N ∈ argmin a∈R d E |X- a| p | X ∈ W a N where W a N = {ξ ∈ R d | |ξ -a N | ≤ d(ξ, a (N -1)
)} is a closed (polyhedral) convex set since the norm is Euclidean and has a positive µ-measure. As a consequence a N ∈ H µ(. |Wa N ) where µ(. |W a N ) is the conditional distribution of µ given W a N . One concludes by noting that

H µ(. |Wa N ) = H µ ∩ W a N ⊂ H µ .
Remark. Let p = 2. We know that µ(W a N ) > 0 as soon as card(supp(µ) ≥ N from Proposition 2.1(b) and that

argmin a∈R d Wa N |ξ -a| 2 µ(dξ) = Wa N ξ µ(dξ) µ(W a N ) i.e. a N = Wa N ξ µ(dξ) µ(W a N ) = E X | X ∈ W a N . (2.2)
This can be seen as a fixed point formula and is the starting point of stochastic optimization procedure to compute by simulation (of i.i.d. samples of X) of optimal greedy sequences (see Section 6).

3 Greedy quantization is rate optimal

A general rate optimality result

Following [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF], we define for every b ∈ (0, +∞) the b-maximal function associated to an L p -optimal greedy quantization sequence (a N ) N ≥1 by

∀ ξ ∈ R d , Ψ b (ξ) = sup N ≥1 λ d B(ξ, bd(ξ, a (N ) )) µ B(ξ, bd(ξ, a (N ) )) ∈ [0, +∞].
It is clear that Ψ b (ξ) > 0 for every ξ = a 1 (L p -median).

Note that this notion of b-maximal function (originally introduced in [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF]) can be naturally defined with respect to a sequence of grids (Γ N ) N ≥1 where Γ N has size N .

The theorem below yields a criterion based on the integrability of the maximal function Ψ b which implies that an (L p , µ)-optimal greedy quantization sequence is (L p , µ)-rate optimal (in the sense of Zador's Theorem). More practical criterions are given further on in Section 4. Theorem 3.1. Let p ∈ (0, +∞) and let µ = P X be such that R d |ξ| p µ(dξ) < +∞. Let (a N ) N ≥1 be an L p -optimal greedy quantization sequence. Assume that there exists b ∈ (0, 1 2 ) such that

Ψ b ∈ L p p+d (µ). Then lim sup N N 1 d e p (a (N ) , X) < +∞. (3.3)
Proof. First, note that if µ is a Dirac mass δ a for some a ∈ R d , then a 1 = a and e p (a (N ) , X) = 0 for every integer N ≥ 1. Otherwise, we rely on the following micro-macro inequality established in [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF] (see Equation (3.4) in the proof of Theorem 2, with the standard convention 1 0 = +∞).

∀ ξ ∈ R d , d(ξ, a (N ) ) p ≤ C p,b µ B(ξ, bd(ξ, a (N ) ))
e p (a (N ) , X) pe p (a (N ) ∪ {ξ}, X) p where b ∈ (0, 1 2 ) and C p,b is a positive real constant depending on p and b. Then, it follows that

e p (a (N ) ∪ {ξ}, X) p ≤ e p (a (N ) , X) p - 1 C p,b µ B(ξ, bd(ξ, a (N ) )) λ d B(ξ, bd(ξ, a (N ) )) b d d(ξ, a (N ) ) p+d V d (3.4)
where V d denotes the hyper-volume of the unit ball with respect to the current norm on

R d i.e. V d = λ d B | . | (0; 1) . This implies that e p (a (N ) ∪ {ξ}, X) p ≤ e p (a (N ) , X) p - 1 C p,b,d 1 Ψ b (ξ) d(ξ, a (N ) ) p+d (3.5)
where ∈ (0, +∞) is a normalizing real constant). Then, integrating the above inequality with respect to ν yields

C p,b,d = C p,b /(b d V d ) ∈ (0, +∞). Note that µ({a 1 }) < 1 since µ is not a Dirac mass, so that
R d e p a (N ) ∪ {ξ}, X p ν(dξ) ≤ e p (a (N ) , X) p -C p,b,d R d d(ξ, a (N ) ) p+d ν(dξ) Ψ b (ξ) .
Jensen's Inequality applied to the convex function u → u

1+ d p yields R d d(ξ, a (N ) ) p+d ν(dξ) Ψ b (ξ) ≥ R d d(ξ, a (N ) ) p ν(dξ) Ψ b (ξ) p p+d 1+ d p = κ 1+ d p b,p,d R d d(ξ, a (N ) ) p µ(dξ) 1+ d p = κ 1+ d p b,p,d e p a (N ) , X p+d .
On the other hand, it is clear that

e p a (N +1) , X p ≤ R d ν(dξ)e p a (N ) ∪ {ξ}, X)
p so that, finally, if we set A N = e p (a (N ) , X) p , N ≥ 1, this sequence satisfies for every integer N ≥ 1, the recursive inequality

A N +1 ≤ A N -κ A 1+ d p N
where κ = κ Remark. • A careful reading of the proof shows that, if we define the sequence of functions Ψ b,N by

∀ ξ ∈ R d , Ψ b,N (ξ) = λ d B(ξ, bd(ξ, a (N ) )) µ B(ξ, bd(ξ, a (N ) )) ∈ [0, +∞],
then the theorem holds true under the weaker assumption that there exists an integer N 0 ≥ 1 such that sup

N ≥N 0 R d Ψ b,N (ξ)µ(dξ) < +∞.
Unfortunately, this fact seems to be of little practical interest.

• When µ is singular with respect to the Lebesgue measure (no absolutely continuous part), it is likely that, like for standard optimal vector quantization in Zador's Theorem, this rate is not optimal. The natural conjecture should be that greedy quantization sequence(s) go to 0 at the same rate as that obtained for sequences of optimal quantizers which is not N -1 d when the distribution µ is singular (see e.g. [START_REF] Graf | Foundations of Quantization for Probability Distributions[END_REF]).

• Since we know that d(ξ, a (N ) ) ↓ 0 as N → +∞, µ(dξ)-a.s., it is clear that if µ = ϕ.λ d (or even µ = ϕ.λ d ⊥ + μ, to be checked), then by the Lebesgue differentiation theorem So, we retrieve here the statement of Remark 6.3(c), p.79, in [START_REF] Graf | Foundations of Quantization for Probability Distributions[END_REF] which points out that if optimal L p -mean quantization goes to zero at rate N -1 d then the above integral is finite (see also Section 1 in [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF]). Of course, as emphasized in Remark 6.3(a) from [START_REF] Graf | Foundations of Quantization for Probability Distributions[END_REF], p.79, the classical condition under which Zador's Theorem holds, namely E|X| p+δ = R d |ξ| p+δ µ(dξ) < +∞ for a δ > 0, implies the finiteness of this integral owing to an appropriate application of Hölder's inequality. The above result suggests a hopefully nonempty question: since L p -rate optimality for greedy sequence (and consequently for true L p -optimal quantizers) holds as soon as X ∈ L p (P) and ψ b (X) ∈ L p p+d (P) for a b ∈ (0, 1 2 ), are such conditions achievable when E|X| p+δ = +∞ for every δ > 0.

1 ϕ(ξ) = lim inf N λ d B(ξ, bd(ξ, a (N ) )) µ B(ξ, bd(ξ, a (N ) )) ≤ Ψ b (ξ) µ(dξ)-a.

Distortion mismatch for optimal greedy quantization sequences

In this section we address the problem of distortion mismatch originally investigated in [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF] for sequences of optimal N -quantizers.

If q ∈ (0, p] and X ∈ L p (P) any optimal greedy sequence (a N ) N ≥1 remains L q -rate optimal for the L q -norm owing to the monotony of the L q -norm as function of q. But the challenging question for distortion mismatch starts with the case q > p. It is solved in the proposition below, still relying on an integrability assumption on the b-maximal function(s) Ψ b . For more practical criterions we again refer to Section 4. Proposition 3.1. Let q ∈ (p, +∞) and let X ∈ L p (P) with distribution µ = P X . Assume that the maximal function Ψ b ∈ L q p+d (µ) for some b ∈ (0, 1 2 ). Let (a N ) N ≥1 be an L p -optimal greedy sequence. Then X ∈ L q (P) and lim sup

N N 1 d e q (a (N ) , X) < +∞.
Remarks. When supp(µ) is not compact it is hopeless to have results for q > p + d since it has been shown in [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF] (Theorem 10 and Equation (2.7)) that the L q -rate optimality of a sequence (a N ) N ≥1 would imply when

µ = ϕ.λ d that ϕ>0 ϕ -q p+d (ξ)µ(dξ) = ϕ>0 ϕ 1-q p+d (ξ)λ d (dξ) < +∞.
However when µ has a compact support, we will see in Proposition 4.2(c) that L q -rate optimality can be preserved under appropriate integrability assumptions.

Proof. First, note that if µ is a Dirac mass δ a for some a ∈ R d , then a 1 = a and e q (a (N ) , X) = 0 for every integer N ≥ 1. Otherwise, it follows from Equation (3.4) rewritten in a reverse way that

∀ ξ ∈ R d , d(ξ, a (N ) ) q ≤ C b,d,p,q e p (a (N ) , X) p -e p (a (N ) ∪ {ξ}, X) p q p+d Ψ b (ξ) q p+d (ξ). Now, we note that ∀ ξ ∈ R d , e p (a (N ) ∪ {ξ}, X) p ≥ e p (a (N +1) , X) p by definition of the sequence (a N ) N ≥1 so that ∀ ξ ∈ R d , d(ξ, a (N ) ) q ≤ C b,d,p,q e p (a (N ) , X) p -e p (a (N +1) , X) p q p+d Ψ b (ξ) q p+d (ξ).
Integrating with respect to µ yields e q (a (N ) , X) q ≤ C b,d,p,q e p (a (N ) , X) pe p (a (N +1) , X)

p q p+d R d Ψ b (ξ) q p+d (ξ)µ(dξ). We know that R d Ψ b (ξ)
q p+d (ξ)µ(dξ) ∈ (0, +∞) owing to the assumption made on µ and ψ b . Hence e q (a (N ) , X) q ≤ C b,d,p,q e p (a (N ) , X) pe p (a (N +1) , X)

p q p+d where C b,d,p,q = C b,d,p,q R d Ψ b (ξ) q p+d (ξ)µ(dξ). Equivalently e q (a (N ) , X) p+d ≤ C p+d q b,d,p,q e p (a (N ) , X) p -e p (a (N +1) , X) p . (3.6)
Summing over k between N and 2N -1 yields It is clear that Ψ b ∈ L p p+d (µ) since p < q and Ψ b ∈ L q p+d (µ). Consequently, combining the result established in Theorem 3.1 and Zador's Theorem on the sharp rate of decay of e p,N (X) in the scale N -1 d (see Theorem 6.2, p.78 in [START_REF] Graf | Foundations of Quantization for Probability Distributions[END_REF]), implies the existence of a positive real constant C ′ b,d,p,q ∈ (0, +∞) such that 1

2N -1 k=N e q (a (k) , X) p+d ≤ C p+d q b,d,p,q e p (a (N ) , X) p -e p (a (2N ) , X) p ≤ C p+d q b,d,p,q e p (a (N ) , X) p -e p,2N (
N 2N -1 k=N e q (a (k) , X) p+d ≤ C ′ b,d,p,q N -(1+ p d ) .
The convexity of u → u p+d then implies that

1 N 2N -1 k=N e q (a (k) , X) p+d ≤ C ′ b,d,p,q N -p+d d .
On the other hand the sequence e q (a (N ) , X) N ≥1 is clearly non-decreasing since (d(ξ, a (N ) ) q ) N ≥1 is non-decreasing for every ξ ∈ R d . This implies that

e q (a (2N ) , X) ≤ 1 N 2N -1 k=N e q (a (k) , X) ≤ κN -1 d .
Finally, still using that N → e q (a (N ) , X) is non-increasing, the announced result holds with κ =

κ b,d,p,q,X = max C 1 q b,d,p,q , X -a 1 q .
4 Practical criterions for the integrability of the maximal function

These criterions are mainly borrowed form [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF] where they have been established for the first time in order to solve the mismatch problem for optimal quantization

Compact case and q < p + d. The compact case relies on the following lemma which allows for non convex support for the distribution µ.

Lemma 4.1 (see Lemma 1 in [21]). If X ∈ L p (P) has a distribution µ and (Γ N ) N ≥1 is a sequence of N -quantizers such that R d d(ξ, Γ N ) p µ(dξ) → 0 then the maximal functions Ψ b associated to (Γ N ) N ≥1 lies in L r loc (µ) for every r ∈ (0, 1) i.e. ∀ r ∈ (0, 1), ∀ b ∈ (0, +∞), ∀R ∈ (0, +∞), {|ξ|≤R} ψ b (ξ) r µ(dξ) < +∞.
By combining this result (applied with r = q p+d ) with Proposition 2.1(b), we derive the following result which extends the one established in [START_REF] Brancolini | Long-term planning versus short term planning in the asymptotical location problem[END_REF] for absolutely continuous distributions with convex support on R d . Note that the proof of the above lemma is not elementary, especially when supp(µ) is not convex, and relies on the Besicovitch covering theorem. Proposition 4.1 (Compact support). If X has a distribution µ with compact support, then any L poptimal greedy quantization sequence (a N ) N ≥1 is L q -rate optimal for every q ∈ (0, p + d) i.e. satisfies lim sup

N N 1 d e q (X, a (N ) ) < +∞.
Compact case and q ≥ p + d. Results can be derived for q > p + d when µ is absolutely continuous and has a compact support. They rely on the following Lemma (see Lemma 2 in [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF]). Lemma 4.2. Assume µ = ϕ.λ d , E|X| p < +∞, supp(µ) is the finite union of closed convex sets and λ d|supp(µ) is absolutely continuous with respect to µ.

Let (Γ N ) N ≥1 be a sequence of quantization grids satisfying e p (Γ N , X) → 0 as N → +∞. Then, for every q ∈ (1, +∞], the associated maximal functions Ψ b lies in L q loc (µ) iff 1 ϕ ∈ L q loc (µ). As a consequence of this lemma, we derive the following proposition which deals with the cases q > p + d (in (a)) and q = p + d (in (b)). Proposition 4.2. (a) Let µ = ϕ.λ d be like in the preceding lemma and let (a N ) N ≥1 is an L p -optimal greedy quantization sequence for µ.

Let q > d + p. If R d ϕ -q d+p (ξ)µ(dξ) = {ϕ>0} ϕ 1-q d+p (ξ)λ d (dξ) < +∞ then (a N ) N ≥1 is L q ′ -
rate optimal for every q ′ ∈ (0, q] i.e.

lim sup N N 1 d e q ′ (X, a (N ) ) < +∞.
In particular, if ϕ ≥ ε > 0 on supp(µ), then the above integral criterion is fulfilled.

(b) Let q = p + d. If there exists δ > 0 such that R d ϕ -(1+δ) (ξ)µ(ξ) = {ϕ>0} ϕ -δ (ξ)λ d (dξ) < +∞ then lim sup N N 1 d e p+d (X, a (N ) ) < +∞.
Non-compact radial case. Let (Γ N ) N ≥1 be a sequence of N -quantizers such that e q (Γ N , X) → 0. If there exists a real constant c > 1 such that

R d ϕ(c ξ) -q p+d µ(dξ) = R d ϕ(c ξ) -q p+d ϕ(ξ)dξ < +∞ (4.8) then Ψ b ∈ L q p+d (µ).
In fact, as stated in [START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF], Corollary 3 is written to be used only with L p -optimal quantizers so the above formulation includes minor modifications. Combining this lemma with Proposition 2.1(b) and Theorem 3.1 yields the following proposition. Proposition 4.3 (Non-compact support with radial density). If X ∈ L p+δ (P) for some δ > 0 with an essentially radial distribution in the sense of (4.7). If, furthermore, ϕ satisfies (4.8), then any L p -optimal greedy sequence (a N ) N ≥1 is L q -rate optimal i.e. satisfies lim sup

N N 1 d e q (X, a (N ) ) < +∞.
This case includes e.g. all the centered hyper-exponential distributions of the form µ = ϕ.λ d with

ϕ(ξ) = κ a,b,c |ξ| c 0 e -a|ξ| b 0 , ξ ∈ R d , a, b > 0, c > -d
and | . | 0 is any norm on R d and subsequently all hyper-exponential distributions since L p -meanquantization errors is invariant by translation of the random vector X. In particular, this includes all normal and Laplace distributions.

Remark. In one dimension, (4.7) can be replaced mutatis mutandis by a one-sided variant: if there exists

R 0 , R ′ 0 ∈ R, R ′ 0 ≥ R 0 such that supp(µ) ⊂ [R 0 , +∞) and f |[R ′ 0 ,+∞) is non-increasing. (4.9)
This criterion is satisfied by the gamma distributions on R + (including the exponential distributions).

Non-compact and possibly non-radial case. Corollary 4.1. Assume µ = ϕ.λ d and E |X| p+δ < +∞ for some δ > 0. Furthermore, assume that supp(µ) is peakless in the following sense

κ ϕ := inf ξ∈supp(µ), 0<ρ≤1 λ d supp(µ) ∩ B(ξ, ρ) λ d B(ξ, ρ) > 0 (4.10)
and that ϕ satisfies the local growth control assumption:

there exist real numbers ε ≥ 0, η ∈ (0, 1 2 ), M, C > 0 such that ∀ ξ, ξ ′ ∈ supp(µ), ξ ≥ M, ξ ′ -ξ ≤ 2η ξ =⇒ ϕ(ξ ′ ) ≥ Cϕ(ξ) 1+ε . (4.11)
Then, for every q ∈ (0, p+d 1+ε ) such that

R d ϕ(ξ) - q(1+ε) p+d µ(dξ) = {ϕ(ξ)>0} ϕ(ξ) 1- q(1+ε)
p+d λ d (dξ) < +∞ (if any), any greedy L p -optimal sequence (a N ) N ≥1 is L q -rate optimal i.e. satisfies lim sup

N N 1 d e q (X, a (N ) ) < +∞.
In particular, if (4.11) holds either for ε = 0 or for every ε ∈ (0, ε] (ε > 0), and if

∀ q ∈ (0, p + d), R d ϕ(ξ) -q p+d µ(dξ) = {ϕ(ξ)>0} ϕ(ξ) 1-q d+p λ d (dξ) < +∞ (4.12)
then the above conclusion holds for every q ∈ (p, p + d).

Note that (if λ d (supp(µ)) = +∞) Assumption (4.10) is e.g. satisfied by any finite intersection of half-spaces, the typical example being R d + . Furthermore, a careful reading of the proof below shows that this assumption can be slightly relaxed into: there exists a real c > 0 such that

κ ′ ϕ := inf ξ∈supp(µ) λ d (supp(µ) ∩ B(ξ, ρ)) λ d (B(ξ, ρ)) , 0 < ρ ≤ c x > 0.
5 Further answers and questions about greedy quantization

In this section, we temporarily denote by a N,p N ≥1 the L p -optimal greedy quantization sequence for the uniform distribution U ([0, 1]) and by α (N ),p N ≥1 the resulting sequence of greedy quantizers.

⊲ Rate optimality of greedy sequences It is a straightforward consequence of Zador's Theorem that if the distribution µ = P X of X ∈ L p+δ , δ > 0, has a non-zero absolutely continuous component (i.e. ϕ = dµ dλ d ≡ 0) and satisfies the assumptions of Theorem 3.1, then ⊲ Can greedy quantization sequence produce asymptotically optimal quantizers? If µ has an absolutely continuous component with density ϕ, then any sequence (Γ n ) n≥1 of asymptotically (L p , µ)-optimal quantization grids at level N n = card(Γ n ) → +∞, satisfies the empirical measure theorem (see [START_REF] Graf | Foundations of Quantization for Probability Distributions[END_REF], Theorem 7.5, p.96 and [START_REF] Delattre | Quantization of probability distributions under norm-based distortion measures[END_REF] for a slight refinement), namely

e p (a (N ),p , X) ≍ N -1 d since e p (a (N ),p , X) ≥ e p,N (
1 N n a∈Γn δ a (w) -→ µ (p) = ϕ d d+p R d ϕ d d+p dλ d .λ d as n → +∞ where (w)
-→ denotes the weak convergence of probability measures. Note that when µ = U ([0, 1]), µ (p) = U ([0, 1]), for every p ∈ (0, +∞).

By asymptotically (L p , µ)-optimal, we mean that the (L p , µ)-mean quantization errors induced by the grids Γ n satisfy the sharp asymptotics of Zador's Theorem, namely lim n N

1 d n e p (Γ n , X) = J p,d ϕ 1 p L p p+d (λ d )
.

It is pointed out in [START_REF] Brancolini | Long-term planning versus short term planning in the asymptotical location problem[END_REF] (Theorem 4.10 and Corollary 4.11) that the quantizers (a (N ),p ) N ≥1 designed from an (L p , µ)-optimal greedy quantization sequence (a N,p ) N ≥1 are usually not asymptotically (L p , µ)optimal, even up to an extraction. The counter-example is exhibited in the 1-dimensional basic setting of the uniform distribution U ([0, 1]).

The authors first build and analyze an (L 1 , U ([0, 1]))-optimal greedy sequence (a N,1 ) N ≥1 . Then, they shown that the (tight) sequence of empirical measures µ N = 1 N 1≤k≤N δ a k,1 on [0, 1] does not have the uniform distribution U ([0, 1]) (or equivalently the Lebesgue measure λ 1|[0,1] over [0, 1]) as a weak limiting distribution. In particular, this implies, owing to the above empirical measure theorem, that lim inf

N e 1 a (N ),1 , U ([0, 1]) > 1 4 = J 1,1 keeping in mind that J 1,1 = lim N e 1,N U ([0, 1]) = inf N e 1,N U ([0, 1]
) . Otherwise, by the above empirical mean theorem, there would exists a subsequence

N ′ → +∞ such that µ N ′ (w) → µ (1) = λ 1|[0,1] = U ([0, 1]). Equivalently, this reads lim inf N e 1 a (N ),1 , U ([0, 1]) e 1,N U ([0, 1]) > 1.
Numerical tests graphically reproduced in [START_REF] Brancolini | Long-term planning versus short term planning in the asymptotical location problem[END_REF] (Figure 1, p.521) suggest that lim inf

N N e 1 a (N ),1 , U ([0, 1]) ≈ 1, 02 × J 1,1 .
Our own numerical tests, based on the algorithms developed in Section 6 in the quadratic case (p = 2), implemented with the uniform distribution, the scalar N (0, 1) and bi-variate N (0; I 2 ) normal distributions provide similar conclusions (see Section 6 devoted to algorithmic aspects and numerical experiments).

This leads to our first open question: is this a generic situation? Or, to be more precise:

Open question 1: May an optimal (L p , µ)-greedy sequence (a N,p ) N ≥1 contain subsequence(s) a (N ′ ),p N ≥1

of asymptotically (L p , µ)-optimal µ-quantizers?

In fact, we conjecture that the a generic answer is negative. This amounts to proving, still owing to the empirical measure theorem, that for any optimal (L p , µ)-greedy sequence (a N,p ) N ≥1 lim inf N e p a (N ),p , µ e p,N µ > 1.

⊲ Are (L p , µ)-optimal greedy quantization sequence really optimal among (µ-rate optimal) sequences? Let us have a look at the celebrated dyadic Van der Corput (VdC ) sequence, viewed as a quantization sequence. Let us recall that the dyadic VdC sequence is defined by

ξ N = r k=0 n k 2 k+1 where N = n r 2 r + • • • + n 0 , n i ∈ {0, 1}, i = 1, . . . , r.
⊲ The L 1 -mean quantization problem for the VdC sequence. Elementary computations, not reproduced here, show that lim inf

N N e 1 ξ 1 , . . . , ξ N , [0, 1] = 1 4 = J 1,1
and that lim sup

N N e 1 ξ 1 , . . . , ξ N , [0, 1] = 9 32 = 9 8 J 1,1 .
This lim inf is achieved by the subsequence N n = 2 n-1 , n ≥ 1, and the lim sup with subsequence

N n = 3 2 .2 n = 3.2 n-1 , n ≥ 1.
So we can claim that:

• there exist rate optimal sequences in the sense of (3.3) which are not solutions to the greedy problem (1.1);

• there exist rate optimal sequences (ξ N ) N ≥1 containing subsequence of quantizers (ξ (N ′ ) ) N ≥1 which are asymptotically L 1 -rate optimal quantizers: so is the case of the VdC sequence with the above subsequence N ′ = 2 n-1 .

Figure 1 in [START_REF] Brancolini | Long-term planning versus short term planning in the asymptotical location problem[END_REF] also suggests that the L 1 -optimal greedy quantization sequence a N,1 N ≥1 for the uniform distribution U ([0, 1]) satisfies lim sup ⊲ The L 2 -mean quantization problem for the VdC sequence. The same phenomenons are confirmed in the quadratic case since, mutatis mutandis,

N N e 1 a (N ),1 , U ([0, 1]) ≈ 1.09 × J 1,
lim inf N N e 2 ξ 1 , . . . , ξ N , [0, 1] = 1 2 √ 3 = J 2,1 and lim sup N N e 2 ξ 1 , . . . , ξ N , [0, 1] = 3 √ 5 4 × J 2,1
where we keep in mind that J 2,1 = lim

N N e 2,N (U ([0, 1])) = inf N N e 2,N (U ([0, 1])).
On the other hand, in a quadratic framework, using the greedy Lloyd I procedure described and analyzed in the next Section 6.1 (see Equations (6.14) if d = 1 and (6.17) if d ≥ 2), we also observe numerically (see Figure 5) that lim inf

N N e 2 (a (N ),2 , U ([0, 1])) ≈ 1.02732 × J 2,1 > J 2,1 and lim sup N N e 2 a (N ),2 , U ([0, 1]) ≈ 1.13401 × J 2,1 .
As for the lim inf, we verify again that no subsequence of a (N ),2 N ≥1 can be asymptotically L 2optimal and, ss for the lim sup, that the quadratic optimal greedy sequence a N,2 N ≥1 outperforms the dyadic VdC sequence from the lim sup criterion since 1.13401 < 3 √ 5 4 = 1.67706. ⊲ Concatenated sequences. From a more general point of view, there is a canonical method to produce for any distribution µ on (R d , Bor(R d )), a µ-rate optimal sequence for (L p , µ)-quantization by concatenating (L p , µ)-optimal grids of size 2 ℓ . We proceed as follows. Let (b N ) N ≥1 be a sequence made up with (L p , µ)-optimal quantizers at level 2 ℓ , ℓ = 0, . . . n -1 i.e. so that b 2 ℓ , . . . , b 2 ℓ+1 -1 is an (L p , µ)-optimal quantizer at level 2 ℓ .

(5.13)

One checks straightforwardly by monotony of the L p -mean quantization error that, for every n ≥ 1,

e 2 n -1 (b (2 n -1) , µ) ≤ e 2 n-1 {b 2 n-1 , . . . , b 2 n -1 }, µ .
Hence, for every N ≥ 1, let be n = n(N ) be such that 2 n -1 ≤ N ≤ 2 n+1 . Then

e p (b (N ) , µ) ≤ e p ({b 2 n-1 , . . . , b 2 n -1 }) = e p,2 n-1 (µ) so that lim sup N N 1 d e p (b (N ) , µ) ≤ lim sup N N 2 n(N ) 1 d lim N N 1 d e p,N (µ) = 2 1 d lim N N 1 d e p,N (µ).
⊲ First elements of comparison.

-If µ = U ([0, 1]) and p = 1, one easily checks by induction that the dyadic VdC sequence can be obtained as a properly reordered sequence (b N ) N ≥1 from the L p -optimal quantizers at level N given by 2k-1 2N , 1 ≤ k ≤ N when N = 2 n , n ≥ 0. In this very situation, the factor 2 1 d = 2 is conservative since it can be replaced when p = 1 by 9 8 = 1.125 as seen above. Anyway, the L 1 -optimal greedy quantization sequence keeps the lead, since lim sup

N e 1 (a (N ),1 , µ) e 1,N (µ) ≈ 1.09 < 9 8 ≈ 1.125.
-If µ = U ([0, 1]) and p = 2, once again, the quadratic optimal greedy quantization sequence again keeps the lead, since

lim sup N e 2 (a (N ),2 , µ) e 2,N (µ) ≈ 1.13401 < 3 √ 5 4 ≈ 1.67706 < 2.
-If µ = N (0; I 2 ) (bivariate normal distribution i.e. d = p = 2), our own numerical experiments suggest for the third time (see more detailed numerical results in Section 6.2) that a quadratic optimal greedy quantization sequence (or, in practice, the suboptimal sequence resulting from the numerical implementation of the greedy Lloyd I algorithm) has a lower constant than 2 ⊲ Practical aspects in view of numerics. From a more applied point of view, it would be of interest to establish for (L p , µ)-optimal greedy sequences a counterpart of the non-asymptotic Zador Theorem in order to upper-bound the (L p , µ)-mean quantization error of any greedy optimal sequence (normalized by N -1 d ) by the L p+δ -pseudo-standard deviation of the distribution µ and a universal constant depending only on d, p and δ. The proof of the non-asymptotic Zador's Theorem (a slight improvement of Pierce's Lemma established e.g. in [START_REF] Luschgy | Functional quantization rate and mean regularity of processes with an application to Lévy processes[END_REF]) relies on a random quantization argument involving the random quantizers (Y (N ) ) N ≥1 designed from an i.i.d. sequence (Y N ) N ≥1 with an appropriate distribution ν, such a result is not hopeless.

1 d × lim N N
For numerical purposes, in particular numerical integration or conditional expectation approximation, some reasonably good estimates of lim sup N N 1 d e 1,N (a (N ) , µ) in (3.3) would be very useful. This is to be compared to the never ending quest for sequences with low discrepancy with lower constant in the Quasi-Monte Carlo community.

Algorithmic aspects in the quadratic case

In this section we assume that R d is equipped with the canonical Euclidean norm and that p = 2 (purely quadratic setting). So, will simply denote (a N ) N ≥1 quadratic optimal greedy sequences.

Practical computation of an optimal greedy sequence of quantizers relies on obvious variants algorithms (CLV Q and Lloyd) implemented recursively: to switch from N to N + 1, one first adds a (N + 1) th point (sampled from the support of the distribution µ) to the N -tuple (a 1 , . . . a N ) computed during the first N th stages of the optimization procedure. This makes the starting (N + 1)-tuple for the modified CLV Q to Lloyd procedure. Then, one launches one of these two optimization procedures with the following restriction: all formerly computed components a i , 1 ≤ i ≤ N -1 are kept frozen, and only the new point is moved following the standard rules. Thus, if implementing a CLV Q like procedure, when the N th component is the "winner" in the competition phase (i.e. the N th component is the nearest neighbour to the new input stimulus). As for the (randomized) Lloyd I procedure, the Voronoi cell of the N th component is the only one whose centroid (the N th component) is updated, the other N -1 components remaining frozen as well. Let us be more precise.

The one-dimensional quadratic case

When d = 1 and the distribution µ is absolutely continuous with a continuous positive probability density ϕ on the real line, one can directly consider the counterpart of the historical deterministic Lloyd I procedure and of the gradient descent sometimes known as Forgy's algorithm or k-means. Let us be more specific.

⊲ Greedy Lloyd's I procedure • Assume a 1 , . . . a N -1 have been computed. Let a (N -1) 1 < • • • < a (N -1)
N -1 be an increasing reordering of a 1 , . . . , a N -1 .

• Assume the N inter-point local inertia has also been computed, namely

σ 2 i := a (N -1) i+ 1 2 a (N -1) i |a (N -1) i -ξ| 2 µ(dξ) + a (N -1) i+1 a (N -1) i+ 1 2 |a (N -1) i+1 -ξ| 2 µ(dξ), i = 1, . . . , N where
a (N -1) 0 = a (N -1) 1 2 = -∞, a (N -1) i-1 2 = a (N -1) i-1 + a (N -1) i 2 , i = 2, . . . , N -2, a (N -1) N -1 2 = a (N -1) N = +∞. • Choose an index i 0 = i 0 (N -1) such that σ 2 i 0 = max 0≤i≤N σ 2 i (maximal local inertia), then consider a 0 = a N,0 ∈ (a (N -1) i 0 , a (N -1) i 0 +1
) and finally define recursively a sequence a

[n] = a N,n , n ≥ 1, by a [n+1] = E X | X ∈ W N,[n] = K µ a (N -1) i 0 +1 +a [n] 2 -K µ a (N -1) i 0 +a [n] 2 F µ a (N -1) i 0 +1 +a [n] 2 -F µ a (N -1) i 0 +a [n] 2
, n ≥ 0, (6.14) where F µ (x) = µ((-∞, x]) is the cumulative distribution function of µ and K µ its cumulative first moment function defined by

K µ (x) = (-∞,x] ξ µ(dξ), x ∈ R.
It follows form an easy induction that, at every step n ≥ 0 of the procedure,

a N,[n] ∈ W N,[n] ⊂ (a (N -1) i 0 , a (N -1) i 0 +1
) so that the procedure is well-defined.

Proposition 6.1. If µ is strongly unimodal in the sense that µ = ϕ.λ 1 with ϕ : R → R log-concave, then a N,[n] converges toward the unique solution a N,∞ ∈ (a

(N -1) i 0 , a (N -1) i 0 +1
) of the fixed point equation

a N = E X | X ∈ W N (6.15)
where W N ⊂ (a

(N -1) i 0 , a (N -1) i 0 +1
) is the closed Voronoi cell of a N in a (N -1) ∪ {a N }. The detailed proof is postponed to the Appendix A.1. But we can already mention that it relies on classical arguments called upon in the proofs of the convergence of the standard Lloyd I procedure (and the uniqueness of the possible stationary limiting point, see [START_REF] Kieffer | Exponential rate of convergence for Lloyd's method I[END_REF][START_REF] Bouton | Self-organization and a.s. convergence of the one-dimensional Kohonen algorithm with non-uniformly distributed stimuli[END_REF]).

Remarks. • The computation of the integrals involved in the algorithm can be performed by higher order quadrature formulas, or e.g. in the case where µ = N (0; 1) using the closed form for

x -∞ ξe -ξ 2 2 dξ √ 2π = -e -x 2 2 √
2π and high accuracy approximations for its cumulative distribution function Φ 0 , using e.g. continuous fractions expansions (see [START_REF] Abramovicz | Handbook of Mathematical Functions[END_REF]).

• The log-concave assumption which implies the uniqueness of the fixed point for Equation (6.14), is satisfied by many usual families of distributions on the real line like e.g. the normal distributions N (m; σ 2 ), the exponential and Laplace distributions, the γ(α, β)-distributions, α ≥ 1, β > 0, are strongly unimodal. On the other hand, the Pareto distributions are not strongly unimodal though uniqueness holds true (see [START_REF] Fort | Asymptotics of optimal quantizers for some scalar distributions[END_REF]).

⊲ Greedy Forgy's algorithm (Newton zero search algorithm) This procedure is defined recursively by

a [n+1] = a [n] -γ n+1 ∧ 1 ρ(a [n] ) a (N -1) i 0 +1 +a [n] 2 a (N -1) i 0 +a [n] 2 a [n] -ξ µ(dξ) (6.16)
where γ n+1 ∈ (0, 1) goes to 0 as n → +∞, n γ n = +∞ and

ρ(a) = µ a (N -1) i 0 + a 2 , a (N -1) i 0 +1 + a 2 + a -a (N -1) i 0 2 f a + a (N -1) i 0 2 + a (N -1) i 0 +1 -a 2 f a + a (N -1) i 0 +1 2 > 0 is the second derivative of the a function a → E min |X -a i | 2 ∧ |X -a| 2 .
Note that, owing to the thresholding of 1/ρ(a N,[n] ) by γ n+1 ∈ (0, 1), this procedure lives in the interval (a

(N -1) i 0 , a (N -1) i 0 +1
) which makes it well-defined and consistent for every n. When µ is not absolutely continuous, one can implement the same procedure by removing the term involving the second derivative with a step γ n satisfying the standard decreasing step assumption ( n γ n = +∞ and n γ 2 n < +∞), provided one can compute the µ-integrals of interest.

⊲ Numerical illustration with the N (0; 1) distribution To compute a quadratic optimal greedy sequence of the normal distribution µ = N (0; 1), we will take advantage of its symmetry. To this end we consider the distribution μ = µ( . | R + ) (µ conditioned to stay non-negative) which is clearly strongly unimodal and we compute by induction its quadratic optimal greedy sequence ( a N ) N ≥1 by the greedy Lloyd I procedure (6.14) with the convention that the origin 0 is a fixed but active point for this slight variant . By active we mean that 0 has its own Voronoi cell in R + or, equivalently, that we implement our computation starting at a 0 = 0 at N = 0. As a second step, it is straightforward that the sequence defined by

a 0 = 0, a 2N -1 = a N , a 2N = -a N , N ≥ 1,

The multidimensional quadratic case (higher dimensions)

In higher dimensions, deterministic procedures like deterministic greedy Lloyd's I (fixed point procedure defined by (6.14)) or the greedy Forgy's (recursive zero search defined by (6.16)) algorithms become computationally too demanding due to the repeated computations of integrals on the Voronoi cells of the quantizers. So, it becomes necessary, at least when d ≥ 3, to switch to stochastic optimization procedures like those described below, which are adaptations of the stochastic procedures introduced to compute true optimal N -quantizers. For more details about these original stochastic optimization procedures, mostly devised in the 1950's, we refer e.g. to [START_REF] Benveniste | Algorithmes adaptatifs and approximations stochastiques[END_REF][START_REF] Pagès | Functional quantization for numerics with an application to option pricing[END_REF] for CLV Q and [START_REF] Kieffer | Exponential rate of convergence for Lloyd's method I[END_REF][START_REF] Du | Centroidal Voronoi tessellations: Applications and algorithms[END_REF][START_REF] Pagès | Pointwise convergence of the Lloyd algorithm in higher dimension[END_REF] for (randomized) Lloyd's I procedure or more applied textbooks like [START_REF] Gersho | Vector Quantization and Signal Compression[END_REF]. From a theoretical point of view, their common feature is that the convergence results (a.s. or in L p ) remain partial, especially little is known when the distribution µ is not compactly supported. So we present below their greedy variants (without rigorous proof as concerns CLV Q). From a practical point of view, for both procedures, the computation of integrals on the Voronoi cells is replaced by repeated nearest neighbor searches among the components of the current N -quantizers which make them rather slow. But in our greedy framework, this drawback could be overcome by appropriate localization around the elementary quantizer of interest. But this is beyond the scope of the present work.

⊲ (Randomized) greedy Lloyd's I like procedure. The greedy Lloyd I procedure to compute a N , assuming that a (N -1) is known, (starting from the mean a 1 = E X) can be recursively defined in the quadratic case as follows:

a N,[n+1] = E X | X ∈ W N,[n] , a N,[0] ∈ R d \ {a (N -1) }, (6.17)
where W N,[n] is the closed Voronoi cell of a N,[n] with respect to the quantizer a (N -1) ∪ {a N,[n] }. Of course in practice, we stop the Monte Carlo simulation at finite range M n .

We establish in the proposition below, at least for absolutely continuous distributions with convex support, that lim n→+∞ a N,[n] does exists under a local finiteness assumption on the possible equilibrium points. Due to the existence of several equilibrium points, especially in higher dimension, this limit may not be the solution to the greedy optimization problem at level N , but only a local minimizer. However, in practice, it turns out to be a good candidate. Proposition 6.2. Assume the distribution µ of X is strongly continuous (i.e. assigns no mass to hyperplanes) with a convex support denoted C µ = supp(µ). Then the above sequence (a N,[n] ) n≥0 is bounded and there exists ℓ ∈ e 2 (a (N ) ), e 2 (a (N -1) ∪ {a [0] } such that the set A ∞ (a [0] ) of its limiting points is a connected compact subset of the set Λ ℓ of ℓ-stationary points defined by

Λ ℓ = a ∈ R d | e 2,N a (N -1) ∪ {a} = ℓ and a = E X | X ∈ W N,a
where W N,a denotes the closed Voronoi cell of a induced by the N -quantizer a (N -1) ∪{a}. In particular, e 2 a (N -1) ∪ {a [n] }, X → ℓ as n → +∞. Furthermore, if the ℓ-stationary set Λ ℓ is locally finite (i.e. with a finite trace on compact sets of R d ), then a N,[n] a.s. converges to some point in Λ ℓ .

The proof is postponed to Appendix A.2.

The true algorithm to be implemented in practice is a randomized version of this procedure where each conditional expectation is computed by Monte Carlo simulation (provided X can be simulated at a reasonable cost): let (X m ) m≥1 be an i.i.d. sequence of copies of X (with distribution µ) defined on a probability space (Ω, A, P). Then, by the Strong Law of Large Numbers,

a N,[n+1] = lim M →+∞ M m=1 X m 1 {X m ∈W N,[n] } M m=1 1 {X m ∈W N,[n] } P-a.s.
⊲ Sequential Competitive Learning Vector Quantization procedure: Let (γ n ) n≥1 be a sequence of (0, 1)-valued step parameters satisfying a so-called decreasing step assumption:

n γ n = +∞ and n γ 2 n < +∞. Then set a N,[n+1] = a N,[n] -γ n+1 1 {|X n+1 -a N,[n] |<min a∈a (N -1) |X n+1 -a|} a N,[n] -X n+1 , a N,[0] ∈ R d .
One may conjecture and experimentally check, at least for distribution with compact convex support,

lim n→+∞ a N,[n] = a N .
If so is the case, one may apply the so-called Ruppert-Polyak principle which states that choosing a "slowly decreasing" step of the form γ n = c c+n α , 1 2 < α < 1, and averaging the procedure by setting

āN,[n] = 1 n a [N,0] + • • • + a [N,n-1] , n ≥ 1,
will speed up the convergence or, to be more precise, will satisfy a Central Limit Theorem at rate √ n with the lowest possible asymptotic variance (see e.g. [START_REF] Luschgy | Martingale in diskreter Zeit, Theorie und Anwendungen Reihe[END_REF][START_REF] Pagès | Introduction to Numerical Probability and Applications to Finance[END_REF] for details).

⊲ Randomized Greedy Lloyd's I randomized procedure for the bi-variate normal distribution Let µ = N (0; I 2 ) be the bi-variate normal distribution on the plane. Figure 3 below depicts the graph of N → √ N e 2 a (N ) , µ for N = 1 up to 1 000 (and Figure 4 depicts a (1000) ). This suggests that this sequence remains bounded. However, we are not sure with such a rough procedure that the computed sequence (a N ) N ≥1 is the optimal greedy one: at each step/level, there are clearly many local parasitic minima and one should add, prior to computing a N , a pre-processing phase, like in one dimension, in order to choose among the areas defined by the Delaunay triangulation attached to a (N -1) , the one which induces the minimal inertia. But this phase is numerically demanding and has not yet been included in the existing script.

The randomized Lloyd 1 has been implemented at each level N with M = M (N ) = 1 000 × N i.i.d. simulations of the N (0; I 2 ) distribution. Following Zador's Theorem lim

N √ N e 2,N N (0; I 2 ) = 2 √ 2π J 2,2 = 2 3 5 π √ 3 ≈ 2.0077
since, owing to [START_REF] Graf | Foundations of Quantization for Probability Distributions[END_REF] (Theorem 8.15, p.120, and Examples 8.12, p.116, devoted to hexagon lattices),

J 2,2 = 1 3 5 2 √ 3 .
The "loss" is less than 10 %. We verify on our own numerical experiments carried out with N = 1000 that it is likely that sup

1≤N ≤1000 √ N e 2 a (N ) , N (0; I 2 ) 2.18.
As already mentioned, it suggests again that the greedy quantization sequence outperforms the concatenated sequence (5.13) since 2.18

< √ 2 × 2 3 5 π √ 3 ≈ 2.
8392 (even if one may guess that the factor 2

1 d = √ 2 is probably too conservative in practice).
7 Greedy quantization versus Quasi-Monte Carlo?

Of course, for every integer N ≥ 1, the weights induced by the µ-mass of the Voronoi cells associated to a (N ) define canonically a sequence of N -tuples which usually cannot be "arranged" into a sequence, even up to a re-scaling. When considering the unit hypercube [0, 1] d as a state space in d dimension, it is easy natural to compare an optimal greedy sequence with respect to the uniform distribution U ([0, 1] d ) and the so-called uniformly distributed sequences usually implemented in the Quasi-Monte Carlo method.

Let us recall that a sequence (ξ k ) k≥1 is uniformly distributed over [0, 1] d if the empirical measures

ν N = 1 N N i=1
δ ξ i weakly converges toward the Lebesgue measure λ d on [0, 1] d . In particular this means that for every bounded dξ-a.s. continuous function f : The answer is essentially log N and si provided by Proinov's theorem (see [START_REF] Proinov | Discrepancy and integration of continuous functions[END_REF]) recalled below which evaluates precisely the convergence rate of empirical measures of uniformly distributed sequences on Lipschitz functions.

[0, 1] d → R, 1 N N i=1 f (ξ i ) → [0,1] d f (
In the Quasi-Monte Carlo (QM C) method, the performance of an N -tuple (ξ 1 , . . . , ξ N ) ∈ ([0, 1] d ) N is measured by the Kolmogorov-Smirnov distance between the extended cumulative distribution function of its empirical measure 1 N 1≤i≤N δ ξ i and the uniform distribution U ([0, 1] d ), namely the socalled star discrepancy defined by

D * N (ξ 1 . . . , ξ N ) = sup x∈[0,1] d 1 N N i=1 1 {ξ i ∈[[0,u]]} -λ d [[0, u]] (7.18)
where [[0, u]] = d ℓ=1 [0, u ℓ ], u = (u 1 , . . . , u d ). Several sequences ξ = (ξ N ) N ≥1 have been exhibited (see [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF]) whose star discrepancy at the origin satisfies for a real constant C(ξ) ∈ (0, +∞),

∀ N ≥ 1, D * N (ξ 1 . . . , ξ N ) ≤ C(ξ) (1 + log N ) d N . (7.19)
Among them one can cite the p-adic VdC(p) sequences (p ≥ 2 in 1-dimension) and, when d ≥ 2, the Halton sequences (whose i th component is the VdC(p i ) sequence where the "basis" p i , i = 1, . . . , d, are the first d prime numbers), the Faure sequences, the Sobol' sequences (a unifying framework has been developed by Niederreiter, see e.g. [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF]). For definitions of these sequences and numerical tests on various problems we refer to [START_REF] Bouleau | Numerical methods for stochastic processes[END_REF][START_REF] Pagès | Sequences with low discrepancy and pseudo-random numbers : theoretical results and numerical tests[END_REF]. Although such a rate has never been proved to be the lowest possible, this opinion is commonly shared by the QM C community (however see again [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF] or [START_REF] Pagès | Introduction to Numerical Probability and Applications to Finance[END_REF] for a review of existing lower bounds).

The striking fact with these sequences satisfying (7.19), called sequences with low discrepancy, is that when they are implemented on the class of functions with finite variation on [0, 1] d the Koksma-Hlawka inequality implies that, for every such function f :

[0, 1] d → R 1 N N k=1 f (ξ k ) - [0,1] d f dλ d ≤ V (f )D * N (ξ 1 . . . , ξ N ) (7.20)
where V (f ) denotes the variation of the function f . So it induces for this specific class of functions a rate of numerical integration of order O (log N ) d

N

. In one dimension (d = 1), However, the above notion of finite variation coincides with the standard definition of finite variation in real analysis.

When d ≥ 2, several definitions can be given, the most popular being the finite variation in the Hardy & Krause sense (as described e.g. in [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF]). Another slightly less general -but more elementarybeing the finite variation in the signed measure sense developed in [START_REF] Bouleau | Numerical methods for stochastic processes[END_REF] (see also [START_REF] Pagès | Introduction to Numerical Probability and Applications to Finance[END_REF]). Unfortunately, as the dimension d increases, the set of functions with finite variation (in any of the above senses) becomes somewhat "sparse" among the set of all real-valued Borel functions defined on [0, 1] d . So this striking behavior may be considered as not significant when dealing with practical simulation problems. However to carry out a comparison, we need to evaluate their performances the same significant functional space, namely that of Lipschitz continuous. The Proinov theorem below provides an answer.

ξ,ξ ′ ∈[0,1] d , |ξ-ξ ′ | ∞ ≤δ |f (ξ) -f (ξ ′ )|. (a) Let (ξ 1 , . . . , ξ N ) ∈ ([0, 1] d ) N . For every continuous function f : [0, 1] d → R, [0,1] d f (x)dx - 1 N N i=1 f (ξ i ) ≤ C d w f, D * N (ξ 1 , . . . , ξ N ) 1 d
where C d ∈ (0, ∞) is a universal optimal real constant only depending on d. In particular, if the function f

: [0, 1] d → R is ℓ ∞ -Lipschitz continuous with coefficient [f ] Lip := sup x,y∈[0,1] d |f (x)-f (y)| |x-y|∞ , then [0,1] d f (x)dx - 1 N N i=1 f (ξ i ) ≤ C d [f ] Lip D * N (ξ 1 , . . . , ξ N ) 1 d . If d = 1, C d = 1 and if d ≥ 2, C d ∈ [1, 4].
(b) In particular if (ξ N ) N ≥1 is a sequence with low discrepancy in the above sense, then

[0,1] d f (x)dx - 1 N N i=1 f (ξ i ) ≤ C d [f ] Lip C(ξ) 1 + log N N 1 d . Corollary 7.1. (a) For every N -tuple (ξ 1 , . . . , ξ N ) ∈ ([0, 1] d ) N e 1 ξ 1 , . . . , ξ N , U ([0, 1] d ) ≤ C d D * N (ξ 1 , . . . , ξ N ) 1 d . (b) In particular, when d = 1, e 1 ξ 1 , . . . , ξ N , U ([0, 1]) ≤ D * N (ξ 1 , . . . , ξ N ). Proof (of (b)). Assume d = 1. The function f ξ : u → min 1≤i≤N |u -ξ i | defined on [0, 1] is 1-Lipschitz continuous, hence has finite variation with V (f ξ ) = 1 .
Then Koksma-Hlawka Inequality (7.20) or Proinov's error bound in (a) both imply that

e 1 ξ 1 , . . . , ξ N , U ([0, 1]) = 1 N N i=1 f ξ (ξ i ) -e 1 ξ 1 , . . . , ξ N , U ([0, 1]) = D * N (ξ 1 , . . . , ξ N ).
The above claim (b) and the corollary both emphasize the fact that considering uniform weights 1 N induces the loss of a log N factor compared to an optimal (or simply rate optimal) greedy sequence for optimal quantization since, for such an (L 1 , U ([0, 1])) greedy optimal sequence a = (a N ) N ≥1 , one has

[0,1] d f (x)dx - N i=1 w (N ) i f (a i ) ≤ κ(a) [f ] Lip 1 N 1 d
where the N -tuple (w (N ) i

) 1≤i≤N is vector of hyper-volumes (Lebesgue measure) of the Voronoi cells attached to a (N ) . Of course the practical implementation of such greedy sequences remains more demanding since one needs to have access to these N -tuples of weights.

However, by contrast, optimal quantization based cubature formulas turn out to be efficient (accurate) for much lower values of N than sequences with low discrepancy (see e.g. the numerical experiment carried out in [START_REF] Pagès | Functional quantization for numerics with an application to option pricing[END_REF] dealing with the pricing of European derivatives).

A Appendix: Greedy Lloyd's I procedure A.1 The one-dimensional greedy Lloyd I procedure

The first is to establish the uniqueness of the equilibrium point a N satisfying (6.15) and the convergence of the Lloyd I procedure at level N toward this point, but with the significant additional constraint that the endpoints of the (closed convex) support of the strongly unimodal distribution µ are active (though fixed). By active we mean that, when finite, they have there own Voronoi area. To be more precise we will show the proposition (note that when a or b are infinite, the corresponding terms in the above expectation can be omitted). (a) The function ϕ is differentiable on I with a derivative given, for every x ∈ I, by

ϕ ′ (x) = 1 2 x+b 2 a+x 2 (x -ξ)µ(dξ).
Furthermore argmin I G is reduced to a single (stationary) point x * satisfying ϕ ′ (x * ) = 0 i.e.

x * = Φ(x * ) where Φ

(x) = K µ b+x 2 -K µ a+x 2 F µ b+x 2 -F µ a+x 2
and F µ and K µ denote the cumulative distribution and first moment functions of the distribution µ respectively.

(b) The greedy Lloyd I procedure defined by

x n+1 = Φ(x n ), x 0 ∈ I converges toward x *
This result can be seen as a variant of the Lloyd procedure at levels N (N = 1 up tp 3), depending on the finiteness of the endpoints of the interval I.

Proof. First note that, when both endpoints are infinite and cannot be active, the above statement becomes trivial since G(x) = E|X -x| 2 which attains its minimum at x * = E X, whereas the Lloyd I procedure reads x 1 = E X, n ≥ 1, whatever the starting point x 0 is.

Otherwise, if a or b are finite, we may assume, up to a symmetry-translation, that a = 0 and b ∈ (0, +∞]. (a) Elementary computations show that, for every x ∈ I,

G(x) = 1 2 x 2 0 ξ 2 µ(dξ) + x+b 2 x 2 (x -ξ) 2 µ(dξ) + +∞ x+b 2 (x -ξ) 2 µ(dξ)1 {b<+∞} G ′ (x) = x+b 2 x 2 (x -ξ)µ(dξ) and G ′′ (x) = F µ x + b 2 -F µ x 2 - x + b 2 -x f x + b 2 -x - x 2 f x 2 .
In what follows we focus on the case b < +∞. The case b = +∞ can be handled likewise (in fact in an easier way). Note that G ′ (0) = - (bξ)µ(dξ) > 0 so that G has at least one zero on (0, b). (When b = +∞, the existence follows form the fact that G does attain a minimum on (0, +∞) since lim x→+∞ G(x) = +∞.)

Set y 1 = x 2 and y 2 = x+b 2 . If we assume that x is a solution to x = Φ(x) (or equivalently to the stationary point equation G ′ (x) = 0), we can plug this expression for x into the above equation for G ′′ (x) so that G ′′ (x) can be expressed as a function of y 1 and y 2 ias follows:

G ′′ (x) = Φ(y 1 , y 2 ) F µ (y 2 ) -F µ (y 1 ) , y 1 < y 2 , y 1 , y 2 ∈ I, with Φ(y 1 , y 2 ) = F µ (y 2 ) -F µ (y 1 ) 2 + K µ (y 2 ) -K µ (y 1 ) ϕ(y 2 ) -ϕ(y 1 ) -F µ (y 2 ) -F µ (y 1 ) y 2 ϕ(y 2 ) -y 1 ϕ(y 1 ) .
Now we consider y 1 and y 2 as free variables living in I such that y 1 ≤ y 2 . First we note that Φ(y, y) = 0. Then, denoting by ϕ ′ r the right derivative of the log-concave function ϕ, we compute the following two (right) partial derivatives of Φ:

∂ Φ ∂y 1 r
(y 1 , y 2 ) = F µ (y 2 ) -F µ (y 1 ) y 1 ϕ ′ r (y 1 )ϕ(y 1 ) + (y 2y 1 )ϕ(y 1 )ϕ(y 2 )ϕ ′ r (y 1 ) K µ (y 2 ) -K µ (y 1 ) and ∂ 2 Φ ∂y 1 ∂y 2 r (y 1 , y 2 ) = (y 2y 1 ) ϕ(y 1 )ϕ ′ r (y 2 )ϕ ′ r (y 1 )ϕ(y 2 ) . When b is finite the sequence (x n ) n≥0 is trivially bounded. When b = +∞, assume there exists a subsequence x n ′ → +∞. By combining the above monotony property and Fatou's Lemma, we get

E|X| 2 ∧ |X -x 0 | 2 = G(x 0 ) ≥ lim inf n G(x n ′ ) ≥ E X 2
which implies that X 2 ≤ (Xx 0 ) 2 P-a.s. This is clearly not satisfied on the event {X ∈ [0, x0

2 )} which has positive probability. Consequently, (x n ) n is always bounded.

Then let x ∞ = lim n→+∞ x n ′ be a limiting value of the I-valued sequence (x n ) n≥0 . Up to a new extraction, still denoted (n ′ ), one may assume that x n ′ +1 converges toward a limiting value x ′ ∞ as well. Passing to the limit owing to continuity we get

x ′ ∞ = x∞ +b 2 x∞ 2
ξµ(dξ).

One shows as above that, except if x ′ ∞ = x ∞ = x * , G(x ′ ∞ ) < G(x ∞ ) which cannot be true since the sequence (G(x n )) n≥0 converges to ℓ 2 . Consequently, x * = x ∞ is the only possible limiting value for the bounded sequence (x n ) n≥0 i.e. its limit.

Proof of Proposition 6.1. The result follows by applying the above result to the procedure on the interval a (N -1) i0

, a

(N -1) i0+1 2 of maximal inertia.

Remark. If we choose a [0] inside an interval which has not the highest local inertia, the procedure will still converge since we never use this fact throughout the proof of the convergence. The resulting limit will live in the same interval as the starting value since the algorithm leaves each interval stable by an obvious convexity argument. So the greedy Lloyd I procedure yields potentially N + 1 "candidates" corresponding to each possible starting interval, but only one (issued from the interval with the highest local inertia) is solution to the greedy optimal quantization problem.

A.2 The multi-dimensional greedy Lloyd I procedure (proof of Proposition 6.2)

We assume in this section that µ has a convex support C µ = supp(µ) and that d ≥ 2. Note that in such a framework there is a major topological difference with the 1-dimensional case: a convex set not reduced to a single point remains pathwise connected when one point of its points is removed. Owing to that property, it is easy to show that the algorithm may visit with positive probability the whole support of C µ (to be precise any nonempty open set of C µ ). Moreover, the points can no longer be naturally ordered like in 1-dimension.

To alleviate notations, we denote by G the R + -valued function a → e 2 a (N -1) ∪ {a} 2 defined on C µ by G(a) = e 2 a (N -1) ∪ {a} 2 = E d X, a (N -1) ∪ {a} 2 .

Let a [0] ∈ C µ \ a (N -1) . Lloyd's I procedure is defined by induction by Equation (6.17 hence

G(a [n+1] ) = E d(X, a (N -1) ∪ {a [n+1] }) 2 ≤ E d(X, a (N -1) ) 2 1 {X / ∈W N,[n] } + E |X -a [n+1] | 2 1 {X∈W N,[n] } < E d(X, a (N -1) ) 2 1 {X / ∈W N,[n] } + E |X -a [n] | 2 1 {X∈W N,[n] } = G(a [n] ).
hence, the (non-increasing, non-negative) sequence (G(a [n] )) n converges to a finite limit ℓ 2 ∈ R + as n → +∞. The fact that ℓ ∈ e 2 (a (N ) , e 2 (a (N -1) ∪ {a ) < E d(X, a (N -1) ) 2 which yields a contradiction.

Step 3: Let a [∞] be a limiting value of the bounded sequence (a [n] ) n (i.e. the limit of a subsequence). Up to a new extraction, we may also assume that a

[n+1] → a ′ [∞] . Since G(a [n]
) is non-decreasing, G(a [∞] ) and

  Notations: • N * = {1, 2, . . .} the set of positive integers. • | . | denotes any norm on R d (except specific mention). For every subset A ⊂ R d and ξ ∈ R d , d(ξ, A) = inf a∈A |ξ -a| (distance of ξ to the set A in (R d , | . |)).

  µ(dξ) > 0. Consequently, as Ψ b ∈ L p p+d (µ), we can define the probability distribution ν = κ b,p,d Ψ

  ,d C r,b,d . The sequence (A N ) N ≥1 being non-negative, one classically derives the announced conclusion (for a proof, see Lemma B.1 in Appendix B, applied with ρ = d p and C = κ).

  s. so that by Fatou's Lemma, the condition Ψ b ∈ L p p+d (µ) implies R d ϕ d p+d (ξ)dλ d (dξ) < +∞.

  X) p where e p,N (X) = inf Γ⊂R d ,card(Γ)≤N e p (Γ, X) denotes the minimal L p -mean quantization error.

Lemma 4 . 3 (

 43 see Corollary 3 in[START_REF] Graf | Distortion mismatch in the quantization of probability measures[END_REF]). If X ∈ L p+δ (P) for some δ > 0 with an essentially radial distribution µ(dξ) = ϕ(ξ)λ d (dξ) in the sense thatϕ = h(| . | 0 ) on B | . | 0 (0, R) c with h : (R, +∞) → R + ,non-increasing and | . | 0 any norm on R d . (4.7)

1 d

 1 X) and lim inf N N e p,N (X) ≥ J p,d ϕ 1 p L p p+d (λ d ) > 0. (By the way it proves that under the assumption of Theorem 3.1, ϕ L p p+d (λ d ) < +∞.) By a similar argument, the same holds true for the distortion mismatch problem under the assumptions of Proposition 3.1.

Figure 1 :

 1 Figure 1: Graph N → N e 2 a (N ) , U ([0, 1]) , N = 1, . . . , 10 000.

1 2 e 2 , 1 d 2 1d

 1212 N N (0; I 2 ). All these considerations experiments lead us to formulate a second open question:Open question 2: Does an (L p , µ)-optimal greedy quantization (a N,p ) N ≥1 produce the lowest value for lim sup N N e p,N a (N ),p , µ among all sequences (a N,p ) N ≥1 ?A less ambitious question could be to compare (L p , µ)-optimal greedy sequences to concatenated sequences (5.13) i.e.: "Is the (strict )inequality lim sup N e p a (N ),p , µ e p,N (µ) < always satisfied?"

Figure 2 : 1 4 2 π 1 4× 3 2 π 1 4

 21211 Figure 2: Graph N → (2N -1)e 2 a (2N -1) , N (0; 1) , N = 4, . . . , 10 000.

Figure 3 : 2 3 ;

 323 Figure 3: Graph N → √ N e 2 a (N ) , N (0; I 2 ) , N = 1, . . . , 10 3 , computed by the randomized greedy Lloyd I procedure (M = M (N ) = 1 000 × N , N = 1, . . . , 10 3 ). Flat solid line (---) depicts Zador's constant J 2,2 = 2 3 5 π √ 3 ; flat dashed line (---) depicts the natural upper bound for the concatenated sequence.

Figure 4 :

 4 Figure 4: Greedy quantizer a (1000) for the N (0; I 2 ) distribution computed by the randomized greedy Lloyd I procedure with a simulation of size M = 10 6 .

1 N 1 N

 11 ξ)dξ. This means that the weights associated to a uniformly distributed sequence are by definition all equal to which leads to a simple normalization factor 1/N . What is the cost induced by these uniform weights , compared to the primal weights deduced from the cell (hyper-)volumes of the Voronoi diagram of ξ 1 , . . . , ξ N ?

Theorem 7 . 1 (

 71 Proinov [36]). Assume R d is equipped with the ℓ ∞ -norm|(ξ 1 , . . . , ξ d )| ∞ = max 1≤i≤d |ξ i |.For every continuous function f : [0, 1] d → R, we define uniform continuity modulus of f (with range δ ∈ [0, 1]) by w(f, δ) := sup

Proposition A. 1 .

 1 Let µ be a distribution on the real line with log-concave density : varphi (i.e. strongly unimodal) with a finite second moment. Then the support I = {ϕ > 0}) is closed interval with endpoints a, b ∈ R. If a or b are finite, one may assume without loss of generality that ϕ(a) or ϕ(b) > 0 (so that I is closed). Then the quantization problem at level N with active finite endpoints (if any) reads min x∈I ϕ(x) := E |X -a| ∧ |X -b| 2 ∧ |X -x| 2

1 2 0 1 1 2

 1212 ξµ(dξ) < 0 and G ′ (b) =

ϕ

  is non-increasing in I, it follows that ∂ 2 e Φ ∂y1∂y2 (y 1 , y 2 ) < 0 if y 1 < y 2 so that y 2 → ∂ e Φ ∂y1 r (y 1 , y 2 ) is (strictly) decreasing on [y 1 , b) which in turn implies it is positive on (y 1 , b). This shows that Φ(y 1 , y 2 ) > 0 for every y 1 , y 2 ∈ I, y 1 < y 2 . As a consequence, any stationary point x satisfies G ′′ (x) < 0 i.e. is a strict local minimum of G. This implies uniqueness of the solution to the equation G ′ (x) = 0 by an elementary one dimensional "mountain pass" argument. (b) In this second claim, we use again a random variable X with distribution µ. By Proposition 2.1(b), we know that ifW [n] = [ xn 2 , xn+b 2 ] denotes the closed Voronoi cell of x n with respect to {0, x n , b} (if b is finite, or {0, x n } otherwise) then E µ |Xx n+1 | 2 1 {X∈W [n] } ≤ E µ |Xx n | 2 1 {X∈W [n] } .with equality iff x n+1 = x n which is equivalent tox n = x * (see claim (a) above). Decomposing |Xx n+1 | 2 on the Voronoi partition [0, xn 2 ] ∪ [ xn 2 , xn+b 2 ] ∪ [ xn+b2, b] of I, one derives that G(x n+1 ) < G(x n ) as soon as x n = x * . the function G being non-negative G(x n ) → ℓ as n → ∞.

1 :

 1 ), namelya [n+1] = E X | X ∈ W N,[n] ∈ C µ where W N,[n] denotes the (closed) Voronoi cell of a [n] induced by a (N -1) ∪ {a [n] }.Step It follows from Proposition 2.1(b) that, as son as a [n] is not stationary, i.e. a[n] = E X | X ∈ W N,[n] , one has E |Xa [n+1] | 2 1 {X∈W N,[n] } < E |Xa [n] | 2 1 {X∈W N,[n] } .

2 :

 2 [0] } is obvious form what precedes.Step Assume there exists a subsequence (a[n ′ ] ) such that |a [n ′ ] | → +∞ as n → +∞.Combining the above monotony of the sequence (G(a [n] )) n≥0 and Fatou's Lemma yieldsE d(X, a (N -1) ) 2 ≤ lim inf n E d(X, a (N -1) ∪ {α [n ′ ] }) 2 ≤ lim inf n G(a [n] ) ≤ G(a [0] ) But, as a [0] ∈ C µ \ a (N -1) , we know from Proposition 2.1(a) that G(a[0]

  In this section we assume that | . | denotes an Euclidean norm on R d . Let H µ be the closed convex hull of the support of the distribution µ. Proposition 2.2. Let ( .|. ) denote the inner product induced by the Euclidean norm. If supp(µ) contains at least N elements then, the first N elements of any optimal greedy quantization sequence takes values in H µ . If supp(µ) is infinite any optimal greedy quantization sequence takes values in H µ .

  1 and 1.09 < 1.125 = 9/8.

	0.35
	0.34
	0.33
	0.32
	0.31
	0.3
	0.29
	0	1000	2000	3000	4000	5000	6000	7000	8000	9000	10000

This is consistent in some way with the conjecture that N e2,N `N (0; 1) ´is increasing toward its limit.

) < e 2 (a (N -1) , µ) so that we a ′ 1) . The distribution µ being strongly continuous (i.e. assigning no mass to hyperplanes), one shows e.g. by following the lines of the proof of Lemma 2.3 in [START_REF] Pagès | Pointwise convergence of the Lloyd algorithm in higher dimension[END_REF] that

which shows that one the one hand that a [n+1]a [n] → 0 as n → +∞ and that any limiting value of (a

The conclusion follows by standard topological arguments on convergence of sequences.

B Appendix: A technical result on sequences

Lemma B.1. Let (A N ) N ≥1 be a sequence of non-negative real numbers and let ρ ∈ (0, +∞) such that

for some real constant C > 0. Then there exists a real constant K > 0 such that

Proof. We may assume that A N > 0 for every N ≥ 1, it follows from the inequality satisfies by the sequence

Now, there exists u 0 = u 0 (ρ) such that for every u ∈ [0, u 0 ], (1 + u) ρ ≥ 1 + ρ 2 u. It is clear from the assumptions that A N ↓ 0, hence, there exists a large enough integer N 0 such that for every N ≥ N 0 ,

so that, for every N > N 0 ,

.

This completes the proof.