Deza M.M., Laurent M. Geometry of Cuts and Metrics

7.6

The

I-Sum

Operation

103

Cx

2

1

and

L b(Xl,X2)b(YI,Y2)d

l

ed

2

«Xl,X2),(Yl,Y2»

=

Xl,Y1EXl

X2.Y2

EX

2

L

aXlaYldl(XbYl)+

L C

X2

Cy2

d2

(X2,Y2):S0.

Xl,YlEXI

X2,Y2EX2

I

Proposition

7.5.3.

(i)

If

Pl E

COR(Xd

and

P2

E

COR(X

2

), then

PI ®

P2

E

COR(XI

X X2).

(ii)

If

PI E

COR(X)

and

P2

E

COR(X),

then PI 0

P2

E

COR(X).

(Here,

PI

0

P2

stands

for

the

componentwise product.)

Proof.

The

proof

of

(i) is based on

the

following observation:

PI

L aS7r(S)

and

P2

= L

/3T7r(T)

=>

PI

®P2

S<;;Xl

T<;;X2

Assertion (ii) follows from

the

fact

that

7r(S)

o7r(T)

S,T

of

X.

7.6

The

1-Sum

Operation

as/1T7r(SxT).

7r(S

n

T)

for all subsets

I

Let

d

1

be

a

distance

on

Xl,

d

2

be

a distance

on

X

2

and

suppose

that

Ix

l

nx

2

1 = 1,

n X

2

{xo}.

The

I-sum

of

d

l

and

d

2

is

the

distance d on

Xl

U defined

by

{

d(x,y)

=

dl(x,y)

d(x,y)

=d

2

(x,y)

d(x, y) d(x, xo) + d(xo, y)

Proposition

7.6.1.

if

x,y

E

Xl,

if

X,y

E X

2

,

ifxEX

1

,y

EX

2.

0)

Let d

be

the

I-sum

of

d

l

and d

2

•

Then, d is

1'1

-embeddable (resp. £l-rigid,

hypercube embeddable, h-rigid)

if

and only

if

d

1

and d

2

are

£l-embeddablc

(resp.

£1

-rigid, hypercube embeddable, h-rigid).

(ii) d is hypermetric (resp.

of

negative type)

if

and only

if

d

1

and d

2

are

hypermetric (resp.

of

negative type).

Proof.

The

proof

of

(i) is based on

the

following two observations:

•

If

dl = Es<;;x

,

\{XO}

as8(S)

and

d2 =

ET<;;X

2

\{xo}

/3T8(T),

then

d

L as8(S) + L /3T8(T).

S<;;Xl\{XO}

T<;;X2\{XO}

104

Chapter

7.

Operations

•

If

d =

LAEA

AAO(A)

with

AA

> 0 for A E A,

where

A is a collection

of

nonempty

subsets

of

Xl

U X

2

\ {xu},

then

A

~

Xl

or

A

~

X

2

for

each

A E A.

This

follows from

the

fact

that

d satisfies

the

triangle

equalities:

d(XI,

X2)

= d(XI, xo) + d(xo,

X2)

for

all

Xl

E

Xl,

X2

E X

2

.

Hence,

di

=

LAEAIA<;X;

AAO(A) for i = 1,2.

We

prove (ii)

in

the

hypermetric

case

(the

negative

type

case is

similar).

The

space

(Xl,

d

l

)

is a

subspace

of

(Xl

U X

2

,

d)

and,

hence,

it

is

hypermetric

when-

ever

(Xl

U X

2

,

d)

is

hypermetric.

Suppose

now

that

(Xl,

d

l

)

and

(X

2

, d

2

)

are

hypermetric.

Let

bE

Z

X

1U

X

2

with

LXEX

1

U

X

2 b

x

= 1. Define a E

ZX1,

C E ZX2

by

setting

ax

:=

b

x

for X E

Xl

\ {xo}, a

xo

:=

LXEX2 b

x

,

C

x

:=

b

x

for X E X

2

\ {xo},

and

c

xo

:=

LXEX

1

b

x

.

Then,

This

shows

that

(Xl

U X

2

,

d)

is

hypermetric.

I

For

path

metrics

of

graphs,

the

I-sum

operation

corresponds

to

the

clique

I-sum

operation

for

graphs.

Namely,

if

G

I

and

G

2

are

two

connected

graphs

and

if

G

denotes

their

clique

I-sum

(obtained

by

identifying a

node

in

G

I

with

a

node

in

G2

and

denoting

it

as

xo),

then

the

path

metric

of

G coincides

with

the

I-sum

of

the

path

metrics

of

G

I

and

G

2

•

M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,

DOI 10.1007/978-3-642-04295-9_8, © Springer-Verlag Berlin Heidelberg 2010

Chapter

8.

L1-Metrics

from

Lattices,

Semigroups

and

Normed

Spaces

We

present

in

this

chapter

several classes

of

distance

spaces for

which

L

1

-

embeddability

can

be

fully

characterized

using

only

hypermetric

or

negative

type

inequalities.

These

distance

spaces arise from

poset

lattices,

semigroups

and

normed

vector

spaces. Several

of

the

results

mentioned

here

are

given

with

a

sketch

of

proof

only

or,

at

times,

with

no

proof

at

all.

They

indeed

rely

on

analytical

methods

whose

exposition

is

beyond

the

scope

of

this

book. We do,

however,

provide

references

that

the

interested

reader

may

consult

for

further

information.

8.1

L1-Metrics

from

Lattices

In

this

section,

we

consider

a class

of

metric

spaces arising from (poset)

lattices

1

.

We

start

with

recalling

some

definitions. A poset (partially ordered set) consists

of

a

set

L

equipped

with

a

binary

relation

~

satisfying

the

conditions: x

~

x,

x

~

y

and

y

~

x

imply

that

x = y, x

~

y

and

y

~

z

imply

that

x

~

z,

for

x,

y,

z E

L.

The

meet

x 1\ y (if

it

exists)

of

two

elements

x

and

y is

the

(unique)

element

satisfying

x 1\ y

~

x,

y

and

z

~

x 1\ y

if

z

~

x,

y;

similarly,

the

join

x

Vy

(if

it

exists)

is

the

(unique)

element

such

that

x,

y

~

x

Vy

and

x

Vy

~

z

if

x,

y

~

z.

Then,

the

poset

(L,~)

is

said

to

be

a lattice

if

every two

elements

x,

y E L have

a

join

x V y

and

a

meet

x 1\ y.

Given

a

lattice

L,

a

function

v : L

--+

114

satisfying

(8.1.1 )

v(x

Vy)

+

v(x

1\ y) =

v(x)

+

v(y)

for all

X,y

E

L.

is

called

a valuation

on

L.

The

valuation

v is

said

to

be

isotone

if

v(x)

:::;

v(y)

whenever

x

~

y

and

positive

if

v(x)

<

v(y)

whenever x

~

y, x

1=

y. Set

(8.1.2)

dv(x,

y)

:=

v(x

V y) -

v(x

1\

y)

for all

x,

y E

L.

One

can

easily check

that

(L,

d

v

)

is a

semimetric

space

if v is

an

isotone

valuation

on

L

and

that

(L,

d

v

)

is a

metric

space

if

v is a positive

valuation

on

L;

in

the

latter

case, L is called a

metric

lattice (see Birkhoff [1967]). Clearly, every

metric

IThe

word

"lattice"

is

used

here

in

the

context

of

partially

ordered

sets.

Another

notion

of

lattice,

referring

to

discrete

subgroups

of

1IR",

will

be

considered

in

Part

II. A

good

reference

on

poset

lattices

is

the

textbook

by

Birkhoff [1967].

106

Chapter

8. LI-Metrics from Lattices, Semigroups

and

Normed

Spaces

lattice

is modular, i.e., satisfies

x

1\

(y

V z) = (x

1\

y)

V z

for all

x,

y,

z

with

z

~

x.

A lattice

is

said

to

be distributive

if

x

1\

(y V

z)

=

(x

1\

y) V

(x

1\

z)

for all

x,

y, z.

The

following result

of

Kelly [1970a] gives a

characterization

of

the

Ll-embeddable

metric lattices. Another characterization

in

terms

ofthe

negative

type

condition

will

be

given

in

Example

8.2.6.

Theorem

8.1.3.

Let

L

be

a lattice, let v

be

a positive valuation

on

L,

and

let d

v

be

the distance

on

L defined by (8.1.2). The following assertions are equivalent.

(i) L is a distributive lattice.

(ii)

(L,

d

v

) is 5-gonal.

(iii)

(L,

d

v

) is hypermetric.

(iv)

(L,d

v

)

is Ll-embeddable.

Proof.

It

suffices

to

show

the

implications (ii) '* (i)

and

(i) '* (iv).

(ii)

'* (i) Using

the

definition

of

the

valuation v

and

applying

the

pentagonal

inequality (6.1.9)

to

the

points

Xl

:=

x Vy, x2

:=

x

1\

y, x3

:=

z,

Yl

:=

x,

Y2

:=

y,

we

obtain

the

inequality:

2(

v(xVyV

z

)-v(xl\yl\z))

~

v(xVy)+v(xV

z)+v(yV

z)-v(xl\y)-v(xl\z

)-v(yl\z).

By applying again

the

pentagonal inequality

to

the

points

Xl

:=

x,

X2

:=

y,

x3

:=

z,

YI

:=

x V

y,

Y2

:=

x

1\

y,

we

obtain

the

reverse inequality. Therefore,

equality holds

in

the

above inequality.

In

fact,

this

condition

of

equality is

equivalent

to

L being

distributive

(see Birkhoff [1967]).

(i)

'* (iv)

Let

Lo

be

a finite subset

of

L;

we

show

that

(Lo, d

v

) is

Ll-embeddable.

Let

K

be

the

sublattice

of

L generated by Lo. Suppose K

has

length

n.

Then,

K is isomorphic to a family N

of

subsets

of

a set X

of

cardinality

IXI

= n

with

the

property

that

N is closed

under

taking

unions

and

intersections (see Birkhoff

[1967]

p. 58).

Via

this

isomorphism,

we

have a valuation defined

on

N,

again

denoted

by

v.

We

can

assume

without

loss

of

generality

that

v(0) =

O.

Then,

v

can

be

extended

to

a valuation

v*

on 2

x

satisfying

v*(S)

=

LV*({x})

for

xES

S

~

X.

Now,

if

x

f----+

Sx is

the

isomorphism from K

to

N,

then

we

have

the

embedding

x

f----+

Sx

from

(Lo,d

v

)

to

(2X,v*)

which

is

isometric. Indeed,

dv(x,

y)

=

v(x

V

y)

-

v(x

1\

y)

=

v(Sx

U Sy) -

v(Sx

n

Sy)

=

v*(Sx

U Sy) -

v*(Sx

n

Sy)

=

v*(Sx!:'Sy).

This

shows

that

every finite subset

of

(L, d

v

)

is

Ll-embeddable.

Therefore,

by

Theorem

3.2.1,

(L,d

v

)

is

Ll-embeddable.

I

8.2

Ll-Metrics

from Semigroups

107

Example

8.1.4.

(Assouad, [1979]) Let (W,::5) denote

the

lattice consisting

of

the

set W of positive integers

with

order relation x

::5

y if x divides y.

Then,

for

x,

yEW,

x A Y is

the

g.c.d. (greatest common divisor) of x

and

y

and

x V y is

their

I.c.m. (lowest common multiple). One checks easily

that

(N°,

::5)

is a

distributive

lattice. Therefore, (W, d

v

)

is

Ll-embeddable

for every positive

valuation

v on

W.

For instance,

x E W

t--+

v(x)

:=

logx

is a positive valuation on

W.

Hence,

the

metric d

v

,

defined by

d

( )

-1

(I.c.m.(x,y))

v

x,y

- og

g.c.d.(x,

y)

for all integers

x,

y

2:

1,

is Ll-embeddable.

I

8.2

L

1

-Metrics

from

Semigroups

We consider now some distance spaces arising in

the

context of semigroups.

We recall

that

a

commutative

semigroup

(S,

+)

consists of a set S

equipped

with

a composition rule

"+"

which

is

commutative

and

associative.

We

assume

the

existence

of

a

neutral

element denoted by

O.

Let

(S,

+)

be a

commutative

semigroup

and

let v : S

---+

Il4 be a

mapping

such

that

v(O)

=

O.

We define a

symmetric

function

2

Dv on S by setting

(8.2.1)

Dv(x,y):=

2v(x

+ y) - v(2x) - v(2y) for all

x,y

E S.

Theorem

8.2.5 below gives some conditions on

Sand

Dv sufficient for ensuring

that

the

distance space

(S,D

v

)

be Ll-embeddable.

It

is essentially based on

a result by Berg, Christensen and Ressel

[1976] concerning a certain class of

functions of positive

type

on

S.

More precisely, given v : S

---+

114,

let

Pv

denote

the

symmetric

function on

S2

defined by

(8.2.2)

Pv(x,y):=

v(x)

+

v(y)

-

v(x

+ y) for all

x,y

E S.

Define N as

the

set of functions v : S

---+

Il4

with

v(O)

= 0

and

for which

Pv

is

of

positive

type

on S

(that

is,

the

matrix

(Pv(Xi,Xj))f,j=l

is

positive semidefinite

for all Xl,

...

,x

n

E S, n

2:

2).

The

members

of

N are completely described in

Theorem

8.2.3 below,

that

we

state

without proof;

this

result was proved by Berg,

Christensen

and

Ressel [1976]. A character on S

is

a mapping p : S

---+

[-1,1]

satisfying p(x + y) = p(x)p(y) for all

x,

YES,

and

p(O)

=

1.

Denote by i

the

unit

character,

taking

value 1 for every element

XES,

and

let S denote

the

set

of

characters on

S.

2

At

this

point,

Dv

is

not

necessarily

a

distance,

as

it

may

take

negative

values.

However,

Dv

is

nonnegative

if

we

assume,

e.g.,

that

Dv

is

of

negative

type.

108

Chapter

8. L1-Metrics from Lattices, Semigroups

and

Normed

Spaces

Theorem

8.2.3.

Let

v E

N.

Then,

there

exist

(i) a

function

h : S

---t

ll4

satisfying

h(x

+

y)

=

h(x)

+

h(y)

for

all

x,

YES,

and

(ii) a

nonnegative

Radon

measure

jL

on

S \ {i}

satisfying

( .

(1

- p(x))jL(dp) <

00

for

all

XES,

such

}

S-{l}

that

(8.2.4)

v(x)

=

h(x)

+ ( .

(1

- p(x))jL(dp)

for

all

xES.

}S-{l}

I

This

allows us

to

derive conditions for

the

distance space

(S,D

v

)

to be L

1

-

embeddable,

as was observed by Assouad [1979, 1980b].

Theorem

8.2.5.

Let

(S,

+)

be

a

commutative

semigroup

with

neutral

element

0,

let

v : S

f---->

ll4

be

a

mapping

such

that

v(O) = 0,

and

let

Dv

be

defined by

(8.2.1).

Assume

that

one

of

the

following

assertions

(i)

or

(ii) holds.

(i)

(S,

+)

is a group.

(ii)

For

each

XES,

there exists

an

integer

n

::::

1

such

that

2nx

=

x.

Then,

(S,

Dv)

is

L1-embeddable

if

and

only

if

(S,

Dv)

is

of

negative type.

Proof.

Suppose

that

(S,

Dv)

is

of

negative type. Let

Pv

: S2

---t

~

denote

the

symmetric

function

obtained

by applying

the

covariance

transformation

~

(pointed

at

0)

to

Dv.

Then,

1

Pv(x,

y)

=

Z(Dv(x,

0)

+

Dv(Y,

0)

-

Dv(x,

y))

=

v(x)

+

v(y)

-

v(x

+ y)

for

x,

yES.

In

other

words,

Pv

coincides

with

the

function defined

in

(8.2.2).

By

assumption,

(S,

Dv)

is

of

negative

type

or, equivalently (by

Lemma

6.1.14),

Pv

is

of

positive type.

That

is,

the

function v belongs to

the

set

N.

Applying

Theorem

8.2.3,

we

can

suppose

that

v is of

the

form (8.2.4).

In

case (i),

(S,

+)

is a

group

and,

thus,

every

character

on

S takes only values

±1.

Setting

Ax:=

{p

E S I

p(x)

=

-I}

for

xES,

we

obtain

that

Pv(x,

y)

=

4jL(AxnAy)

for all

x,

yES.

In

case (ii), every

character

on

S takes only values

0,

1.

Setting

Ax

:=

{p

E S I

p(x)

=

O}

for

XES,

we

obtain

that

Pv(x,

y)

= jL(Ax

nAy)

for all

x,

yES.

Therefore,

Pv

is

a

{O,

1}-

covariance

in

both

cases (i)

and

(ii).

This

shows (by

Lemma

5.3.2)

that

(S,

Dv)

is L

1

-embeddable. I

Example

8.2.6.

Let (L,

:j)

be

a

lattice

and

let S

be

a

subset

of

L which is

stable

under

the

join

operation

V

of

L

and

contains

the

least element °

of

L.

Then,

8.3 L1-Metrics from Normed Spaces

109

(8,

v)

is a

commutative

semigroup satisfying

Theorem

8.2.5 (ii). Therefore, given

a

mapping

v:

8

~

lilt such

that

v(O)

= 0,

(8,

Dv) is

Ll-embeddable

{=::}

(8, Dv) is of negative type,

where

Dv(x, y) = 2v(x V y) - vex) - v(y) for x, y E 8.

We formulate

in

Corollary 8.2.7

the

result obtained in the special case when v is

a valuation

on

L.

I

Corollary

8.2.7.

Let L

be

a lattice, let v : L

m.+

be

a valuation

on

L (that

is, v satisfies

(8.1.1)) and let d

v

be

defined

by

(8.1.2). Then,

(L, d

v

)

is L1-embeddable

{=::}

(L, d

v

) is

of

negative type.

Proof. Observe

that,

since v satisfies (8.1.1), the two distances d

v

and

Dv

coin-

cide, where

d

v

is defined

by

(8.1.2)

and

Dv

by

(8.2.1). Hence, the result follows

by applying

Theorem

8.2.5 to the semigroup (L,

v)

(condition (ii) applies as

xVx=xforallxEL).

I

Another

example

of

application of

Theorem

8.2.5 is

obtained

by

taking

as

semigroup a set family closed under the symmetric difference.

Corollary

8.2.8.

Let A

be

a family

of

subsets

of

a set n which is

clo.~ed

under

the

symmetric

difference (that is,

A6B

E A for all

A,

B E

A).

Let

v : A

~

lilt

be

a mapping such that v(0) = 0, and let

du,/::'

be

the distance

on

A defined by

(8.2.9)

dv,/::,(A,

B)

v(A6B)

for

all

A,

B E A.

Then,

CA,

d

u

,/::,)

is

L1

-embeddable

{=::}

CA,

d

u

,/::,)

