2

Let $(X,d_X), (Y,d_Y)$ be metric spaces. Let $f:X \to Y$. Suppose $f$ satisfies that $$ d_X(p) \leq d_X(p') \implies d_Y(f(p)) \leq d_Y(f(p')) $$ where $p = (x_1,x_2), p'= (x'_1,x'_2), f(p) = (f(x_1),f(x_2))$.

  1. I want to know the name of this property if there is any.
  2. Are there related works?
  3. What would be a non-trivial equivalent characteristics of $f$?

Example: $(\mathbb{R},d)\to (\mathbb{R},d): x \mapsto x^r$ with $r$ odd.

le4m
  • 3,006

1 Answers1

1

Such maps appear under various names:

Other names appear in applied literature, the aforementioned "Local Ordinal Embedding" paper by Terada and Luxburg has a list of references going back to 1960s.

The "Monotone maps" paper by Bilu and Linial is the most mathematical treatment of the subject to my knowledge, although it's classified as theoretical computer science.

I don't think there is any "nontrivial characterization" other than the definition you stated. What's a characterization of homeomorphisms? Being a homeomorphism, of course. Same for bi-Lipschitz maps, etc. The interesting problems are finding obstructions to such embeddings, and constructing embeddings when they exist.

  • Thank you for your great answer. What I really want to do is that I want to constrain solutions of an optimization process to satisfy the above characteristics. Suppose $f$ is to minimize some cost function $C(f)$ while maintaining the above monotonic characteristic. Would there be any optimization trick to achieve that..? I want to know.. – le4m Sep 25 '17 at 10:51
  • We may not be able to find equivalent characteristics but we may find some conditions that imply monotone embedding, can't we? For example, as to functions $f: \mathbb{R} \to \mathbb{R}$, the monotonicity of $f$ implies monotone embedding. How about in $\mathbb{R}^d$ with $d>1$? Can we find such a condition that implies it? – le4m Sep 26 '17 at 03:19