Notes of Yuri Makarychev’s lecture nr 1

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 {X}, {Y} metric spaces, {f:X\rightarrow Y}. Let

\displaystyle  \begin{array}{rcl}  \|f\|_{Lip}=\sup_{x\not= y}\frac{d(f(x),f(y))}{d(x,y)}. \end{array}

Given subset {Z\subset X}, let

\displaystyle  \begin{array}{rcl}  l_Z (X,Y)=\inf\{C\,;\, \forall f:Z\rightarrow Y, \,\exists \textrm{ extension }\hat{f}:X\rightarrow Y \textrm{ with }\|\hat{f}\|_{Lip}\leq C\|f\|_{Lip}.\} \end{array}


\displaystyle  \begin{array}{rcl}  l_k (X,Y)=\sup\{l_Z (X,Y)\,;\, |Z|\leq k\}. \end{array}

Example 1 If {X=[0,1]}, {Y=\{ 0,1 \}}. Then {l_2 (X,Y)=\infty} since identity {Z=\{ 0,1 \}\subset X} to {Y} does not extend continuously to {X}.

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

2. Lipschitz extension rate {1}

2.1. {L_{\infty}}

Theorem 2 (McShane 1934)

\displaystyle  \begin{array}{rcl}  l_k (X,{\mathbb R})=1\quad\textrm{ for all metric spaces }X \textrm{ and all }k. \end{array}

Proof: By induction on {k}. Can assume that {\|f\|_{Lip}=1}. When adding new point {x} to subset {Z}, one needs a number {\lambda\in {\mathbb R}} such that for all {z\in Z},

\displaystyle  \begin{array}{rcl}  f(z)-d(x,z)\leq\lambda\leq f(z)+d(x,z). \end{array}

By assumption,

\displaystyle  \begin{array}{rcl}  \inf_{z\in Z}f(z)+d(x,z) \end{array}


Corollary 3

\displaystyle  \begin{array}{rcl}  l_k (X,L_{\infty})=1\quad\textrm{ for all metric spaces }X \textrm{ and all }k. \end{array}

Indeed, consider each coordinate separately.

2.2. {L_2}

Theorem 4 (Kirszbraun 1934)

\displaystyle  \begin{array}{rcl}  l_k (L_2,L_2)=1\quad\textrm{ for all }k. \end{array}

Proof: By induction on {k}. Can assume that {\|f\|_{Lip}=1}. When adding new point {x} to subset {Z}, one needs a point {v\in L_2} such that for all {z\in Z},

\displaystyle  \begin{array}{rcl}  v\in B(f(z),d(x,z)). \end{array}

For {y\in L_2}, set

\displaystyle  \begin{array}{rcl}  h(y)=\max_{z\in Z}\frac{d(y,f(z))}{d(x,z)}. \end{array}

This function attains its minimum, say at {\hat{y}}. Assume that {h(\hat{y})>1}. Let

\displaystyle  \begin{array}{rcl}  Z'=\{z\in Z\,;\,h(\hat{y})=\frac{d(\hat{y},f(z))}{d(x,z)}\}. \end{array}

