## 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}$

Let

$\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}$

$\Box$

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}$

so

$\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}$

and

$\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

Conversely,

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\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}$

and

$\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).

Again,

$\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.