text: (cid:80) (cid:80) Proof. If f s are not linearly independent then k λ f = 0 for λ¯ = (λ , λ , . . . , λ ) ∈ Fk \ {¯0}. Theni, the nonzero multilinear polynomial ik=1 λi mi (X) evaluates to1 ze2ro on FkN, whqich i=1 i i q contradicts Theorem 7. { } Consider the derivatives of NW (X) corresponding to the sets x , x , . . . , x n,(cid:15) 1a(1) 2a(2) ≥(cid:15)na((cid:15)n) for all univariate polynomials a of degree < (cid:15)n. From Lemma 9, it follows that dim(H) n(cid:15)n = e(cid:15)nlnn. W.l.o.g, we can assume that the constant function 1 : Fn2 → F given by ∀x, 1(x) = 1 is q q also in H. This corresponds to the derivatives of order n. { } The derivative space of IMM (X) polynomial family n,n n>0 For our application, we consider n = 2m where m ranges over the positive integers. Consider − the set of matrices X(1), X(3), . . . , X(2m 1) corresponding to the odd places. Let S be any set of m variables chosen as follows. Choose any variable from the ﬁrst row of X(1) and choose any one − variable from each of the matrices X(3), . . . , X(2m 1). We call such a set S an admissible set. If we diﬀerentiate IMM (X) with respect to two diﬀerent admissible sets of variables S and (cid:48) n,n S , then we get two diﬀerent monomials of length m each. This follows from the structure of the − monomials in the IMM (X) polynomial, whenever we ﬁx two variables from X(i 1) and X(i+1), n,n the variable from X(i) gets ﬁxed. So the number of such monomials after diﬀerentiation is exactly − − n2m 1 = e(n 1)lnn. Let m be the monomial obtained after diﬀerentiating IMM (X) by the set of variables in S S n,n and var(m ) be the set of variables in m . Consider the derivatives of IMM (X) with respect S S n,n to the following sets of variables. { ∪ ⊆ } S T : T var(m ) where S ranges over all admissible sets. S Let H be the su(cid:26)bspace spanned by these derivatives. More formally, (cid:27) H := F -span ∂IMMn,n(X) : D = S ∪ T where T ⊆ var(m ); S is an admissible set q ∂D S As before, we can assume that the constant function 1 is in H. From Lemma 9, we know that ≥ − dim(H) e(n 1)lnn. Now to unify the arguments for NW (X) and IMM (X) polynomials, we n,(cid:15) n,n introduce the following notion. Downward closed property M Deﬁnition 10. A set of monomials is said to be downward closed if the following property ∈ M (cid:48) (cid:48) ⊆ (cid:48) ∈ M holds. If m(X) and m (X) is such that var(m (X)) var(m(X)), then m (X) . M Now we consider a downward closed set of monomials over N variables. These monomials F F can be viewed as functions from N to . W.l.o.g, we assume that the constant function is also M q q in (constant function corresponds to a monomial with an empty set of variables). Let H be M the subspace spanned by these functions in . ∈ F − For any u N, deﬁne an operator T such that (T (f))(X) = f(X u) for any function F → F q u u f : N . The following proposition is simple to prove. q q M Proposition 11. Let H be the subspace spanned by a downward closed set of monomials over { } ∈ F t(cid:80)he set of variables x1, x2, . . . , xN . Then for any u Nq , Tu is a linear map from H to H. Proof. Let g(X) be an arbi∈trMary functio∈n Fin H wh(cid:88)ic≥h can be expressed as follows: g(X) = ≥ c m (X) where m (X) , and c for all i 1. i 1 i i i i q − − (T (g))(X) = g(X u) = c m (X u) u i i ≥ i 1 8 ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Proof.

text: If

text: f

text: s

text: are

text: not

text: linearly

text: independent

text: then

text: k

text: λ

text: f

text: for

text: λ¯