Then {\hat{y}} belongs to the convex hull of {h(Z')} (otherwise, we could decrease {h} by replacing {\hat{y}} with its projection on this convex set). Write

\displaystyle  \begin{array}{rcl}  \hat{y}=\sum_{z\in Z'}\mu(z)f(z), \end{array}

where {\mu} is a probability measure on {Z}. For all {z}, {z'\in Z'},

\displaystyle  \begin{array}{rcl}  |f(z)-f(z')|^2 \leq |z-z'|^2 , \end{array}


\displaystyle  \begin{array}{rcl}  2(f(z)-\hat{y})\cdot(f(z')-\hat{y})&=&|f(z)-\hat{y}|^2 +|f(z')-\hat{y}|^2 -|f(z)-f(z')|^2 \\ &\geq& |z-x|^2 +|z'-x|^2 -|z-z'|^2 \\ &=&2(z-x)\cdot (z'-x), \end{array}


\displaystyle  \begin{array}{rcl}  0&\leq&|\sum_{z\in Z'}\mu(z)(z-x)|^2 \\ &=&\sum_{z\in Z'}\mu(z)^2 |z-x|^2 +\sum_{z\not=z'\in Z'}\mu(z)\mu(z')(z-x)\cdot(z'-x)\\ &<&\sum_{z\in Z'}\mu(z)^2 |f(z)-\hat{y}|^2 +\sum_{z\not=z'\in Z'}\mu(z)\mu(z')(f(z)-\hat{y})\cdot(f(z')-\hat{y})\\ &=&|\sum_{z\in Z'}\mu(z)(f(z)-\hat{y})|^2 , \end{array}

contradiction. We conclude that {h(\hat{y})=1}, the balls above intersect and we can find {v} in it and set {f(x)=v}. \Box

Example 2 If {X=\ell_1^3}, {Y=\ell_2^2}, {l_3 (X,Y)\geq \sqrt{3}>1}.

Indeed, map the basis vectors to an equilateral triangle of side {2}. Then the best choice for the image {\hat{y}} of the origin is the center, at distance {\sqrt{3}} of all three vertices.

2.3. Observations

1. If {X'\subset X}, then {l_k (X',Y)\leq l_k (X,Y)}. Since every space can be isometrically embedded in {L_{\infty}}, we get

Definition 5 Say {Y} is a Lipschitz retract of {Y'} if there exists {h:Y'\rightarrow Y} such that {h_{|Y'}=id_{Y'}} and {\|h\|_{Lip}=1}.

2. Clearly, in this case, {l_k (X,Y')\leq l_k (X,Y)} for all {k}.

3. {l_k (X,Y)\leq l_k (L_{\infty},Y)}.

4. {l_k (X,Y)=\sup_{X'\subset X,\,|X'|<\infty} l_k (X',Y)}.

3. Lipschitz extension rates {>1}

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 {\ell_p} spaces.

3.1. {\ell_p} spaces

Theorem 6 (Marcus, Pisier 1984)

\displaystyle  \begin{array}{rcl}  l_k (\ell_p ,\ell_2)\leq C_p (\log k)^{\frac{1}{p}-\frac{1}{2}}\quad \textrm{ for }1<p\leq 2 . \end{array}


Theorem 7 (Johnson, Lindenstrauss 1984)

\displaystyle  \begin{array}{rcl}  l_k (\ell_p ,\ell_2)\geq C'_p (\frac{\log k}{\log\log k})^{\frac{1}{p}-\frac{1}{2}}. \end{array}

3.2. Markov type

Definition 8 Say {X} has Markov type {2} if for all reversible Markov chains {Z_i \in X},

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E} d(Z_0 ,Z_t)^2 \leq C\,t\,\mathop{\mathbb E} d(Z_0 ,Z_1)^2 . \end{array}

The best constant {C} is denoted by {M_2 (X)}.

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

\displaystyle  \begin{array}{rcl}  l_k (X,\ell_q)\leq\frac{6}{\sqrt{q-1}}M_2 (X). \end{array}

Initially, Ball did not know any space of Markov type {2} but {L_2}. He conjectured that {\ell_p} should have this property.

Theorem 10 (Naor, Peres, Schramm, Sheffield 2004) For every {p>2}, {\ell_p} has Markov type {2}, and

\displaystyle  \begin{array}{rcl}  l_k (\ell_p ,\ell_q)\leq 24\sqrt{\frac{p-1}{q-1}}\quad \textrm{ if }1<q\leq 2\leq p>\infty. \end{array}

In all other cases, {l_k (\ell_p ,\ell_q)} tends to infinity as {k} tends to infinity.

Conjecture (Ball 1992): Does {l_k (\ell_2 ,\ell_1)} stay bounded as {k} 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 {X} and {Y},

\displaystyle  \begin{array}{rcl}  l_k (X,Y)\leq C\, \log k . \end{array}

In all other cases, {l_k (\ell_p ,\ell_q)} tends to infinity as {k} tends to infinity.

This was improved later by Lee and Naor.

Theorem 12 (Lee, Naor 2003) 1. For every metric space {X} and every normed space {Y},

\displaystyle  \begin{array}{rcl}  l_k (X,Y)\leq C\, \frac{\log k}{\log\log k} . \end{array}

2. If {X} is the shortest path metric on a graph belonging to the family of graphs with excluded {K_{\eta}}, then for all normed spaces {Y},

\displaystyle  \begin{array}{rcl}  l_k (X,Y)\leq C\, \eta^2 . \end{array}

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

\displaystyle  \begin{array}{rcl}  l_k (X,Y)\leq C\, \log g . \end{array}

4. Connection to the {0}-extension problem

4.1. The problem

Input: a graph {G}, a set {T\subset V} of terminals, {|T|=k}, a metric {d} on {T}, weights on edges.

Task: find {f:V:to T} so as to minimize

\displaystyle  \begin{array}{rcl}  \sum_{\mathrm{edges}\,uv}w_{uv}d(f(u),f(w)), \end{array}

subject to {f(t)=t} for {t\in T}.

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

Known to be NP-hard.

4.2. Results

[Calinescu, Karloff, Rabani] gave an (LP-based) {O(\log k)} approximation.

[Fakcharoenphol, Harrelson, Rao, Talwar 2003] improved it into a (still LP-based) {O(\frac{\log k}{\log\log k})} approximation.

4.3. Relaxation

The LP relaxation amounts to minimizing

\displaystyle  \begin{array}{rcl}  \sum_{\mathrm{edges}\,uv}w_{uv}\rho(u,v), \end{array}

under constraints

\displaystyle  \begin{array}{rcl}  \rho(u,v)+\rho(v,w)\geq \rho(u,w),\quad \rho(u,v)\geq 0,\quad \rho(u,v)=\rho(v,u) \end{array}


\displaystyle  \begin{array}{rcl}  \rho(s,t)=d(s,t) \quad \textrm{ for }s,\,t\in T. \end{array}

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

4.4. Rounding

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

  1. Solve the LP, get metric {\rho}. Denote by {R_x =\rho(x,T)} the distance of vertex {x} to {T} in metric {\rho}.
  2. Choose a random ordering {\pi} of terminals.
  3. Let {M=\log k}. Sample {\alpha} from the distribution with density {\frac{1}{t\log M}}, {t\in[1,M]}.

  4. Map each vertex {x} to the first (in ordering {\pi}) point of {T} in {B_{\rho}(x,\alpha R_x)}.

4.5. Analysis

For every edge {uv}, let {\Delta=\rho(u,v)}. This is the contribution of edge {uv} to the LP value.

1. Assume first that {\Delta\geq\frac{1}{2}\min\{R_u ,R_v\}}. Then

\displaystyle  \begin{array}{rcl}  d(f(u),f(v))\leq \alpha R_u +\Delta +\alpha R_v \leq (5\alpha +1)\Delta, \end{array}

so the contribution of edge {uv} to the objective function is

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E} d(f(u),f(v))\leq 6\mathop{\mathbb E}(\alpha)\Delta\leq 6\frac{\log k}{\log\log k}\Delta. \end{array}

2. Otherwise, {\Delta<\frac{1}{2}\min\{R_u ,R_v\}}. Say that {u} settles {uv} if {f(u)\leq f(v)} in ordering {\pi}. Say that {u} cuts the edge {uv} if {f(u)<f(v)}.


\displaystyle  \begin{array}{rcl}  d(f(u),f(v))\leq \alpha R_u +\Delta +\alpha R_v \leq \alpha R_u +\Delta +\alpha (R_u +\Delta)\leq 3\alpha R_u . \end{array}

Assume that {u} cuts edge {uv}. Then {f(u)=x_i} is the first terminal in {B_{\rho}(u,\alpha R_u)}, {R_u =\rho(u,x_i)}, and {\rho(v,x_i)\geq\alpha R_v}. It follows that

\displaystyle  \begin{array}{rcl}  \rho(u,x_i)+\Delta \geq \alpha (R_u -\Delta),\quad \rho(u,x_i)\leq\alpha R_u . \end{array}

Note that randomness comes from {\pi} for the first inequality, and {\alpha} in the second, so both events are independent. Let {E} be the event that {u} cuts edge {uv}. Then

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}(1_{E} d(f(u),f(v)))\leq\mathop{\mathbb E}(3\alpha R_u 1_{\frac{\rho(u,x_i)}{R_u}\alpha\leq \frac{\rho(u,x_i)+\Delta}{R_u -\Delta}})\mathop{\mathbb P}(...) \end{array}

Continued tomorrow.


About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Course and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s