Find a bijection that best preserves distances

Question

I have two spaces (not necessarily equal in dimension) with N points. I am trying to find a bijection (pairing) of the points, such that the distances are preserved as well as possible.

I can't seem to find a discussion of possible solutions or algorithms to this question online. Can anyone suggest keywords that I could search for? Does this problem have a name, or does it come up in any domain?

Answer 1

I believe you are looking for a Multidimensional Scaling algorithm where you are minimizing the total change in distance. Unfortunately, I have very little experience in this area and can't be of much more help.

Answer 2

I haven't heard of the exact same problem. There are two similar types of problems:

1. Non-linear dimensionality reduction, you're given N high dimensional points and you want to find N low dimensional points that preserve distance as well as possible. MDS, mentioned by Michael Koval is one such method.
2. This might be more promising: algorithms for the assignment problem. For example Kuhn-Munkres (the Hungarian algorithm), you're given an NxN matrix that encodes the cost of matching pi with pj and you want to find the minimum cost bijection. There are many generalizations of this problem, for example b-matching (Kuhn-Munkres solves 1-matching).

Depending on how you define "preserves distances as well as possible" I think you either want (2) or a generalization of (2) in such a way that the cost doesn't only depend on the two points being matched but the assignment of all other points.

Finally, Kuhn-Munkres comes up everywhere in operations research.