is

of

negative type.

Proof. Observe

that

d

v

,/::,

group

(A,

.6.).

and

apply

Theorem

8.2.5

to

the

commutative

I

The

distance spaces

of

the form

(A,

d

u

,/::,)

are

of

particular

interest.

They

are

indeed very closely related

to

the

measure semimetric spaces (defined

in

Sec-

tion

3.2), which

playa

central role

in

the theory of L1-metrics.

We

will

apply

Corollary 8.2.8

in

the next

chapter

for finding metric transforms preserving L

1

-

embeddabilitYi see

Theorem

9.0.3

and

its proof.

8.3

L1-Metrics

from

Normed

Spaces

Let

(E,

II

.

II)

be

a normed space.

We

consider

the

associated metric space

(E,dll.

II

)'

where

dll.11

is the

norm

metric defined by

dll.lI(x,y) x y

II

110

Chapter

8.

L

1

-Metrics from Lattices, Semigroups

and

Normed Spaces

for all

x,

y E

E.

In

this

section,

we

mention without proof several results char-

acterizing

the

norms on E

]Rm

for which

the

metric space

(]Rffi,

dll.ll)

is L

1

-

embeddable.

We first recall some definitions.

If

II

.

II

is a norm on

]RTn,

its

unit

ball B is

defined as