text: (λ

text: λ

text: λ

text: Fk

text: Theni,

text: the

text: nonzero

text: multilinear

text: polynomial

text: λi

text: mi

text: (X)

text: evaluates

text: on

text: FkN,

text: whqich

text: i

text: i

text: q

text: contradicts

text: Theorem

text: Consider

text: the

text: derivatives

text: of

text: NW

text: (X)

text: corresponding

text: to

text: the

text: sets

text: x

text: x

text: x

text: for

text: all

text: univariate

text: polynomials

text: a

text: of

text: degree

text: From

text: Lemma

text: it

text: follows

text: that

text: dim(H)

text: W.l.o.g,

text: we

text: can

text: assume

text: that

text: the

text: constant

text: function

text: F

text: given

text: by

text: ∀x,

text: is

text: q

text: q

text: also

text: in

text: H.

text: This

text: corresponds

text: to

text: the

text: derivatives

text: of

text: order

text: n.

text: The

text: derivative

text: space

text: of

text: IMM

text: (X)

text: polynomial

text: family

text: n,n

text: For

text: our

text: application,

text: we

text: consider

text: n

text: where

text: m

text: ranges

text: over

text: the

text: positive

text: integers.

text: Consider

text: the

text: set

text: of

text: matrices

text: corresponding

text: to

text: the

text: odd

text: places.

text: Let

text: S

text: be

text: any

text: set

text: of

text: m

text: variables

text: chosen

text: as

text: follows.

text: Choose

text: any

text: variable

text: from

text: the

text: ﬁrst

text: row

text: of

text: and

text: choose

text: any

text: one

text: variable

text: from

text: each

text: of

text: the

text: matrices

text: We

text: call

text: such

text: a

text: set

text: S

text: an

text: admissible

text: set.

text: If

text: we

text: diﬀerentiate

text: IMM

text: (X)

text: with

text: respect

text: to

text: two

text: diﬀerent

text: admissible

text: sets

text: of

text: variables

text: S

text: and

text: n,n

text: S

text: then

text: we

text: get

text: two

text: diﬀerent

text: monomials

text: of

text: length

text: m

text: each.

text: This

text: follows

text: from

text: the

text: structure

text: of

text: the

text: monomials

text: in

text: the

text: IMM

text: (X)

text: polynomial,

text: whenever

text: we

text: ﬁx

text: two

text: variables

text: from

text: X(i

text: and

text: n,n

text: the

text: variable

text: from

text: X(i)

text: gets

text: ﬁxed.

text: So

text: the

text: number

text: of

text: such

text: monomials

text: after

text: diﬀerentiation

text: is

text: exactly

text: e(n

text: Let

text: m

text: be

text: the

text: monomial

text: obtained

text: after

text: diﬀerentiating

text: IMM

text: (X)

text: by

text: the

text: set

text: of

text: variables

text: in

text: S

text: S

text: n,n

text: and

text: var(m

text: be

text: the

text: set

text: of

text: variables

text: in

text: m

text: Consider

text: the

text: derivatives

text: of

text: IMM

text: (X)

text: with

text: respect

text: S

text: S

text: n,n

text: to

text: the

text: following

text: sets

text: of

text: variables.

text: S

text: T

text: T

text: var(m

text: where

text: S

text: ranges

text: over

text: all

text: admissible

text: sets.

text: S

text: Let

text: H

text: be

text: the

text: spanned

text: by

text: these

text: derivatives.

text: More

text: formally,

text: H

text: F

text: -span

text: ∂IMMn,n(X)

text: D

text: S

text: T

text: where

text: T

text: var(m

text: S

text: is

text: an

text: admissible

text: set

text: q

text: ∂D

text: S

text: As

text: before,

text: we

text: can

text: assume

text: that

text: the

text: constant

text: function

text: is

text: in

text: H.

text: From

text: Lemma

text: we

text: know

text: that

text: dim(H)

text: e(n

text: Now

text: to

text: unify

text: the

text: arguments

text: for

text: NW

text: (X)

text: and

text: IMM

text: (X)

text: polynomials,

text: we

text: n,n

text: introduce

text: the

text: following

text: notion.

text: Downward

text: closed

text: property

text: M

text: Deﬁnition

text: A

text: set

text: of

text: monomials

text: is

text: said

text: to

text: be

text: downward

text: closed

text: if

text: the

text: following

text: property

text: M

text: M

text: holds.

text: If

text: m(X)

text: and

text: m

text: (X)

text: is

text: such

text: that

text: var(m

text: (X))

text: var(m(X)),

text: then

text: m

text: (X)

text: M

text: Now

text: we

text: consider

text: a

text: downward

text: closed

text: set

text: of

text: monomials

text: over

text: N

text: variables.

text: These

text: monomials

text: F

text: F

text: can

text: be

text: viewed

text: as

text: functions

text: from

text: N

text: to

text: W.l.o.g,

text: we

text: assume

text: that

text: the

text: constant

text: function

text: is

text: also

text: M

text: q

text: q

text: in

text: (constant

text: function

text: corresponds

text: to

text: a

text: monomial

text: with

text: an

text: empty

text: set

text: of

text: variables).

text: Let

text: H

text: be

text: M

text: the

text: subspace

text: spanned

text: by

text: these

text: functions

text: in

text: F

text: For

text: any

text: u

text: N,

text: deﬁne

text: an

text: operator

text: T

text: such

text: that

text: (T

text: (f))(X)

text: f(X

text: u)

text: for

text: any

text: function

text: F

text: F

text: q

text: u

text: u

text: f

text: N

text: The

text: following

text: proposition

text: is

text: simple

text: to

text: prove.

text: q

text: q

text: M

text: Proposition

text: Let

text: H

text: be

text: the

text: subspace

text: spanned

text: by

text: a

text: downward

text: closed

text: set

text: of

text: monomials

text: over

text: F

text: set

text: of

text: variables

text: xN

text: Then

text: for

text: any

text: u

text: Nq

text: Tu

text: is

text: a

text: linear

text: map

text: from

text: H

text: to

text: H.

text: Proof.

text: Let

text: g(X)

text: be

text: an

text: arbi∈trMary

text: functio∈n

text: Fin

text: H

text: can

text: be

text: expressed

text: as

text: follows:

text: g(X)

text: c

text: m

text: (X)

text: where

text: m

text: (X)

text: and

text: c

text: for

text: all

text: i

text: i

text: i

text: i

text: i

text: i

text: q

text: (T

text: (g))(X)

text: g(X

text: u)

text: c

text: m

text: (X

text: u)

text: u

text: i

text: i

text: i

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: ∈ { } (cid:92) Set for every i, j 1, . . . , N ∞ ∞ { ∞ ≥ } (ϕ(k)) ϕ = lim ϕ and C = ϕ 0 . ij →∞ ij i ij ϕ(k) (cid:54) j=i ∈ { } ∞ Hence, for every i 1, . . . , N , C is a closed polyhedral convex set containing x . It also contains ∈ i i∈ { } x˜ since x(ϕ(k)+1) C (Γ(ϕ(k))) owing to the stationarity property. Then, for every j 1, . . . , N , i i i ∞ ∞ ≥ (ϕ(k)) (ϕ(k)+1) ϕ (x˜ ) = lim ϕ (x ) 0 ij i →∞ ij i ϕ(k) ∞ (ϕ(k)) since ϕ uniformly on compact sets toward ϕ (simple convergence of aﬃne forms in ﬁnite di- ij i mension implies locally uniform convergence). ∈ { } { | ∞ ∞} { } Assume there exists i 1, . . . , N such that I = i x = x is not reduces to i i.e. 0 (cid:110) (cid:0) 0 i (cid:1)(cid:111) (cid:91)i0 0 contains at least two indices. It is clear that ∅ (cid:54) ∈ R | | − ∞| ∞ \ { } ⊂ ∞ = ξ d ξ x < d ξ, Γ( ) x C . i0 i0 ∈ i i I0 ∈ The above nonempty open set has non zero µ-mass since x U. Hence, there exists two indices ∈ ∞ ∞ i0 ∞ ∞ ≥ ∞ ≥ i , i I such that µ(C ) and µ(C ) > 0. First note that ϕ (x ) 0 and ϕ (x ) 0 but 1 2 0 i1 i2∞ ∞ i1i2 i1 i2i1 i2 both quantities being opposite since x = x they are equal to 0 which means that i1 i2 ∞ ∞ ∞ ∈ ∞ ∩ ∞ x = x = x ∂C ∂C . i0 i1 i2 i1 i2 ◦ ◦ Since these sets are polyhedral and µ assigns no mass to hyperplanes, µ(C ) and µ(C ) > 0. i1 i2 Then one checks that 1 ◦ = lim 1◦ , (cid:96) = 1, 2 ∞ Ci(cid:96) k Ci((cid:96)ϕ(k)) (cid:0) (cid:1) so that, still using that µ assigns no mass to the boundaries of these polyhedral convex sets, we get ◦ ◦ ∞ (ϕ(k)) 0 < µ(C ) = lim µ C , (cid:96) = 1, 2. i(cid:96) k→+∞ i(cid:96) ◦ ∞ Set ε = min µ(C ) > 0. It follows form(cid:0)(2.7) that(cid:1)(cid:0)(cid:12) (cid:12) (cid:12) (cid:12) (cid:1) 0(cid:98) (cid:96)=1,2 i(cid:96) (cid:98) (cid:12) (cid:12) (cid:12) (cid:12) ◦ (cid:107) − (cid:107) −(cid:107) − (cid:107) ≥ (ϕ(k)) − − X XΓ(ϕ(k)) 2 X XΓ(ϕ(k)+1) 2 min µ C x(ϕ(k)+1) x(ϕ(k)) 2 + x(ϕ(k)+1) x(ϕ(k)) 2 . 2 2 (cid:96)=1,2 i(cid:96) i1 i1 i2 i2 (cid:0)(cid:12) (cid:12) (cid:12) (cid:12) (cid:1) Letting ϕ(k) go to inﬁnity implies th(cid:12)at (cid:12) (cid:12) (cid:12) ∞ − ∞ ∞ − ∞ ≤ (cid:98) ε x˜ x 2 + x˜ x 2 0 0 i1 i1 i2 i2 (cid:107) − (cid:107) ∞ ∞ since X XΓ(k) is a converging sequence. Hence x˜ = x , (cid:96) = 1, 2, which in turn implies that ∞ ∞ 2 i(cid:96) i(cid:96) x˜ = x˜ = x . i1 i1 i0 (cid:90) (cid:90) One shows likewise, still taking advantage of the µ-negligibility of the boundaries of the polyhedral ∞ sets C , that i lim ξµ(dξ) = ξµ(dξ), (cid:96) = 1, 2. k→+∞ Ci(cid:96)(Γ(ϕ(k))) Ci∞(cid:96) 14

label: paragraph

text: Set

text: for

text: every

text: i,

text: j

text: N

text: (ϕ(k))

text: ϕ

text: lim

text: ϕ

text: and

text: C

text: ϕ

text: ij

text: ij

text: i

text: ij

text: ϕ(k)

font: default

text: j=i

text: Hence,

text: for

text: every

text: i

text: N

text: C

text: is

text: a

text: closed

text: polyhedral

text: convex

text: set

text: containing

text: x

text: It

text: also

text: contains

text: i

text: i∈

text: x˜

text: since

text: C

text: (Γ(ϕ(k)))

text: owing

text: to

text: the

text: stationarity

text: property.

text: Then,

text: for

text: every

text: j

text: N

text: i

text: i

text: i

text: (ϕ(k))

text: ϕ

text: (x˜

text: lim

text: ϕ

text: (x

text: ij

text: i

text: ij

text: i

text: ϕ(k)

text: (ϕ(k))

text: since

text: ϕ

text: uniformly

text: on

text: compact

text: sets

text: toward

text: ϕ

text: (simple

text: convergence

text: of

text: aﬃne

text: forms

text: in

text: ﬁnite

text: di-

text: ij

text: i

text: mension

text: implies

text: locally

text: uniform

text: convergence).

text: Assume

text: there

text: exists

text: i

text: N

text: such

text: that

text: I

text: i

text: x

text: x

text: is

text: not

text: reduces

text: to

text: i

text: i.e.

text: i

text: contains

text: at

text: least

text: two

text: indices.

text: It

text: is

text: clear

text: that

text: R

text: ξ

text: d

text: ξ

text: x

text: d

text: ξ,

text: Γ(

text: x

text: C

text: i

text: i

text: The

text: above

text: nonempty

text: open

text: set

text: has

text: non

text: zero

text: µ-mass

text: since

text: x

text: U.

text: Hence,

text: there

text: exists

text: two

text: indices

text: i

text: i

text: I

text: such

text: that

text: µ(C

text: and

text: µ(C

text: First

text: note

text: that

text: ϕ

text: (x

text: and

text: ϕ

text: (x

text: but

text: both

text: quantities

text: being

text: opposite

text: since

text: x

text: x

text: they

text: are

text: equal

text: to

text: which

text: means

text: that

text: x

text: x

text: x

text: ∂C

text: ∂C

text: Since

text: these

text: sets

text: are

text: polyhedral

text: and

text: µ

text: assigns

text: no

text: mass

text: to

text: hyperplanes,

text: µ(C

text: and

text: µ(C

text: Then

text: one

text: checks

text: that

text: lim

text: 1◦

text: k

text: so

text: that,

text: still

text: using

text: that

text: µ

text: assigns

text: no

text: mass

text: to

text: the

text: boundaries

text: of

text: these

text: polyhedral

text: convex

text: sets,

text: we

text: get

text: (ϕ(k))

text: µ(C

text: lim

text: µ

text: C

text: k→+∞

text: Set

text: ε

text: min

text: µ(C

text: It

text: follows

text: (ϕ(k))

text: X

text: XΓ(ϕ(k))

text: X

text: min

text: µ

text: C

text: x(ϕ(k))

text: x(ϕ(k))

text: Letting

text: ϕ(k)

text: go

text: to

text: inﬁnity

text: implies

text: ε

text: x˜

text: x

text: x˜

text: x

text: since

text: X

text: XΓ(k)

text: is

text: a

text: converging

text: sequence.

text: Hence

text: x˜

text: x

text: which

text: in

text: turn

text: implies

text: that

text: x˜

text: x˜

text: x

text: One

text: shows

text: likewise,

text: still

text: taking

text: advantage

text: of

text: the

text: µ-negligibility

text: of

text: the

text: boundaries

text: of

text: the

text: polyhedral

text: sets

text: C

text: that

text: i

text: lim

text: ξµ(dξ)

text: ξµ(dξ),

text: k→+∞


text: (cid:12) (cid:12) (cid:88) (cid:12)(cid:12) (cid:12)(cid:12) (cid:88) (cid:12)(cid:90) (cid:12) (cid:88) (cid:90) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) |∇G | N ∂G 2 N (cid:12) − P (cid:12)2 ≤ N | − | P G (Γ) 2 = (Γ) = 4 (x ξ) (dξ) 4 x ξ 2 (dξ) = 4 (Γ) 2 ∂x (cid:0) (cid:1) i i i=1 i i=1 Ci(Γ i=1 Ci(Γ ∇G P so that the sequence (Γ(k)) ≥ is bounded. Now, as assigns no mass to the boundary of (cid:0) (cid:1) k 0 X any Voronoi tessellations, we derive from what precedes that any limiting grid of (Γ(k)) ≥ is stationary ∇G ∞ k 0 i.e. (Γ( )) = 0. It is clear by an extraction procedure that 0 is the only limiting value for the ∇G bounded sequence (Γ(k)) ≥ which consequently converges toward 0. k 0 (d) The set of limiting grids of the sequence (Γ(k)) ≥ is compact by construction. Its connectedness k 0 will classically follow from | − | −−→−∞→ Γ(k+1) Γ(k) k 0 (see e.g. [15]). { ≥ } ∪ It is clear from item (a) that K = Γ(k), k 0 Υ∞ is a compact whose intersection with the { ∈ R Γ(cid:54) (cid:54) } closed set (x , . . . , x ) ( d)N, x = x , i = j c. Hence, K stands at a positive distance of this set 1 N i j Γ or, equivalently, there exists δ > 0, such that ∀ ≥ ∀ ∈ { } (cid:54) | − | ≥ (k) (k) k 0, i, j 1, . . . , N , i = j, x x δ. i j As a consequence, every Voronoi cell satisﬁes ◦ ⊂ B(x(k), δ/2) C (Γ(k)) i i ◦ (cid:0) (cid:1) where B(ξ, r) denotes the open ball with center ξ and radius r. Since U = supp(µ) is a (closed) ⊂ ⊂ ∈ N ⊂ convex set and Γ(0) supp(µ), then Γ(k) U for every k . As a consequence, K U which in (cid:55)→ P ∈ ◦ Γ turn implies that the function ξ X B(ξ, δ/2) is (strictly) positive on the compact set K , so (cid:0) (cid:1) Γ that we can deﬁne P ∈ ◦ m∗ := inf X B(ξ, δ/2) > 0 (2.6) ∈ ξ KΓ which implies in particular that M(k) = P(X ∈ C (Γ(k))) (cid:62) m∗, 1 ≤ i ≤ N, k ≥ 0. i i (cid:13) (cid:13) (cid:13) (cid:13) Now we introduce the energy gap (cid:13) (cid:98) (cid:13) (cid:13) (cid:101) (cid:13) − − − ∆(k) = X XΓ(k) 2 X XΓ(k+1) 2 2 2 known to be non-negative by (2.4) in Lemma 2.1. Then 16 ##LTLine##

label: equation

text: |∇G

text: N

text: ∂G

text: N

text: P

text: N

text: P

text: G

text: (Γ)

text: (Γ)

text: (x

text: ξ)

text: (dξ)

text: x

text: ξ

text: (dξ)

text: (Γ)

text: ∂x

text: i

text: i

text: i

text: Ci(Γ

text: Ci(Γ

text: ∇G

text: P

text: so

text: that

text: the

text: sequence

text: (Γ(k))

text: is

text: bounded.

text: Now,

text: as

text: assigns

text: no

text: mass

text: to

text: the

text: boundary

text: of

text: k

text: X

text: any

text: Voronoi

text: tessellations,

text: we

text: derive

text: from

text: what

text: precedes

text: that

text: any

text: limiting

text: grid

text: of

text: (Γ(k))

text: is

text: stationary

text: ∇G

text: k

text: i.e.

text: (Γ(

text: It

text: is

text: clear

text: by

text: an

text: extraction

text: procedure

text: that

text: is

text: the

text: only

text: limiting

text: value

text: for

text: the

text: ∇G

text: bounded

text: sequence

text: (Γ(k))

text: which

text: consequently

text: converges

text: toward

text: k

text: (d)

text: The

text: set

text: of

text: limiting

text: grids

text: of

text: the

text: sequence

text: (Γ(k))

text: is

text: compact

text: by

text: construction.

text: Its

text: connectedness

text: k

text: will

text: classically

text: follow

text: from

text: Γ(k)

text: k

text: (see

text: e.g.

text: It

text: is

text: clear

text: from

text: item

text: (a)

text: that

text: K

text: Γ(k),

text: k

text: Υ∞

text: is

text: a

text: compact

text: whose

text: intersection

text: with

text: the

text: R

text: closed

text: set

text: (x

text: x

text: d)N,

text: x

text: x

text: i

text: j

text: c.

text: Hence,

text: K

text: stands

text: at

text: a

text: positive

text: distance

text: of

text: this

text: set

text: N

text: i

text: j

text: Γ

text: or,

text: equivalently,

text: there

text: exists

text: δ

text: such

text: that

text: (k)

text: (k)

text: k

text: i,

text: j

text: N

text: i

text: j,

text: x

text: x

text: δ.

text: i

text: j

text: As

text: a

text: consequence,

text: every

text: Voronoi

text: cell

text: satisﬁes

text: B(x(k),

text: C

text: (Γ(k))

text: i

text: i

text: where

text: B(ξ,

text: r)

text: denotes

text: the

text: open

text: ball

text: with

text: center

text: ξ

text: and

text: radius

text: r.

text: Since

text: U

text: supp(µ)

text: is

text: a

text: (closed)

text: N

text: convex

text: set

text: and

text: supp(µ),

text: then

text: Γ(k)

text: U

text: for

text: every

text: k

text: As

text: a

text: consequence,

text: K

text: U

text: which

text: in

text: P

text: Γ

text: turn

text: implies

text: that

text: the

text: function

text: ξ

text: X

text: B(ξ,

text: is

text: (strictly)

text: positive

text: on

text: the

text: compact

text: set

text: K

text: so

text: Γ

text: that

text: we

text: can

text: deﬁne

text: P

text: m∗

text: inf

text: X

text: B(ξ,

text: ξ

text: KΓ

text: which

text: implies

text: in

text: particular

text: that

text: M(k)

text: P(X

text: C

text: (Γ(k)))

text: m∗,

text: i

text: N,

text: k

text: i

text: i

text: Now

text: we

text: introduce

text: the

text: energy

text: gap

text: ∆(k)

text: X

text: XΓ(k)

text: X

text: known

text: to

text: be

text: non-negative

text: by

text: in

text: Lemma

text: Then

text: ##LTLine##


text:  (cid:0) (cid:1) Γ(0) ⊂ Rd. For every k ≥ 0, (cid:101) (cid:98) (cid:101) (cid:0) (cid:1)      E | (I)Centroid updating : X(k+1) = X XΓ(k) , Γ(k+1) = X(k+1)(Ω)  (cid:98) (cid:101) = E 1{X(cid:98)(cid:98)Γ(k)=x(ik)}X , i = 1, . . . , N P(XΓ(k)=x(k)) i ← (II)Voronoi cells re-allocation : XΓ(k+1) X(k+1). (cid:98) (cid:98) with the following degeneracy convention: if P(XΓ(k) = x(k)) = P(X ∈ C (Γ(k))) = 0 then XΓ(k+1) = x(k). i i i We need now to formalize in a more precise way what can be a consistent connection between the sequence of iterated grids (Γ(k)) ≥ in the Lloyd procedure and the N-tuples that can be associated k 0 to their values. | | Deﬁnition 2.1. Let (Γ(k)) ≥ be a sequence of iterates of the Lloyd procedure where Γ(0) = N. A k 0 sequence of N-tuples (x(k)) ≤ is a consistent representation of the sequence Γ(k) if k 0 { } (i) Γ(k) = x(k), i = 1, . . . , N , i (cid:0) (cid:1) ≥ ∈ { } (ii) For every integer k 0 and every(cid:0) i 1, . . . , N , x(cid:1)(k+1) is the centroid of the cell of x(k) i.e. i (cid:98) i E (cid:98) x(k+1) = E X | X ∈ C (Γ(k)) = 1{XΓ(k)=x(ik)}X i i P(XΓ(k) = x(k)) i (still with the above degeneracy convention). There are clearly N! consistent representations of a sequence of Lloyd iterates, corresponding to the possible numbering of Γ(0). But then this numbering is frozen as k increases. It is also clear R that roundedness, convergence (in ( d)N) of such consistent representations does not depend on the ∞ ∞ selected representation. So is true for a possible limit x( ) of such sequences since Γ( ) will not | ∞ | depend on the selected representation. However on may have Γ( ) < N in case of an asymptotic merging of some of the components of the representation. One checks that under the assumptions we make (µ continuous, or convex support or splitting assumption on Γ(0)) no merging occurs at ﬁnite range. Throughout the paper (x(k)) ≥ will always denote a consistent representation of the sequence of k 0 iterates Γ(k)) ≥ . These remark lead naturally to the following deﬁnition k 0 → ∞ → Deﬁnition 2.2 (Convergence of iterated grids). We will say that Γ(k) Γ( ) (converges) as k ∞ R ∞ + if there exists a constant representation (x(k)) ≥ converging in ( d)N toward x( ) such that k 0 ∞ { } Γ( ) = x(k), i = 1, . . . , N . i Several speciﬁc results established in what follows are known in the literature, but we chose to provide all proofs for self-completeness of the paper and reader’s convenience. Let us ﬁrst recall a basic fact which is at the origin of the eﬃciency of the Lloyd algorithm. Lemma 2.1. The iteration of Lloyd’s algorithm makes the quantization error decrease. ≤ (cid:98) (cid:98) e(Γ(k+1), X) e(Γ(k), X). (cid:98) (cid:98) (cid:98) (cid:98) (cid:54) E | P Furthermore, e(Γ(k+1), X) < e(Γ(k), X) as long as XΓ(k) = (X XΓ(k)) with positive -probability. E | P ∈ N P Conversely, if XΓ(k0) = (X XΓ(k0)) -a.s. for an integer k , then XΓ(k) = XΓ(k0) -a.s. for every ≥ 0 k k . 0 7 ##LTLine## ##LTLine##

text: Γ(0)

text: Rd.

text: For

text: every

text: k

text: E

text: (I)Centroid

text: updating

text: X

text: XΓ(k)

text: E

text: i

text: N

text: P(XΓ(k)=x(k))

text: i

text: (II)Voronoi

text: cells

text: re-allocation

text: with

text: the

text: following

text: degeneracy

text: convention:

text: if

text: P(XΓ(k)

text: x(k))

text: P(X

text: C

text: (Γ(k)))

text: then

text: x(k).

text: i

text: i

text: i

text: We

text: need

text: now

text: to

text: formalize

text: in

text: a

text: more

text: precise

text: way

text: what

text: can

text: be

text: a

text: consistent

text: connection

text: between

text: the

text: sequence

text: of

text: iterated

text: grids

text: (Γ(k))

text: in

text: the

text: Lloyd

text: procedure

text: and

text: the

text: N-tuples

text: that

text: can

text: be

text: associated

text: k

text: to

text: their

text: values.

text: Deﬁnition

text: Let

text: (Γ(k))

text: be

text: a

text: sequence

text: of

text: iterates

text: of

text: the

text: Lloyd

text: procedure

text: where

text: N.

text: A

text: k

text: sequence

text: of

text: N-tuples

text: (x(k))

text: is

text: a

text: consistent

text: representation

text: of

text: the

text: sequence

text: Γ(k)

text: if

text: k

text: (i)

text: Γ(k)

text: x(k),

text: i

text: N

text: i

text: (ii)

text: For

text: every

text: integer

text: k

text: and

text: i

text: N

text: is

text: the

text: centroid

text: of

text: the

text: cell

text: of

text: x(k)

text: i.e.

text: i

text: i

text: E

text: E

text: X

text: X

text: C

text: (Γ(k))

text: i

text: i

text: P(XΓ(k)

text: x(k))

text: i

text: (still

text: with

text: the

text: above

text: degeneracy

text: convention).

text: There

text: are

text: clearly

text: N!

text: consistent

text: representations

text: of

text: a

text: sequence

text: of

text: Lloyd

text: iterates,

text: corresponding

text: to

text: the

text: possible

text: numbering

text: of

text: But

text: then

text: this

text: numbering

text: is

text: frozen

text: as

text: k

text: increases.

text: It

text: is

text: also

text: clear

text: R

text: that

text: roundedness,

text: convergence

text: (in

text: d)N)

text: of

text: such

text: consistent

text: representations

text: does

text: not

text: depend

text: on

text: the

text: selected

text: representation.

text: So

text: is

text: true

text: for

text: a

text: possible

text: limit

text: x(

text: of

text: such

text: sequences

text: since

text: Γ(

text: will

text: not

text: depend

text: on

text: the

text: selected

text: representation.

text: However

text: on

text: may

text: have

text: Γ(

text: N

text: in

text: case

text: of

text: an

text: asymptotic

text: merging

text: of

text: some

text: of

text: the

text: components

text: of

text: the

text: representation.

text: One

text: checks

text: that

text: under

text: the

text: assumptions

text: we

text: make

text: (µ

text: continuous,

text: or

text: convex

text: support

text: or

text: splitting

text: assumption

text: on

text: no

text: merging

text: occurs

text: at

text: ﬁnite

text: range.

text: Throughout

text: the

text: paper

text: (x(k))

text: will

text: always

text: denote

text: a

text: consistent

text: representation

text: of

text: the

text: sequence

text: of

text: k

text: iterates

text: Γ(k))

text: These

text: remark

text: lead

text: naturally

text: to

text: the

text: following

text: deﬁnition

text: k

text: Deﬁnition

text: (Convergence

text: of

text: iterated

text: grids).

text: We

text: will

text: say

text: that

text: Γ(k)

text: Γ(

text: (converges)

text: as

text: k

text: R

text: if

text: there

text: exists

text: a

text: constant

text: representation

text: (x(k))

text: converging

text: in

text: d)N

text: toward

text: x(

text: such

text: that

text: k

text: Γ(

text: x(k),

text: i

text: N

text: i

text: Several

text: speciﬁc

text: results

text: established

text: in

text: what

text: follows

text: are

text: known

text: in

text: the

text: literature,

text: but

text: we

text: chose

text: to

text: provide

text: all

text: proofs

text: for

text: self-completeness

text: of

text: the

text: paper

text: and

text: reader’s

text: convenience.

text: Let

text: us

text: ﬁrst

text: recall

text: a

text: basic

text: fact

text: which

text: is

text: at

text: the

text: origin

text: of

text: the

text: eﬃciency

text: of

text: the

text: Lloyd

text: algorithm.

text: Lemma

text: The

text: iteration

text: of

text: Lloyd’s

text: algorithm

text: makes

text: the

text: quantization

text: error

text: decrease.

text: X)

text: e(Γ(k),

text: X).

text: E

text: P

text: Furthermore,

text: X)

text: e(Γ(k),

text: X)

text: as

text: long

text: as

text: XΓ(k)

text: (X

text: XΓ(k))

text: with

text: positive

text: -probability.

text: E

text: P

text: N

text: P

text: Conversely,

text: if

text: (X

text: -a.s.

text: for

text: an

text: integer

text: k

text: then

text: XΓ(k)

text: -a.s.

text: for

text: every

text: k

text: k

text: ##LTLine##

text: ##LTLine##


text: H ⊂ and U = (supp(µ)) (closed convex hull of the support of µ) since we assume that Γ(0) U: then, ∈ N for every k , so will be the case for Γ(k) as emphasized in the description of the procedure. Claim (b) emphasizes that, by an appropriate choice of (the quadratic quantization error) Γ(0) may imply the boundedness of the whole sequence of iterates (Γ(k)) ≥ . This approach known by k 0 practitioners as the splitting method is investigated in the next subsection. We will prove this theorem step by step, establishing intermediary results, often under less stringent assumptions than the above theorem, which may have their own interest. 2.2 Possibly unbounded inputs: the splitting method In practical computations, if one aims at computing (hopefully) optimal quantization grids (or CV T ) of X on a wide range of levels N (see e.g. the website www.quantize.maths-fi.com), the so-called splitting method appears as an extremely eﬃcient “level-by-level” procedure. The principle is to compute the grids in a telescopic manner based on their size N: assume we have access to an optimal grid of size N. Imagine we add to this grid an (N + 1)th U-valued component e.g. sampled randomly from the distribution of X (or any U-supported distribution). Doing so, we make up a grid which has for sure a lower quadratic mean quantization error than any grid with N points. This grid of size N + 1 is likely to lie in the attracting basin of the optimal quadratic quantizer (or CV T ) at level N + 1. This is often observed in practice and, even if not optimal, it provides at least very good quantizers. Its main the trade-oﬀ is that it requires a systematic, hence heavily time consuming, simulation. Many variants or potential improvements can be implemented (like adding an optimal ≥ quantizer of size N 2 at each new initialization to directly obtain (hopefully) optimal quantizers of 0 size N + N (see e.g. [13]). 0 ≥ Splitting Assumption (on the starting grid): Let N 1 be such that card(suppµ) > N (where P ∗ { ∗ } ⊂ − P µ = ). Let Γ − = x , i = 1, . . . , n U be an optimal grid of size N 1 for and let ∈ X \ N∗ 1 i (cid:110) (cid:111) X (0) x supp(µ) Γ − . The Lloyd algorithm is initialized as follows: N N 1 ∗ ∪ { } ∗ ∗ · · · ∗ Γ(0) = Γ − x(0) = x , x , , x − , x(0) . (2.5) N 1 N 1 2 N 1 N One natural way to generate the additional element x(0) is in practice to simulate randomly a copy N of X (in fact one can also simulate a copy of a random vector whose distribution is equivalent to that of X, see the remark below). Remark. If µ has a density ρ, it is more eﬃcient to simulate according to the distribution whose probability density is proportional to ρd+d2 (one checks that this function is integrable if X ∈ L2+η(P) d for an η > 0, see e.g. [7]). The reason is that the resu≥lting distribution µd = κdρd+2 .λd provides the best random N(cid:110)-quantizers of(cid:0)µ = ρ.λd for ev(cid:1)ery N 1 in the following sense(cid:111): the asymptotic minimization problem inf lNim→s+u∞p N d2 E 1≤mi≤inN |X − Yi|2 , Y1, . . . , YN i.i.d., ⊥⊥ X, Y1 ∼ ν ⊥⊥ has ν = µ as a solution ( denotes here independence). d If the Splitting Assumption on the initialization of the procedure is satisﬁed, the grids of the iter- ations in the Lloyd algorithm share an interesting property (which implies their global boundedness). The arguments developed in the proof below are close to those used in the proof of the existence of an optimal quantizer at level N (see e.g. [12, 7]). 9 ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: H

text: and

text: U

text: (supp(µ))

text: (closed

text: convex

text: hull

text: of

text: the

text: support

text: of

text: µ)

text: since

text: we

text: assume

text: that

text: U:

text: then,

text: N

text: for

text: every

text: k

text: so

text: will

text: be

text: the

text: case

text: for

text: Γ(k)

text: as

text: emphasized

text: in

text: the

text: description

text: of

text: the

text: procedure.

text: Claim

text: (b)

text: emphasizes

text: that,

text: by

text: an

text: appropriate

text: choice

text: of

text: (the

text: quadratic

text: quantization

text: error)

text: may

text: imply

text: the

text: boundedness

text: of

text: the

text: whole

text: sequence

text: of

text: iterates

text: (Γ(k))

text: This

text: approach

text: known

text: by

text: k

text: practitioners

text: as

text: the

text: splitting

text: method

text: is

text: investigated

text: in

text: the

text: next

text: subsection.

text: We

text: will

text: prove

text: this

text: theorem

text: step

text: by

text: step,

text: establishing

text: intermediary

text: results,

text: often

text: under

text: less

text: stringent

text: assumptions

text: than

text: the

text: above

text: theorem,

text: which

text: may

text: have

text: their

text: own

text: interest.

text: Possibly

text: unbounded

text: inputs:

text: the

text: splitting

text: method

text: In

text: practical

text: computations,

text: if

text: one

text: aims

text: at

text: computing

text: (hopefully)

text: optimal

text: quantization

text: grids

text: (or

text: CV

text: T

text: of

text: X

text: on

text: a

text: wide

text: range

text: of

text: levels

text: N

text: (see

text: e.g.

text: the

text: website

text: the

text: so-called

text: splitting

text: method

text: appears

text: as

text: an

text: extremely

text: eﬃcient

text: “level-by-level”

text: procedure.

text: The

text: principle

text: is

text: to

text: compute

text: the

text: grids

text: in

text: a

text: telescopic

text: manner

text: based

text: on

text: their

text: size

text: N:

text: assume

text: we

text: have

text: access

text: to

text: an

text: optimal

text: grid

text: of

text: size

text: N.

text: Imagine

text: we

text: add

text: to

text: this

text: grid

text: an

text: (N

text: U-valued

text: component

text: e.g.

text: sampled

text: randomly

text: from

text: the

text: distribution

text: of

text: X

text: (or

text: any

text: U-supported

text: distribution).

text: Doing

text: so,

text: we

text: make

text: up

text: a

text: grid

text: which

text: has

text: for

text: sure

text: a

text: lower

text: quadratic

text: mean

text: quantization

text: error

text: than

text: any

text: grid

text: with

text: N

text: points.

text: This

text: grid

text: of

text: size

text: N

text: is

text: likely

text: to

text: lie

text: in

text: the

text: attracting

text: basin

text: of

text: the

text: optimal

text: quadratic

text: quantizer

text: (or

text: CV

text: T

text: at

text: level

text: N

text: This

text: is

text: often

text: observed

text: in

text: practice

text: and,

text: even

text: if

text: not

text: optimal,

text: it

text: provides

text: at

text: least

text: very

text: good

text: quantizers.

text: Its

text: main

text: the

text: trade-oﬀ

text: is

text: that

text: it

text: requires

text: a

text: systematic,

text: hence

text: heavily

text: time

text: consuming,

text: simulation.

text: Many

text: variants

text: or

text: potential

text: improvements

text: can

text: be

text: implemented

text: (like

text: adding

text: an

text: optimal

text: quantizer

text: of

text: size

text: N

text: at

text: each

text: new

text: initialization

text: to

text: directly

text: obtain

text: (hopefully)

text: optimal

text: quantizers

text: of

text: size

text: N

text: N

text: (see

text: e.g.

text: Splitting

text: Assumption

text: (on

text: the

text: starting

text: grid):

text: Let

text: N

text: be

text: such

text: that

text: card(suppµ)

text: N

text: (where

text: P

text: P

text: µ

text: Let

text: Γ

text: x

text: i

text: n

text: U

text: be

text: an

text: optimal

text: grid

text: of

text: size

text: N

text: for

text: and

text: let

text: X

text: N∗

text: i

text: X

text: x

text: supp(µ)

text: Γ

text: The

text: Lloyd

text: algorithm

text: is

text: initialized

text: as

text: follows:

text: N

text: N

text: Γ

text: x

text: x

text: x

text: N

text: N

text: N

text: N

text: One

text: natural

text: way

text: to

text: generate

text: the

text: additional

text: element

text: is

text: in

text: practice

text: to

text: simulate

text: randomly

text: a

text: copy

text: N

text: of

text: X

text: (in

text: fact

text: one

text: can

text: also

text: simulate

text: a

text: copy

text: of

text: a

text: random

text: vector

text: whose

text: distribution

text: is

text: equivalent

text: to

text: that

text: of

text: X,

text: see

text: the

text: remark

text: below).

text: Remark.

text: If

text: µ

text: has

text: a

text: density

text: ρ,

text: it

text: is

text: more

text: eﬃcient

text: to

text: simulate

text: according

text: to

text: the

text: distribution

text: whose

text: probability

text: density

text: is

text: proportional

text: to

text: (one

text: checks

text: that

text: this

text: function

text: is

text: integrable

text: if

text: X

text: d

text: for

text: an

text: η

text: see

text: e.g.

text: The

text: reason

text: is

text: that

text: the

text: resu≥lting

text: distribution

text: µd

text: .λd

text: provides

text: the

text: best

text: random

text: ρ.λd

text: for

text: N

text: in

text: the

text: following

text: the

text: asymptotic

text: minimization

text: problem

text: inf

text: lNim→s+u∞p

text: N

text: E

text: |X

text: YN

text: i.i.d.,

text: X,

text: ν

text: has

text: ν

text: µ

text: as

text: a

text: solution

text: denotes

text: here

text: independence).

text: d

text: If

text: the

text: Splitting

text: Assumption

text: on

text: the

text: initialization

text: of

text: the

text: procedure

text: is

text: satisﬁed,

text: the

text: grids

text: of

text: the

text: iter-

text: ations

text: in

text: the

text: Lloyd

text: algorithm

text: share

text: an

text: interesting

text: property

text: (which

text: implies

text: their

text: global

text: boundedness).

text: The

text: arguments

text: developed

text: in

text: the

text: proof

text: below

text: are

text: close

text: to

text: those

text: used

text: in

text: the

text: proof

text: of

text: the

text: existence

text: of

text: an

text: optimal

text: quantizer

text: at

text: level

text: N

text: (see

text: e.g.

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: Proposition 2.1. Assume the Splitting Assumption (2.5). (a) The quantization error induced by the grid Γ(0) deﬁned by (2.5) is strictly smaller than e − (X) − (cid:13) ∗ (cid:13) | | N 1 (i.e. that of the optimal (N 1)-quan(cid:13)tizer Γ(cid:98) )(cid:13)so that Γ(k) = N and − N 1 − ≤ e(Γ(k), X) = X XΓ(k) e(Γ(0), X) < e − (X). 2 N 1 R ⊂ R (b) The sequence of iterated grids (Γ(k)) ≥ is bounded in d i.e. there exists a compact set K d k 0 such that ∀ ∈ N ⊂ k , Γ(k) K. (c) All the limiting values of the sequence of consistent representations (x(k)) ≥ have N pairwise k 0 distinct components (i.e. the the sequence of grids (Γ(k)) ≥ has asymptotically full size full size N). k 0 (cid:16) (cid:17) Proof: (a) The (squared) quadratic means quantization error (or “distortion value”) induced by Γ(0) satisﬁes: e(Γ(0), X)2 = G(x∗, x∗, · · · , x∗ − , x(0)) = E min |X − x(0)|2 . 1 2 (N 1) N ≤ ≤ i 1 i N ∗ ≤ ≤ − | ∗ − | ∈ where x(0) = x , 1 j N 1. Let ε = 1 min ≤ ≤ − x x(0) . For every ξ B(x(0), ε), j j 3 1 i N 1 i N N | − | ≥ | ∗ − | − | − | ≥ − | − | ξ x(0) x x(0) ξ x(0) 3ε ε = 2ε > ξ x(0) 2. i i N N N { ∈ } (0) Consequently, on the event A = X B(x , ε) , we have ε N | − | | − | | − | min X(ω) x(0) 2 = X(ω) x(0) 2 > min X(ω) x(0) ≤ ≤ i 2 N 2 ≤ ≤ − i 2 1 i N 1 i N 1 | − | ≤ | − | whereas we always have that min ≤ ≤ X(ω) x(0) 2 min ≤ ≤ − X(ω) x(0) 2. On the other ∈ P 1 i N P i 1 i N 1 i hand we know that x(0) supp( ) so that (A ) > 0 which implies in turn that X ε N e(Γ(0), X)2 < e − (X)2. N 1 One concludes by noting that Lloyd’s algorithm makes the sequence of (squared) quadratic quantiza- tion error induced by the iterated grids non-increasing. | | → ∞ (ϕ(k)) (b) Suppose that there exists a subsequence (ϕ(k)) and a component i such that x + as → ∞ 0 { ·i0· · } k + . Then, by re-extracting ﬁnitely many subsequences, we can split the set 1, , N into two (cid:110) (cid:12) (cid:12) (cid:111) disjoint non empty subsets I and Ic and ﬁnd a subsequ(cid:12)ence (s(cid:12)till denoted (ϕ(k)) ≥ for convenience) k 0 such that ∈ { } → ∞ (cid:54) ∅ I = (cid:110)j 1 . . . , N such that x(ϕ(k)) + =(cid:111) j and Ic = j ∈ {1 . . . , N} such that x(ϕ(k)) → x∞ ∈ Rd . j j (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) It is clear that ∀ ξ ∈ Rd, lim min ξ − x(ϕ(k)) 2 = lim min ξ − x(ϕ(k)) 2 = min |ξ − x∞|2. → ∞ ≤ ≤ i →∞ ∈ j ∈ j k + 1 i N k j Ic j Ic Therefore, it follows from Fatou’s Lemma that 10 ##LTLine##

text: Proposition

text: Assume

text: the

text: Splitting

text: Assumption

text: (a)

text: The

text: quantization

text: error

text: induced

text: by

text: the

text: grid

text: deﬁned

text: by

text: is

text: strictly

text: smaller

text: than

text: e

text: (X)

text: N

text: (i.e.

text: that

text: of

text: the

text: optimal

text: (N

text: that

text: Γ(k)

text: N

text: and

text: N

text: e(Γ(k),

text: X)

text: X

text: XΓ(k)

text: X)

text: e

text: (X).

text: N

text: R

text: R

text: (b)

text: The

text: sequence

text: of

text: iterated

text: grids

text: (Γ(k))

text: is

text: bounded

text: in

text: d

text: i.e.

text: there

text: exists

text: a

text: compact

text: set

text: K

text: d

text: k

text: such

text: that

text: N

text: k

text: Γ(k)

text: K.

text: (c)

text: All

text: the

text: limiting

text: values

text: of

text: the

text: sequence

text: of

text: consistent

text: representations

text: (x(k))

text: have

text: N

text: pairwise

text: k

text: distinct

text: components

text: (i.e.

text: the

text: the

text: sequence

text: of

text: grids

text: (Γ(k))

text: has

text: asymptotically

text: full

text: size

text: full

text: size

text: N).

text: k

text: Proof:

text: (a)

text: The

text: (squared)

text: quadratic

text: means

text: quantization

text: error

text: (or

text: “distortion

text: value”)

text: induced

text: by

text: satisﬁes:

text: G(x∗,

text: x∗,

text: x∗

text: E

text: min

text: |X

text: (N

text: N

text: i

text: i

text: N

text: where

text: x

text: j

text: N

text: Let

text: ε

text: min

text: x

text: For

text: every

text: ξ

text: ε),

text: j

text: j

text: i

text: N

text: i

text: N

text: N

text: ξ

text: x

text: ξ

text: 3ε

text: ε

text: 2ε

text: ξ

text: i

text: i

text: N

text: N

text: N

text: Consequently,

text: on

text: the

text: event

text: A

text: X

text: B(x

text: ε)

text: we

text: have

text: ε

text: N

text: min

text: X(ω)

text: X(ω)

text: min

text: X(ω)

text: i

text: N

text: i

text: i

text: N

text: i

text: N

text: whereas

text: we

text: always

text: have

text: that

text: min

text: X(ω)

text: min

text: X(ω)

text: On

text: the

text: other

text: P

text: i

text: N

text: P

text: i

text: i

text: N

text: i

text: hand

text: we

text: know

text: that

text: supp(

text: so

text: that

text: (A

text: which

text: implies

text: in

text: turn

text: that

text: X

text: ε

text: N

text: e

text: N

text: One

text: concludes

text: by

text: noting

text: that

text: Lloyd’s

text: algorithm

text: makes

text: the

text: sequence

text: of

text: (squared)

text: quadratic

text: quantiza-

text: tion

text: error

text: induced

text: by

text: the

text: iterated

text: grids

text: non-increasing.

text: (ϕ(k))

text: (b)

text: Suppose

text: that

text: there

text: exists

text: a

text: subsequence

text: (ϕ(k))

text: and

text: a

text: component

text: i

text: such

text: that

text: x

text: as

text: ·i0·

text: k

text: Then,

text: by

text: re-extracting

text: ﬁnitely

text: many

text: subsequences,

text: we

text: can

text: split

text: the

text: set

text: N

text: into

text: two

text: disjoint

text: non

text: empty

text: subsets

text: I

text: and

text: Ic

text: and

text: ﬁnd

text: a

text: denoted

text: (ϕ(k))

text: for

text: convenience)

text: k

text: such

text: that

text: I

text: N

text: such

text: that

text: x(ϕ(k))

text: j

text: and

text: Ic

text: j

text: N}

text: such

text: that

text: x(ϕ(k))

text: x∞

text: Rd

text: j

text: j

text: It

text: is

text: clear

text: that

text: ξ

text: Rd,

text: lim

text: min

text: ξ

text: x(ϕ(k))

text: lim

text: min

text: ξ

text: x(ϕ(k))

text: min

text: |ξ

text: i

text: j

text: j

text: k

text: i

text: N

text: k

text: j

text: Ic

text: j

text: Ic

text: Therefore,

text: it

text: follows

text: from

text: Fatou’s

text: Lemma

text: that

text: ##LTLine##


text: A. Prior Work on 3D k-coverage results proposed in [2]. We end the paper with conclusion and potential research directions for future. There are relatively fewer works done to address the problem of 3D k-coverage as compared to the 2D version of III. COMPUTING THE VOLUME OF SIXSOID the problem. In [1], [2] the authors make signiﬁcant progress S The Sixsoid which we denote by (R) is deﬁned as the 3- on this problem. They discuss the relevance of Reuleaux D object obtained due to the intersection of six spheres placed Tetrahedron in various issues dealing with connectivity and k- on the centers of the faces of a cube of side-length R. The coverage in 3D. Prior to that the following works disscuss the radius of each sphere is R. In this section, we compute the 3D version; in [16], authors propose a coverage optimization S volume V of (R). Our basic strategy is to take a horizontal algorithm based on sampling for 3D underwater WSNs. [12] cross section (via a sliding plane) of the cube at a distance of x proposes an optimal polynomial time algorithm based on from the top of the cube and perform the following integration, voronoi diagram and graph search algorithms, in [9] authors (cid:90) (cid:90) suggest algorithms to ensure k-coverage of every point in a ﬁeld where sensors may have same or different sensing radii, [10] deﬁnes the minimum number of sensors for k- R R/2 V = A(x) dx = 2 A(x) dx coverage with a probability value, [15] studies the effect of 0 0 sensing radius on the probability of k-coverage, [7] proposes an optimal deployment strategy to deal with full coverage and 2-connectivity, [4] brought forward a sensor placement model where A(x) is the area of the cross Dsection and the last based on Voronoi structure to cover a 3D region, in [14], equality follows due to the symmetry of (R). authors provide a study on connectivity and coverage issues in Henceforth, we will use the following notation re- a randomly deployed 3D WSN. In this paper, we compare our garding the geometry of the objects involved in this proposed Sixsoid based k-coverage model with the existing section. Let F (top), F (bottom), F (left), F (right), Reuleaux Tetrahedron based model [1]. Comparison has been F (front), F (xb1ack) be thxe2 faces of they1 cube andy2we de- done in terms of volume of k-coverage, sensor spatial density nozt1e the respz2ective spheres (centered at face centers) by in 3D and placement and packing in 3D. S , S , S , S , S , S . We will denote the sliding plane II. OUR CONTRIBUTION bwyxh1icPhxxi2sanodby1talientye2drαbiyz1btheez2iitnsterrasdeicutsio. nLoeft PCαiwibthe Sthe wcihrecrlee In a previous work [13], the authors used a convex α ∈ {x, y, z} and i ∈ {1, 2}. In the remaindxer of thiαsisection body that resembles a super-ellipse for k-coverage in 2D we show the behavior of the cross-section as the plane P x homogeneous WSN. This model [13] showed much better slides from x = 0 to x = R. 2 efﬁciency in terms of area of k-coverage, energy consumption ≤ ≤ atdThnoeedtnrekarh-eiceqnoduvri[oer1enr]am.gMieesnomtftuioovrdftahetleeledrswsebixtynhtuetRnhmdeebeuefdlarecattouoftxh3saTeDtrnicsaobonnyrgsslietdaaeks[r1iinc]n.gogmTRahpeia“surseluwedpaoeurtrkox- c0inocntrocOeeabRns(cid:113)stee/rsir2cva,anctrdiixorc1Cnlex1ms1:o=anFnooCdtroxnar2ilxcla2at0llx≤y=drxeRxc1r/.e2a.AsRel/sso,2,raxCs2x1xmaovnnadoriteCosnxi2fcraoalmlrye ≤ ≤ elliptical” tile has proven to be much better than the Reuleaux Observation 2: For 0 x R/2, r = r = r = Triangle based model [13], in this work we extend that idea − y1 y2 z1 to 3D. The main hurdle was to compute the volume of the rz2 = 3R42 + Rx x2. solid (Sixsoid) generated out of our construction. Unlike the − Lemma 1: A(√x) = π(2Rx x2) from x = 0 to x = l , Reuleaux Tetrahedron its volume was not already known. − ≈ 1 Another reason for opting our construction is its resemblence where l1 = R(3 4 7) 0.0886R to a superellipsoid because of which it ﬁts much better in (cid:112)Proof: We observe that, A(x) is exactly C as P 3D rather than a Reuleaux Tetrahedron. Moreover, Sixsoid slides below x = 0. So to compute A(x) we onlyx2need txo provides a practical and easier packing in 3D. Once we ﬁll compute the radius r of C . This value can be computed the FoI with cubes of side length R, a Sixsoid is formed by as R2 − (R − x)2,xw2hich pxr2oves the claim regarding A(x). the overlapping of six sensors lying on the six face centers of Now inorder to know l (the event when the cross section 1 a cube. So, every cube contains a Sixsoid inside it. When we changes), we need to ﬁnd the value of x at which C is consider packing in 3D, cubes are space ﬁlling. We propose a tangential to C , this is also the instance at which Cx2 is result in a later section that states that our deployment strategy tangential to eazc1h C , C and C . To ﬁnd this x we xn2eed ensures 4-coverage of the entire FoI along with fact that to s(cid:114)olve the followinyg1 equya2tion, rxz21= R/2 + rz1 approximately 68% of it is 6-covered. Thus, the Sixsoid based (cid:112) model ensures at least 4-coverage of the entire FoI. Packing of Reuleaux Tetrahedron in 3D as proposed in [1] is harder 3R2 − − R (cid:112) + Rx x2 = 2Rx x2 + to achieve and it is not feasible for practical deployment. In 4 2 the subsequent sections, we calculate the volume of the Sixsoid 3R2 − (cid:112) − R2 − + Rx x2 = 2Rx x2 + + R 2Rx x2 with the supporting theorems and compare our results with the 4 4 Reuleaux Tetrahedron based model. In the remaining part of R − − x = 2Rx x2 the paper, we discuss the computation of volume of a Sixsoid 2 in Section 3. In Section 4 we discuss the deployment and − R2 2x2 3Rx + = 0 packing strategy in 3D that exploits the structure of Sixsoid. 4 Section 5 is devoted to the comparison of our model with the ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: A.

label: section

text: Prior

text: Work

text: on

text: k-coverage

text: results

text: proposed

text: in

text: We

text: end

text: the

text: paper

text: with

text: conclusion

text: and

text: potential

text: research

text: directions

text: for

text: future.

text: There

text: are

text: relatively

text: fewer

text: works

text: done

text: to

text: address

text: the

text: problem

text: of

text: k-coverage

text: as

text: compared

text: to

text: the

text: version

text: of

text: III.

text: COMPUTING

text: THE

text: VOLUME

text: OF

text: SIXSOID

text: the

text: problem.

text: In

text: the

text: authors

text: make

text: signiﬁcant

text: progress

text: S

text: The

text: Sixsoid

text: which

text: we

text: denote

text: by

text: (R)

text: is

text: deﬁned

text: as

text: the

text: on

text: this

text: problem.

text: They

text: discuss

text: the

text: relevance

text: of

text: Reuleaux

text: D

text: object

text: obtained

text: due

text: to

text: the

text: intersection

text: of

text: six

text: spheres

text: placed

text: Tetrahedron

text: in

text: various

text: issues

text: dealing

text: with

text: connectivity

text: and

text: k-

text: on

text: the

text: centers

text: of

text: the

text: faces

text: of

text: a

text: cube

text: of

text: side-length

text: R.

text: The

text: coverage

text: in

text: Prior

text: to

text: that

text: the

text: following

text: works

text: disscuss

text: the

text: radius

text: of

text: each

text: sphere

text: is

text: R.

text: In

text: this

text: section,

text: we

text: compute

text: the

text: version;

text: in

text: authors

text: propose

text: a

text: coverage

text: optimization

text: S

text: volume

text: V

text: of

text: (R).

text: Our

text: basic

text: strategy

text: is

text: to

text: take

text: a

text: horizontal

text: algorithm

text: based

text: on

text: sampling

text: for

text: underwater

text: WSNs.

text: cross

text: section

text: (via

text: a

text: sliding

text: plane)

text: of

text: the

text: cube

text: at

text: a

text: distance

text: of

text: x

text: proposes

text: an

text: optimal

text: polynomial

text: time

text: algorithm

text: based

text: on

text: from

text: the

text: top

text: of

text: the

text: cube

text: and

text: perform

text: the

text: following

text: integration,

text: voronoi

text: diagram

text: and

text: graph

text: search

text: algorithms,

text: in

text: authors

text: suggest

text: algorithms

text: to

text: ensure

text: k-coverage

text: of

text: every

text: point

text: in

text: a

text: ﬁeld

text: where

text: sensors

text: may

text: have

text: same

text: or

text: different

text: sensing

text: radii,

text: deﬁnes

text: the

text: minimum

text: number

text: of

text: sensors

text: for

text: k-

text: R

text: V

text: A(x)

text: dx

text: A(x)

text: dx

text: coverage

text: with

text: a

text: probability

text: value,

text: studies

text: the

text: effect

text: of

text: sensing

text: radius

text: on

text: the

text: probability

text: of

text: k-coverage,

text: proposes

text: an

text: optimal

text: deployment

text: strategy

text: to

text: deal

text: with

text: full

text: coverage

text: and

text: brought

text: forward

text: a

text: sensor

text: placement

text: model

text: where

text: A(x)

text: is

text: the

text: area

text: of

text: the

text: cross

text: Dsection

text: and

text: the

text: last

text: based

text: on

text: Voronoi

text: structure

text: to

text: cover

text: a

text: region,

text: in

text: equality

text: follows

text: due

text: to

text: the

text: symmetry

text: of

text: (R).

text: authors

text: provide

text: a

text: study

text: on

text: connectivity

text: and

text: coverage

text: issues

text: in

text: Henceforth,

text: we

text: will

text: use

text: the

text: following

text: notation

text: re-

text: a

text: randomly

text: deployed

text: WSN.

text: In

text: this

text: paper,

text: we

text: compare

text: our

text: garding

text: the

text: geometry

text: of

text: the

text: objects

text: involved

text: in

text: this

text: proposed

text: Sixsoid

text: based

text: k-coverage

text: model

text: with

text: the

text: existing

text: section.

text: Let

text: F

text: (top),

text: F

text: (bottom),

text: F

text: (left),

text: F

text: (right),

text: Reuleaux

text: Tetrahedron

text: based

text: model

text: Comparison

text: has

text: been

text: F

text: (front),

text: F

text: be

text: faces

text: of

text: cube

text: de-

text: done

text: in

text: terms

text: of

text: volume

text: of

text: k-coverage,

text: sensor

text: spatial

text: density

text: the

text: spheres

text: (centered

text: at

text: face

text: centers)

text: by

text: in

text: and

text: placement

text: and

text: packing

text: in

text: S

text: S

text: S

text: S

text: S

text: S

text: We

text: will

text: denote

text: the

text: sliding

text: plane

text: II.

text: OUR

text: CONTRIBUTION

text: nLoeft

text: PCαiwibthe

text: Sthe

text: wcihrecrlee

text: In

text: a

text: previous

text: work

text: the

text: authors

text: used

text: a

text: convex

text: α

text: {x,

text: y,

text: z}

text: and

text: i

text: In

text: the

text: remaindxer

text: of

text: thiαsisection

text: body

text: that

text: resembles

text: a

text: super-ellipse

text: for

text: k-coverage

text: in

text: we

text: show

text: the

text: behavior

text: of

text: the

text: cross-section

text: as

text: the

text: plane

text: P

text: x

text: homogeneous

text: WSN.

text: This

text: model

text: showed

text: much

text: better

text: slides

text: from

text: x

text: to

text: x

text: R.

text: efﬁciency

text: in

text: terms

text: of

text: area

text: of

text: k-coverage,

text: energy

text: consumption

text: elliptical”

text: tile

text: has

text: proven

text: to

text: be

text: much

text: better

text: than

text: the

text: Reuleaux

text: Observation

text: For

text: x

text: r

text: r

text: r

text: Triangle

text: based

text: model

text: in

text: this

text: work

text: we

text: extend

text: that

text: idea

text: to

text: The

text: main

text: hurdle

text: was

text: to

text: compute

text: the

text: volume

text: of

text: the

text: Rx

text: solid

text: (Sixsoid)

text: generated

text: out

text: of

text: our

text: construction.

text: Unlike

text: the

text: Lemma

text: A(√x)

text: from

text: x

text: to

text: x

text: l

text: Reuleaux

text: Tetrahedron

text: its

text: volume

text: was

text: not

text: already

text: known.

text: Another

text: reason

text: for

text: opting

text: our

text: construction

text: is

text: its

text: resemblence

text: where

text: to

text: a

text: superellipsoid

text: because

text: of

text: which

text: it

text: ﬁts

text: much

text: better

text: in

text: We

text: observe

text: that,

text: A(x)

text: is

text: exactly

text: C

text: as

text: P

text: rather

text: than

text: a

text: Reuleaux

text: Tetrahedron.

text: Moreover,

text: Sixsoid

text: slides

text: below

text: x

text: So

text: to

text: compute

text: A(x)

text: we

text: txo

text: provides

text: a

text: practical

text: and

text: easier

text: packing

text: in

text: Once

text: we

text: ﬁll

text: compute

text: the

text: radius

text: r

text: of

text: C

text: This

text: value

text: can

text: be

text: computed

text: the

text: FoI

text: with

text: cubes

text: of

text: side

text: length

text: R,

text: a

text: Sixsoid

text: is

text: formed

text: by

text: as

text: (R

text: the

text: claim

text: regarding

text: A(x).

text: the

text: overlapping

text: of

text: six

text: sensors

text: lying

text: on

text: the

text: six

text: face

text: centers

text: of

text: Now

text: inorder

text: to

text: know

text: l

text: (the

text: event

text: when

text: the

text: cross

text: section

text: a

text: cube.

text: So,

text: every

text: cube

text: contains

text: a

text: Sixsoid

text: inside

text: it.

text: When

text: we

text: changes),

text: we

text: need

text: to

text: ﬁnd

text: the

text: value

text: of

text: x

text: at

text: which

text: C

text: is

text: consider

text: packing

text: in

text: cubes

text: are

text: space

text: ﬁlling.

text: We

text: propose

text: a

text: tangential

text: to

text: C

text: this

text: is

text: also

text: the

text: instance

text: at

text: which

text: is

text: result

text: in

text: a

text: later

text: section

text: that

text: states

text: that

text: our

text: deployment

text: strategy

text: tangential

text: to

text: C

text: C

text: and

text: C

text: To

text: ﬁnd

text: this

text: x

text: we

text: ensures

text: of

text: the

text: entire

text: FoI

text: along

text: with

text: fact

text: that

text: to

text: the

text: approximately

text: of

text: it

text: is

text: Thus,

text: the

text: Sixsoid

text: based

text: model

text: ensures

text: at

text: least

text: of

text: the

text: entire

text: FoI.

text: Packing

text: of

text: Reuleaux

text: Tetrahedron

text: in

text: as

text: proposed

text: in

text: is

text: harder

text: R

text: Rx

text: to

text: achieve

text: and

text: it

text: is

text: not

text: feasible

text: for

text: practical

text: deployment.

text: In

text: the

text: subsequent

text: sections,

text: we

text: calculate

text: the

text: volume

text: of

text: the

text: Sixsoid

text: Rx

text: R

text: with

text: the

text: supporting

text: theorems

text: and

text: compare

text: our

text: results

text: with

text: the

text: Reuleaux

text: Tetrahedron

text: based

text: model.

text: In

text: the

text: remaining

text: part

text: of

text: R

text: x

text: the

text: paper,

text: we

text: discuss

text: the

text: computation

text: of

text: volume

text: of

text: a

text: Sixsoid

text: in

text: Section

text: In

text: Section

text: we

text: discuss

text: the

text: deployment

text: and

text: packing

text: strategy

text: in

text: that

text: exploits

text: the

text: structure

text: of

text: Sixsoid.

text: Section

text: is

text: devoted

text: to

text: the

text: comparison

text: of

text: our

text: model

text: with

text: the

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: √ ≤ ≤ − (cid:48) Fig. 3. For 0 x (2 10)R, A (x) is the union of regions 3 6 AEXF,GY HB,TICJ,LSKD A. Computing the 4-covered Volume To compute the volume of the FoI we need to compute ≤ ≤ Fig. 2. Cross-Section of A(x) is the enclosed region ABCD for l2 x the volume that is only 3-covered, as the remaining volume is R/2 (cid:113) 4-covered. We notice that as the horizonal plane slides from x = 0 to x = R/2, the topology of the cross section that is √ − − only 3-covered changes twice, thus to compute the volume R+ 5R2+48Rx 8x2 and s = rz1 = 3R42 + Rx x2. inside the cube that is only 3-covered have to perform an Thus ar(cid:32)ea of the square is (cid:33) integration similar to case of the Sixs√oid. It can be veriﬁe√d the − − two transitions happen at x = (2 10)R and x = (3 5)R √ 3 6 (cid:48) 4 − − 2 respectively. In the following we how A (x), the area of cross · 5R2 8x2 + 8Rx R section tha√t is only 3-covered, varies√ between x = 0 to 2 − − 4 x = (2 10) and between x = (3 5)R to x = R/2√. We 3 6 4 − omit the deta√ils of the expre(cid:104)ssion when x is between (2 (cid:105)10) − 3 6 (b) The area of a cap (say the cap AB) can be obtained an(cid:104)d x = (3 45)R. ((cid:105)present in an extended version of the paper) by subtracting the area of ∆OAB from the area of Lemma 4: A(cid:48)(x) = 8 R2−z2 − {(s2·θ − z(z−R/2))} + sector OAB which is equal to √ 2 2 √ 2 · (cid:48) − } − 8(cid:113)(s2 θ 3R2 ) for x = 0 to x = (2 10)R where 2 √ 4 3 6 √ − − (cid:48) − 1 · · − 1 · · − R z = R+ 5R2 8x2+8Rx, θ = sin 1(z), θ = sin 1( 3), s = s2 θ z (z ) − 4 r 2 2 2 2 Rx x2 + 3R2 (cid:113) 4 where θ =−∠AOB = 2 sin−1 z−z√R2 an−d in thPeroFoifg:ur(eSke3t.chT)hCeonarseidaerthtahte iscroosnsl-ysec3t-ioconvearseddeipsicttehde s = Rx x2 + 3R2 , z = R+ 5R2 8x2+8Rx union of regions AEXF, GY HB, TICJ, LSKD. A simple 4 4 but tideous(cid:16)calculation(cid:17)gives us(cid:18)the r(cid:113)esult. (cid:19) Putting the values of z and s and multiplying the area of the (cid:48) − cap by 4 gives us the desired result. We use observation 1, to Lemma 5: A (x) is equal to R2 + 4(2Rx conclude that the cross section doesn’t change for all values x2) cos−1 √ R − − 2R 2Rx − x2 − R2 − of x between l and R/2. Thus l = R/2. 2 2Rx x2 √ 4 3 4 − − π(2Rx x2) for x = (3 5)R to x = R. As a consequence of the previous results, we can conclude 4 2 the following: Proof: (Sketch) Consider the cross-section as depicted in (cid:34) (cid:35) the Figure 3. The area that is only 3-covered is the union of (cid:90) (cid:90) (cid:90) Theorem 1: regions AST, BUV, CWX, ZY D. Again a simple calculation gives us the result. l1 l2 R/2 (cid:48) V = 2 A(x) dx + A(x) dx + A(x) dx Theorem 2: The volume V inside a cube that is 4-covered 0 l1 l2 is (cid:34) (cid:35) (cid:90) (cid:90) (cid:90) In order to get a good estimate on the value of the above (cid:48) (cid:48) deﬁnite integral, we use Matlab to perform the numerical (cid:48) l1 l2 R/2 V = 2 A(x) dx + A(x) dx + A(x) dx integration. The value of V turns out to be approximately 0 l(cid:48) l(cid:48) 1 2 0.685R3. ##LTFigure## ##LTFigure## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine## ##LTLine##

label: caption

text: Fig.

text: For

text: x

text: A

text: (x)

text: is

text: the

text: union

text: of

text: regions

text: AEXF,GY

text: HB,TICJ,LSKD

text: A.

text: Computing

text: the

text: Volume

text: To

text: compute

text: the

text: volume

text: of

text: the

text: FoI

text: we

text: need

text: to

text: compute

text: Fig.

text: Cross-Section

text: of

text: A(x)

text: is

text: the

text: enclosed

text: region

text: ABCD

text: for

text: x

text: the

text: volume

text: that

text: is

text: only

text: as

text: the

text: remaining

text: volume

text: is

label: list

text: We

text: notice

text: that

text: as

text: the

text: horizonal

text: plane

text: slides

text: from

text: x

text: to

text: x

text: the

text: topology

text: of

text: the

text: cross

text: section

text: that

text: is

text: only

text: changes

text: twice,

text: thus

text: to

text: compute

text: the

text: volume

text: R+

text: and

text: s

text: Rx

text: inside

text: the

text: cube

text: that

text: is

text: only

text: have

text: to

text: perform

text: an

text: Thus

text: of

text: the

text: square

text: is

text: integration

text: similar

text: to

text: case

text: of

text: the

text: Sixs√oid.

text: It

text: can

text: be

text: veriﬁe√d

text: the

text: two

text: transitions

text: happen

text: at

text: x

text: and

text: x

text: respectively.

text: In

text: the

text: following

text: we

text: how

text: A

text: (x),

text: the

text: area

text: of

text: cross

text: R

text: section

text: tha√t

text: is

text: only

text: varies√

text: between

text: x

text: to

text: x

text: and

text: between

text: x

text: to

text: x

text: We

text: omit

text: the

text: deta√ils

text: of

text: the

text: when

text: x

text: is

text: between

text: (b)

text: The

text: area

text: of

text: a

text: cap

text: (say

text: the

text: cap

text: AB)

text: can

text: be

text: obtained

text: x

text: in

text: an

text: extended

text: version

text: of

text: the

text: paper)

text: by

text: subtracting

text: the

text: area

text: of

text: ∆OAB

text: from

text: the

text: area

text: of

text: Lemma

text: sector

text: OAB

text: which

text: is

text: equal

text: to

text: θ

text: for

text: x

text: to

text: x

text: where

text: R

text: z

text: R+

text: θ

text: sin

text: θ

text: sin

text: s

text: θ

text: z

text: (z

text: r

text: Rx

text: where

text: θ

text: =−∠AOB

text: an−d

text: in

text: s

text: Rx

text: z

text: R+

text: union

text: of

text: regions

text: AEXF,

text: GY

text: HB,

text: TICJ,

text: LSKD.

text: A

text: simple

text: but

text: Putting

text: the

text: values

text: of

text: z

text: and

text: s

text: and

text: multiplying

text: the

text: area

text: of

text: the

text: cap

text: by

text: gives

text: us

text: the

text: desired

text: result.

text: We

text: use

text: observation

text: to

text: Lemma

text: A

text: (x)

text: is

text: equal

text: to

text: conclude

text: that

text: the

text: cross

text: section

text: doesn’t

text: change

text: for

text: all

text: values

text: R

text: of

text: x

text: between

text: l

text: and

text: Thus

text: l

text: for

text: x

text: to

text: x

text: R.

text: As

text: a

text: consequence

text: of

text: the

text: previous

text: results,

text: we

text: can

text: conclude

text: the

text: following:

text: Proof:

text: (Sketch)

text: Consider

text: the

text: cross-section

text: as

text: depicted

text: in

text: the

text: Figure

text: The

text: area

text: that

text: is

text: only

text: is

text: the

text: union

text: of

text: Theorem

text: regions

text: AST,

text: BUV,

text: CWX,

text: ZY

text: D.

text: Again

text: a

text: simple

text: calculation

text: gives

text: us

text: the

text: result.

text: V

text: A(x)

text: dx

text: A(x)

text: dx

text: A(x)

text: dx

text: Theorem

text: The

text: volume

text: V

text: inside

text: a

text: cube

text: that

text: is

text: is

text: In

text: order

text: to

text: get

text: a

text: good

text: estimate

text: on

text: the

text: value

text: of

text: the

text: above

text: deﬁnite

text: integral,

text: we

text: use

text: Matlab

text: to

text: perform

text: the

text: numerical

text: V

text: A(x)

text: dx

text: A(x)

text: dx

text: A(x)

text: dx

text: integration.

text: The

text: value

text: of

text: V

text: turns

text: out

text: to

text: be

text: approximately

text: ##LTFigure##

text: ##LTFigure##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##


text: 1 Optimal Control with Noisy Time Andrew Lamperski Noah J. Cowan Abstract— This paper examines stochastic optimal control problems in stochastic control problems are derived, based on extensions of the which the state is perfectly known, but the controller’s measure of time classical Hamilton-Jacobi-Bellman equation. The results apply to a is a stochastic process derived from a strictly increasing Le´vy process. wide class of stochastic time changes given by strictly increasing We provide dynamic programming results for continuous-time ﬁnite- Le´vy processes. The dynamic programming principles are then spe- horizon control and specialize these results to solve a noisy-time variant of the linear quadratic regulator problem and a portfolio optimization cialized to give explicit solutions to time-changed versions of the problem with random trade activity rates. For the linear quadratic case, ﬁnite-horizon linear quadratic regulator and a portfolio optimization the optimal controller is linear and can be computed from a generalization problem. of the classical Riccati differential equation. Section deﬁnes the notation used in the paper, states the necessary facts about Le´vy, and deﬁnes the class of noisy clock models used. I. INTRODUCTION The main results on time-changed diffusions and optimal control Effective feedback control often requires accurate timekeeping. are given in Section . The results are proved in Sections with For example, ﬁnite-horizon optimal control problems generally result supplementary arguments given in the appendices. Sections and in policies that are time-varying functions of the state. However, discuss future work and conclusions, respectively. chronometry is imperfect and thus feedback laws are inevitably II. PRELIMINARIES applied at incorrect times. Little appears to be known about the After establishing notation and reviewing Le´vy processes, this consequences of imperfect timing on control [1]–[3]. This paper section culminates in the construction of Le´vy-process-based clock addresses optimal control with temporal uncertainty. models upon which the remainder of the theory of this paper is built. A stochastic process can be time-changed by replacing its time A. Notation index by a monotonically increasing stochastic process [4]. Time- (cid:107) · (cid:107) changed stochastic processes arise in ﬁnance, since changing the time The norm symbol, , is used to denote the Euclidean norm for index to a measure of economically relevant events, such as trades, vectors and the Frobenius norm for matrices. can improve modeling [5]–[7]. This new time index is, however, For a set S, its closure is denoted by S. stochastic with respect to “calendar” time. The spectrum of matrix A is denoted by spec(A). ⊗ We suspect that similar notions of stochastic time changing may The Kronecker product is denoted by , while the Kronecker sum ⊕ facilitate the study of time estimation and movement control in the is denoted by : nervous system. Biological timing is subject to noise and environ- ⊕ ⊗ ⊗ mental perturbation [8]. Furthermore, humans rationally exploit the A B = A I + I B. statistics of their temporal noise during simple timed movements, The vectorization operation of stacking the columns of a matrix is such as button pushing [9] and pointing [10]. To analyze more denoted by vec. complex movements, a theory of feedback control that compensates R × R → R C A function h : n is in 1,2 if h(s, x) is continuously for temporal noise seems desirable. differentiable in s, twice continuously differentiable in x. The func- Within control, the most closely related work to the present paper tion h is sa(cid:12)id to satisf(cid:12)y a(cid:12)polynomi(cid:12)al g(cid:12)rowth cond(cid:12)ition, if in addition, deals with analysis and synthesis of systems with uncertain sampling (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) there are co(cid:12)nstants K(cid:12) an(cid:12)d q such (cid:12)tha(cid:12)t (cid:12) times. The study of uncertain sampling times has a long history (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) in control [11], and is often motivated by problems of clock jitter | | ∂h(s, x) ∂h(s, x) ∂2h(s, x) ≤ (cid:107) (cid:107) h(s, x) , , , K (1 + x q) , [12], [13] or network delays [14]. In these works, control inputs are ∂s ∂x ∂x ∂x i i j sampled at known times and held over unknown intervals. To derive ∈ R ∈ C for i, j = 1, . . . n, and all x n. In this case, h 1,2 is written. the dynamic programming principle in this paper, system behavior p Stochastic processes will be denoted as ζ , X , etc., with time is analyzed for control inputs held over random intervals, bearing t s indices as subscripts. Occasionally, processes with nested subscripts some similarity to optimal control with random sampling [15]. will be written with parentheses, e.g. ζ = ζ(τ ). Similarly, the Fundamentally, however, studies of sampling uncertainty assumes that τs s elements of a stochastic vector will be denoted as X (s). an accurate clock can measure the sample times; the present work 1 Functions that are right-continuous with left-limits will be called relaxes this assumption. ca`dla`g, while functions that are left-continuous with right-limits will Other aspects of imperfect timing have been addressed in control be called ca`gla`d. research to a more limited extent. For example, the importance of B. Background on Le´vy Processes synchronizing clocks in distributed systems seems clear [16], [17], but more work is needed to understand the the implications of Basic notions from Le´vy processes required to deﬁne the general asynchronous clock behavior on common control issues, such as class of clock models are now reviewed. The deﬁnitions and results stability [18] and optimal performance [19]. can be found in [20]. This paper focuses on continuous-time stochastic optimal control A real-valued stochastic process Z is called a Le´vy process if s with perfect state information, but a stochastically time-changed con- • Z = 0 almost surely (a.s.). 0 ≤ ≤ trol process. Dynamic programming principles for general nonlinear • Z has independent, stationary increments: If 0 r s, then s − − Z and Z Z are independent and Z Z has the same Department of Engineering, University of Cambridge, Cambridge, UK r s r s r distribution as Z − . (a.lamperski@eng.cam.ac.uk). s r ≥ Department of Mechanical Engineering, The Johns Hopkins University, • Zs is stPoch| asti−cally|continuous: For all a > 0 and all r 0, Baltimore, MD, USA (ncowan@jhu.edu). lim → ( Z Z > a) = 0. r s s r ##LTLine## ##LTLine## ##LTLine## ##LTLine##

text: Optimal

label: title

text: Control

text: with

text: Noisy

text: Time

text: Andrew

label: author

text: Lamperski

text: Noah

text: J.

text: Cowan

text: Abstract—

text: This

label: abstract

text: paper

text: examines

text: stochastic

text: optimal

text: control

text: problems

text: in

text: stochastic

text: control

text: problems

text: are

text: derived,

text: based

text: on

text: extensions

text: of

text: the

text: which

text: the

text: state

text: is

text: perfectly

text: known,

text: but

text: the

text: controller’s

text: measure

text: of

text: time

text: classical

text: Hamilton-Jacobi-Bellman

text: equation.

text: The

text: results

text: apply

text: to

text: a

text: is

text: a

text: stochastic

text: process

text: derived

text: from

text: a

text: strictly

text: increasing

text: Le´vy

text: process.

text: wide

text: class

text: of

text: stochastic

text: time

text: changes

text: given

text: by

text: strictly

text: increasing

text: We

text: provide

text: dynamic

text: programming

text: results

text: for

text: continuous-time

text: ﬁnite-

text: Le´vy

text: processes.

text: The

text: dynamic

text: programming

text: principles

text: are

text: then

text: spe-

text: horizon

text: control

text: and

text: specialize

text: these

text: results

text: to

text: solve

text: a

text: noisy-time

text: variant

text: of

text: the

text: linear

text: quadratic

text: regulator

text: problem

text: and

text: a

text: portfolio

text: optimization

text: cialized

text: to

text: give

text: explicit

text: solutions

text: to

text: time-changed

text: versions

text: of

text: the

text: problem

text: with

text: random

text: trade

text: activity

text: rates.

text: For

text: the

text: linear

text: quadratic

text: case,

text: ﬁnite-horizon

text: linear

text: quadratic

text: regulator

text: and

text: a

text: portfolio

text: optimization

text: the

text: optimal

text: controller

text: is

text: linear

text: and

text: can

text: be

text: computed

text: from

text: a

text: generalization

text: problem.

text: of

text: the

text: classical

text: Riccati

text: differential

text: equation.

text: Section

text: deﬁnes

text: the

text: notation

text: used

text: in

text: the

text: paper,

text: states

text: the

text: necessary

text: facts

text: about

text: Le´vy,

text: and

text: deﬁnes

text: the

text: class

text: of

text: noisy

text: clock

text: models

text: used.

text: I.

text: INTRODUCTION

text: The

text: main

text: results

text: on

text: time-changed

text: diffusions

text: and

text: optimal

text: control

text: Effective

text: feedback

text: control

text: often

text: requires

text: accurate

text: timekeeping.

text: are

text: given

text: in

text: Section

text: The

text: results

text: are

text: proved

text: in

text: Sections

text: with

text: For

text: example,

text: ﬁnite-horizon

text: optimal

text: control

text: problems

text: generally

text: result

text: supplementary

text: arguments

text: given

text: in

text: the

text: appendices.

text: Sections

text: and

text: in

text: policies

text: that

text: are

text: time-varying

text: functions

text: of

text: the

text: state.

text: However,

text: discuss

text: future

text: work

text: and

text: conclusions,

text: respectively.

text: chronometry

text: is

text: imperfect

text: and

text: thus

text: feedback

text: laws

text: are

text: inevitably

text: II.

text: PRELIMINARIES

text: applied

text: at

text: incorrect

text: times.

text: Little

text: appears

text: to

text: be

text: known

text: about

text: the

text: After

text: establishing

text: notation

text: and

text: reviewing

text: Le´vy

text: processes,

text: this

text: consequences

text: of

text: imperfect

text: timing

text: on

text: control

text: This

text: paper

text: section

text: culminates

text: in

text: the

text: construction

text: of

text: Le´vy-process-based

text: clock

text: addresses

text: optimal

text: control

text: with

text: temporal

text: uncertainty.

text: models

text: upon

text: which

text: the

text: remainder

text: of

text: the

text: theory

text: of

text: this

text: paper

text: is

text: built.

text: A

text: stochastic

text: process

text: can

text: be

text: time-changed

text: by

text: replacing

text: its

text: time

text: A.

text: Notation

text: index

text: by

text: a

text: monotonically

text: increasing

text: stochastic

text: process

text: Time-

text: changed

text: stochastic

text: processes

text: arise

text: in

text: ﬁnance,

text: since

text: changing

text: the

text: time

text: The

text: norm

text: symbol,

text: is

text: used

text: to

text: denote

text: the

text: Euclidean

text: norm

text: for

text: index

text: to

text: a

text: measure

text: of

text: economically

text: relevant

text: events,

text: such

text: as

text: trades,

text: vectors

text: and

text: the

text: Frobenius

text: norm

text: for

text: matrices.

text: can

text: improve

text: modeling

text: This

text: new

text: time

text: index

text: is,

text: however,

text: For

text: a

text: set

text: S,

text: its

text: closure

text: is

text: denoted

text: by

text: S.

text: stochastic

text: with

text: respect

text: to

text: “calendar”

text: time.

text: The

text: spectrum

text: of

text: matrix

text: A

text: is

text: denoted

text: by

text: spec(A).

text: We

text: suspect

text: that

text: similar

text: notions

text: of

text: stochastic

text: time

text: changing

text: may

text: The

text: Kronecker

text: product

text: is

text: denoted

text: by

text: while

text: the

text: Kronecker

text: sum

text: facilitate

text: the

text: study

text: of

text: time

text: estimation

text: and

text: movement

text: control

text: in

text: the

text: is

text: denoted

text: by

text: nervous

text: system.

text: Biological

text: timing

text: is

text: subject

text: to

text: noise

text: and

text: environ-

text: mental

text: perturbation

text: Furthermore,

text: humans

text: rationally

text: exploit

text: the

text: A

text: B

text: A

text: I

text: I

text: B.

text: statistics

text: of

text: their

text: temporal

text: noise

text: during

text: simple

text: timed

text: movements,

text: The

text: vectorization

text: operation

text: of

text: stacking

text: the

text: columns

text: of

text: a

text: matrix

text: is

text: such

text: as

text: button

text: pushing

text: and

text: pointing

text: To

text: analyze

text: more

text: denoted

text: by

text: vec.

text: complex

text: movements,

text: a

text: theory

text: of

text: feedback

text: control

text: that

text: compensates

text: R

text: R

text: R

text: C

text: A

text: function

text: h

text: n

text: is

text: in

text: if

text: h(s,

text: x)

text: is

text: continuously

text: for

text: temporal

text: noise

text: seems

text: desirable.

text: differentiable

text: in

text: s,

text: twice

text: continuously

text: differentiable

text: in

text: x.

text: The

text: func-

text: Within

text: control,

text: the

text: most

text: closely

text: related

text: work

text: to

text: the

text: present

text: paper

text: tion

text: h

text: is

text: to

text: if

text: in

text: addition,

text: deals

text: with

text: analysis

text: and

text: synthesis

text: of

text: systems

text: with

text: uncertain

text: sampling

text: there

text: are

text: q

text: such

text: times.

text: The

text: study

text: of

text: uncertain

text: sampling

text: times

text: has

text: a

text: long

text: history

text: in

text: control

text: and

text: is

text: often

text: motivated

text: by

text: problems

text: of

text: clock

text: jitter

text: ∂h(s,

text: x)

text: ∂h(s,

text: x)

text: x)

text: h(s,

text: x)

text: K

text: x

text: q)

text: or

text: network

text: delays

text: In

text: these

text: works,

text: control

text: inputs

text: are

text: ∂s

text: ∂x

text: ∂x

text: ∂x

text: i

text: i

text: j

text: sampled

text: at

text: known

text: times

text: and

text: held

text: over

text: unknown

text: intervals.

text: To

text: derive

text: R

text: C

text: for

text: i,

text: j

text: n,

text: and

text: all

text: x

text: n.

text: In

text: this

text: case,

text: h

text: is

text: written.

text: the

text: dynamic

text: programming

text: principle

text: in

text: this

text: paper,

text: system

text: behavior

text: p

text: Stochastic

text: processes

text: will

text: be

text: denoted

text: as

text: ζ

text: X

text: etc.,

text: with

text: time

text: is

text: analyzed

text: for

text: control

text: inputs

text: held

text: over

text: random

text: intervals,

text: bearing

text: t

text: s

text: indices

text: as

text: subscripts.

text: Occasionally,

text: processes

text: with

text: nested

text: subscripts

text: some

text: similarity

text: to

text: optimal

text: control

text: with

text: random

text: sampling

text: will

text: be

text: written

text: with

text: parentheses,

text: e.g.

text: ζ

text: ζ(τ

text: Similarly,

text: the

text: Fundamentally,

text: however,

text: studies

text: of

text: sampling

text: uncertainty

text: assumes

text: that

text: τs

text: s

text: elements

text: of

text: a

text: stochastic

text: vector

text: will

text: be

text: denoted

text: as

text: X

text: (s).

text: an

text: accurate

text: clock

text: can

text: measure

text: the

text: sample

text: times;

text: the

text: present

text: work

text: Functions

text: that

text: are

text: right-continuous

text: with

text: left-limits

text: will

text: be

text: called

text: relaxes

text: this

text: assumption.

text: ca`dla`g,

text: while

text: functions

text: that

text: are

text: left-continuous

text: with

text: right-limits

text: will

text: Other

text: aspects

text: of

text: imperfect

text: timing

text: have

text: been

text: addressed

text: in

text: control

text: be

text: called

text: ca`gla`d.

text: research

text: to

text: a

text: more

text: limited

text: extent.

text: For

text: example,

text: the

text: importance

text: of

text: B.

text: Background

text: on

text: Le´vy

text: Processes

text: synchronizing

text: clocks

text: in

text: distributed

text: systems

text: seems

text: clear

text: but

text: more

text: work

text: is

text: needed

text: to

text: understand

text: the

text: the

text: implications

text: of

text: Basic

text: notions

text: from

text: Le´vy

text: processes

text: required

text: to

text: deﬁne

text: the

text: general

text: asynchronous

text: clock

text: behavior

text: on

text: common

text: control

text: issues,

text: such

text: as

text: class

text: of

text: clock

text: models

text: are

text: now

text: reviewed.

text: The

text: deﬁnitions

text: and

text: results

text: stability

text: and

text: optimal

text: performance

text: can

text: be

text: found

text: in

text: This

text: paper

text: focuses

text: on

text: continuous-time

text: stochastic

text: optimal

text: control

text: A

text: real-valued

text: stochastic

text: process

text: Z

text: is

text: called

text: a

text: Le´vy

text: process

text: if

text: s

text: with

text: perfect

text: state

text: information,

text: but

text: a

text: stochastically

text: time-changed

text: con-

text: Z

text: almost

text: surely

text: (a.s.).

text: trol

text: process.

text: Dynamic

text: programming

text: principles

text: for

text: general

text: nonlinear

text: Z

text: has

text: independent,

text: stationary

text: increments:

text: If

text: r

text: s,

text: then

text: s

text: Z

text: and

text: Z

text: Z

text: are

text: independent

text: and

text: Z

text: Z

text: has

text: the

text: same

text: Department

text: of

text: Engineering,

text: University

text: of

text: Cambridge,

text: Cambridge,

text: UK

text: r

text: s

text: r

text: s

text: r

text: distribution

text: as

text: Z

text: (a.lamperski@eng.cam.ac.uk).

text: s

text: r

text: Department

text: of

text: Mechanical

text: Engineering,

text: The

text: Johns

text: Hopkins

text: University,

text: Zs

text: is

text: stPoch|

text: asti−cally|continuous:

text: For

text: all

text: a

text: and

text: all

text: r

text: Baltimore,

text: MD,

text: USA

text: (ncowan@jhu.edu).

text: lim

text: Z

text: Z

text: a)

text: r

text: s

text: s

text: r

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##

text: ##LTLine##