19
$\begingroup$

Kirszbraun theorem states that if $U$ is a subset of some Hilbert space $H_1$, and $H_2$ is another Hilbert space, and $f : U \to H_2$ is a Lipschitz-continuous map, then $f$ can be extended to a Lipschitz function on the whole space $H_1$ with the same Lipschitz constant.

Now let's take $H_2$ to be the Euclidean space $\mathbb{R}^n$. My question is: Is there way to explicitly construct this extension? Note that the standard proof (e.g. see Federer's geometric measure theory book or Schwartz's nonlinear functional analysis book) is an existence proof, which uses Hausdorff's maximal principle.

Some remarks:
1) For $n = 1$, the extension can be constructed explicitly, which works even if $H_1$ is only a metric space (with metric $d$): $\tilde{f}(x) = \inf_{y \in U} \{ f(y) + {\rm Lip}(f) d(x,y) \}$. See for example Mattila's book p. 100.

2) For $n > 1$, performing the above extension for each component of $f$ results in blowing up the Lipschitz constant by a factor of $\sqrt{n}$.

$\endgroup$
4
  • $\begingroup$ Offhand I don't know how constructive this is, but are you aware of the paper of Lang-Pavlovic-Schroeder's springerlink.com/content/5pd0u4yr5frrvbyk ? $\endgroup$ May 10, 2011 at 16:11
  • 3
    $\begingroup$ The key step in the proof of Kirszbraun's theorem involves extending the function to one more point. You write down the conditions on an extension which make the extension have the same Lipschitz constant and show that it is possible to satisfy the conditions. It is easy to make the extension explicit. TBC $\endgroup$ May 10, 2011 at 18:29
  • 2
    $\begingroup$ If the space is separable, you can choose a countable dense set of the complement of the domain of the function and recursively define the extension to include that countable dense set and then extend to the whole space by continuity. The entire proof is then explicit once you have the countable dense set and an ordering on it. $\endgroup$ May 10, 2011 at 18:31
  • 2
    $\begingroup$ If the dimension is finite, there is no need to use Hausdorff's maximal principle. Choose a dense countable set in U and extend the map to set of all rational points. The obtained map can be extended to a Lipschitz one on whole space. $\endgroup$ May 10, 2011 at 23:06

4 Answers 4

10
$\begingroup$

I like a recent proof by Akopyan and Tarasov:

A. V. Akopyan, A. S. Tarasov, "A constructive proof of Kirszbraun's theorem"(Russian), Mat. Zametki 84 (2008), no. 5, 781--784; translation in Math. Notes 84 (2008), no. 5-6, 725–728; MR2500644.

I could not find this paper in the open web, but there is a copy behind a paywall: https://dx.doi.org/10.1134/S000143460811014X

What they do: if $U\subset\mathbb R^n$ is a finite set and $f:U\to\mathbb R^n$ is 1-Lipschitz, then they construct a piecewise-linear piecewise-isometric (and hence 1-Lipshitz) extension of $f$ to the whole space. The construction is explicit, but some combinatorics is involved, so I'm not sure how it works for an infinite $U$. (I haven't read the paper but learned the proof from a seminar talk by one of the authors.)

$\endgroup$
3
  • 3
    $\begingroup$ I learned from Akopyan, that the same construction was done earlier (but independently) in Brehm, U., Extensions of distance reducing mappings to piecewise congruent mappings on $R^m$. J. Geom. 16 (1981), no. 2, 187--193 $\endgroup$ May 10, 2011 at 21:54
  • $\begingroup$ Is it known any kind of control on the sides of symplexes of the partition on which these functions are piecewise? I.e. is it possibile to construct a uniformily converging sequencer of pwc function to a 1-Lip function in such a fashion faces do not have their outward normale pointing towards a fixed direction? $\endgroup$
    – user94880
    Jul 9, 2016 at 16:45
  • $\begingroup$ @user94880 I assume you mean to comment on the accepted answer, so I'm moving it there. If you meant to comment on the question, let me know. $\endgroup$
    – Todd Trimble
    Jul 9, 2016 at 18:18
6
$\begingroup$

A recent work Kirszbraun's theorem via an explicit formula by Daniel Azagra, Erwan Le Gruyer, Carlos Mudarra at https://arxiv.org/abs/1810.10288 extends the explicit formula $\tilde f$ given in the question for N=1 to any Hilbert spaces.

$\endgroup$
4
$\begingroup$

If I remember well the Kirszbraun's extension of a $L$-Lipschitz map $f:U\subset H_1\to H_2$ has the following canonical construction, analogous to the one-dimensional case you mentioned (so in a sense it is explicit).

Let $\mathcal{Co} (H_2)$ denote the metric space of all non-empty bounded closed convex sets of $H_2$ endowed with the Hausdorff distance. Let $f_*:H_1\to \mathcal{Co}(H_2)$ be defined by $$f_*(x):=\cap_{u\in U}\overline{B}(f(u),L\|x-u\|)$$

(In other words, $f_*$ takes $x\in H_1$ to the set of the admissible values at $x$ for any $L$-Lipschitz extension of $f$ to $U\cup\{x\}$). This map $f_*$ has the same Lipschitz constant of $f$, w.r.to the Hausdorff distance on $\mathcal{Co}(H_2)$.

Any non-empty bounded closed convex $C$ of a Hilbert space $H$ has a well-defined point $\kappa( C), $ the center of the closed ball of minimum radius containing $C$; this point is unique, and the corresponding map $\kappa: \mathcal{Co}(H)\to H $ is $1$-Lipschitz. (Warning - here there is an issue; it seems this is not the right selection map; see Junekey Jeon‘s comment below)

One can therefore define a canonical $L$-Lipschitz extension of $f$ as $\tilde f:=\kappa \circ f_*$. In case $n=1$, the set $f_*(x)$ is just an interval, its end-points are the inf-convolution you mentioned, and the sup-convolution, and this $\tilde f$ is their arithmetic mean.

$\endgroup$
3
  • 1
    $\begingroup$ Is $\kappa$ really $1$-Lipschitz? Could you provide a reference? Because this paper (core.ac.uk/download/pdf/81127315.pdf, Theorem 2) seems to show the opposite. $\endgroup$ Feb 2, 2021 at 4:17
  • $\begingroup$ Should'nt $f_*(x)$ be the intersection of all balls $\overline B(f(u),L\|x-u\|)$? The main point is then to show that $f_*(x)$ is not empty. $\endgroup$ Mar 2, 2023 at 16:25
  • 1
    $\begingroup$ Yes, and the intersection is not empty because it is a family of (weakly) compact sets with non-empty finite intersection. A finite intersection being not empty is equivalent to the theorem in the case of finite sets U. $\endgroup$ Mar 2, 2023 at 18:12
1
$\begingroup$

See also an efficient algorithm for constructing the Kirszbraun extension, here: https://arxiv.org/abs/1905.11930

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.