B {xE]Rm:llxll::5:1}

and

BO

denotes the

polar

of

B.

A polytope is called a zonotope if

it

is

the

vector

sum

of some line segments.

(Hence, parallelotopes,

that

were mentioned in Theorem 6.3.7, are special in-

stances

of

zonotopes.) A zonoid is a convex body

that

can be approximated by

zonotopes with respect to

the

Blaschke-Hausdorff metric. Zonotopes

and

zonoids

are central objects in convex geometry

and

they are also relevant to many

other

fields, in particular, to

the

topic

of

L

1

-metrics as

the

results below show.

\Ve

refer to Bolker

[1969]

and

Schneider

and

Weil

[1983]

for detailed exposition on

zonoids.

We

now

present several equivalent characterizations

3

for the L

1

-embeddable

normed metric spaces

(]Rm,

dll.ll)'

Theorem

8.3.1.

Let

II

.

II

be

a

norm

on]RTn

and let B

be

its

unit

ball. The

jollowing assertions are equivalent.

(i)

dll.ll

is

oj

negative type.

(ii)

dll.ll

is hypermetric.

(iii)

(]Rm,

dll.ll)

is

Ll

-embeddable.

(iv)

The

polar

oj

B is a zonoid.

I

Precise reference for the equivalence

(i)

