**Lipschitz extendability**

Classical subject in mathematics, started having applications to computer science in the 1990’s.

**1. Lipschitz extension rates **

** 1.1. Definition **

Definition 1, metric spaces, . LetGiven subset , let

Let

Example 1If , . Then since identity to does not extend continuously to .

Therefore, to avoid topological obstructions, one should assume that is contractible. In the sequel, we shall assume that is a Banach space.

**2. Lipschitz extension rate **

** 2.1. **

Theorem 2 (McShane 1934)

*Proof:* By induction on . Can assume that . When adding new point to subset , one needs a number such that for all ,

By assumption,

Corollary 3

Indeed, consider each coordinate separately.

** 2.2. **

Theorem 4 (Kirszbraun 1934)

*Proof:* By induction on . Can assume that . When adding new point to subset , one needs a point such that for all ,

For , set

This function attains its minimum, say at . Assume that . Let

Then belongs to the convex hull of (otherwise, we could decrease by replacing with its projection on this convex set). Write

where is a probability measure on . For all , ,

so

and

contradiction. We conclude that , the balls above intersect and we can find in it and set .

Example 2If , , .

Indeed, map the basis vectors to an equilateral triangle of side . Then the best choice for the image of the origin is the center, at distance of all three vertices.

** 2.3. Observations **

1. If , then . Since every space can be isometrically embedded in , we get

Definition 5Say is a Lipschitz retract of if there exists such that and .

2. Clearly, in this case, for all .

3. .

4. .

**3. Lipschitz extension rates **

One cannot rely on the point by point extension method any more. There were no results for many years, until Marcus and Pisier could handle spaces.

** 3.1. spaces **

Theorem 6 (Marcus, Pisier 1984)

Conversely,

Theorem 7 (Johnson, Lindenstrauss 1984)

** 3.2. Markov type **

Definition 8Say has Markov type if for all reversible Markov chains ,

The best constant is denoted by .

Theorem 9 (Ball 1992)If is a metric space of Markov type , then

Initially, Ball did not know any space of Markov type but . He conjectured that should have this property.

Theorem 10 (Naor, Peres, Schramm, Sheffield 2004)For every , has Markov type , and

In all other cases, tends to infinity as tends to infinity.

**Conjecture (Ball 1992)**: Does stay bounded as tends to infinity ?

We shall see tomorrow applications of this conjecture to computer science.

** 3.3. Results for general (Banach) range spaces **

Theorem 11 (Johnson, Lindenstrauss, Schetchtman 1996)For every metric spaces and ,

In all other cases, tends to infinity as tends to infinity.

This was improved later by Lee and Naor.

Theorem 12 (Lee, Naor 2003)1. For every metric space and every normed space ,2. If is the shortest path metric on a graph belonging to the family of graphs with excluded , then for all normed spaces ,

Theorem 13 (Lee, Sidiropoulos 2010)Let be a Riemannian surface of genus , then for every normed space ,

**4. Connection to the -extension problem **

** 4.1. The problem **

Input: a graph , a set of terminals, , a metric on , weights on edges.

Task: find so as to minimize

subject to for .

Motivation: Want to partition into clusters around terminals. Used in pattern recognition.

Known to be NP-hard.

** 4.2. Results **

**[Calinescu, Karloff, Rabani]** gave an (LP-based) approximation.

**[Fakcharoenphol, Harrelson, Rao, Talwar 2003]** improved it into a (still LP-based) approximation.

** 4.3. Relaxation **

The LP relaxation amounts to minimizing

under constraints

and

Its value is clearly less than the optimum of the -extension problem.

** 4.4. Rounding **

The [Fakcharoenphol, Harrelson, Rao, Talwar 2003] rounding procedure goes as follows.

- Solve the LP, get metric . Denote by the distance of vertex to in metric .
- Choose a random ordering of terminals.
- Let . Sample from the distribution with density , .
- Map each vertex to the first (in ordering ) point of in .

** 4.5. Analysis **

For every edge , let . This is the contribution of edge to the LP value.

1. Assume first that . Then

so the contribution of edge to the objective function is

2. Otherwise, . Say that settles if in ordering . Say that cuts the edge if .

Again,

Assume that cuts edge . Then is the first terminal in , , and . It follows that

Note that randomness comes from for the first inequality, and in the second, so both events are independent. Let be the event that cuts edge . Then

Continued tomorrow.