8
$\begingroup$

Suppose there is a compact metric space $(X,\rho)$ and a Euclidean space $\mathbb{R}^n$.

There is a sequence of unequal points $\{x_1,...x_N\}$ in $X$ such that all metrics $\rho(x_i,x_j)$ are known and $f(x_i)=a_i$ for some $a_i$ in $\mathbb{R}^n$ whereas:

$$ \forall x_i,x_j \in \{x_1,...x_N\} . ||a_i-a_j|| \leq L \cdot \rho(x_i, x_j) $$

for a fixed $L$.

Suppose also that $\{x_1,...x_N\}$ form a finite cover of $X$ by balls of some suitable (known) radius.

If $X$ were just a compact interval, $\{x_1,...x_N\}$ its partition, and $n$ were $1$, we could certainly construct a piecewise-linear function $f:X \rightarrow \mathbb{R}^n$ such that:

$$ f(x_i)=a_i \\ \forall x,y \in X . ||f(x)-f(y)|| \leq L \cdot \rho(x, y) $$

with a slope controlled by $L$.

It should be also possible in certain cases if $X \subset \mathbb{R}^m$.

Is it possible to construct such a function for a general compact metric space? And if $X$ is a subset of a Euclidean space?

$\endgroup$
6
$\begingroup$

Applying rescaling you can assume that $L=1$.

We look for a 1-Lipschitz piecewise linear maps $f\colon\mathbb{R}^m\to\mathbb{R}^n$.

If $m=n$ we get $f$ from Brehm's theorem; it says that there is a piecewise distance preserving map of that type (in particular 1-Lipschitz and piecewise linear). See Brehm, U., Extensions of distance reducing mappings to piecewise congruent mappings on $\mathbb{R}^m$ and also our paper written for kids.

If $m<n$ we can think that $\mathbb{R}^m$ is a subspace of $\mathbb{R}^n$; in this case apply Brehm's theorem and restrict the obtained map to $\mathbb{R}^m$.

If $m>n$ we can think that $\mathbb{R}^n$ is a subspace of $\mathbb{R}^m$; in this case apply Brehm's theorem and compose the obtained map with the projection to $\mathbb{R}^n$. Since projection linear and 1-Lipschitz, so it the composition.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @ValerySaharov Rescale $X$ or $\mathbb R^n$:) $\endgroup$ – Anton Petrunin Oct 25 '15 at 18:19
  • $\begingroup$ @ValerySaharov, After first line $L=1$ :) $\endgroup$ – Anton Petrunin Oct 25 '15 at 18:52
  • $\begingroup$ @ValerySaharov We look for a 1-Lipschitz PL-maps $\mathbb{R}^m\to\mathbb{R}^n$. If $m=n$ we get it from Brehm's theorem. If $m<n$ we can think that $\mathbb{R}^m$ is a subspace of $\mathbb{R}^n$; in this case apply Brehm's theorem and restrict the obtained map to $\mathbb{R}^m$. If $m>n$ we can think that $\mathbb{R}^n$ is a subspace of $\mathbb{R}^m$; in this case apply Brehm's theorem and compose the obtained map with the projection to $\mathbb{R}^m$. $\endgroup$ – Anton Petrunin Oct 27 '15 at 11:06
6
$\begingroup$

Anton's answer is for the case where $X$ is a subset of a Hilbert space. For $X$ a general metric space (compactness does not help, BTW), $L$ must be increased by a factor of order $\log^{1/2}N$; see $$$$ Johnson, William B.; Lindenstrauss, Joram Extensions of Lipschitz mappings into a Hilbert space. Conference in modern analysis and probability (New Haven, Conn., 1982), 189–206, Contemp. Math., 26, Amer. Math. Soc., Providence, RI, 1984.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You do not except PL map from general metric space, dont' you? $\endgroup$ – Anton Petrunin Oct 25 '15 at 21:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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