{=:::>

(ii)

{=:::>

(iv) from Theorem 8.3.1

can

be found in Schneider and Weil

[1983]

and (iii)

{=:::>

(iv) is proved in Bolker

[1969].

L

1

-embeddability

of

norm metrics can be characterized by much simpler

inequalities when

the

unit

ball of

the

normed space

is

a polytope;

we

refer to

Assouad [1980a,

1984]

and

Witsenhausen

[1978]

for the next result.

Theorem

8.3.2.

Let

II

.

II

be

a

norm

on

]Rm

jor

which the

unit

ball B is a

polytope. The

jol101/Jing

assertions are equivalent.

(i)

II.

II

satisfies Hlawka's inequality:

II

x

II

+

II

y

II

+

II

z

II

+

II

x + y + z

11:2:

II

x + y

II

+

II

x + z

II

+

II

y + z

II

jor

all

x,y,z

E

]Rm.

generally,

it

is shown in Bretagnolle,

Dacunha

Castelle

and

Krivine

[1966J

that,

for

1

S;

P S;

2,

a

norm

metric

dll.1I

is Lp-embeddable if

and

only if

its

p-th

power (dl!.II)P is of

negative

type.

8.3 LI-Metrics from Normed Spaces

(ii)

II

.

II

satisfies the 7 -gonal inequality:

L

II

Xi

Xj

II

+ L

II

Yh

Ylc

for

all

Xl,

X2, X3,

X4,YI,

Y2,

Y3

E

Rm.

(iii) (Rm, dll.ll) is

L1

-embeddable.

(iv) The polar

of

B is a zonotope.

111

II

Xi

Ylc

II

I

In

fact,

the

implication (ii) (i) of Theorem 8.3.2 remains valid for general

norms. Namely, if an

arbitrary

norm on R

m

satisfies the 7-gonal inequality,

then

it

also satisfies Hlawka's inequality (Assouad [1984]).

The

above results can be partially extended to

the

more general concept

of

projective metrics. A continuous metric d on R

m

is called a projective

metric

if

it

satisfies

d(x,z)

d(x,y)+d(y,z)

for any collinear points

X,

Y,

z lying in

that

order on a common line. Clearly, every

norm

metric is projective.

The

cone

of

projective metrics is

the

object considered

by Hilbert's fourth problem

(d.

Alexander

[1988],

Ambartzumian

[1982];

Deza M.M., Laurent M. Geometry of Cuts and Metrics

Подождите немного. Документ загружается.