The setup. Let's say that we have a set of objects $O_i$ for which we have a dissimilarity measure $M(O_1,O_2)$. With this we can build a distance matrix $D_{ij}$.

Let's also assume that we have NO any reasonable or natural a priory way to assign the objects to vectors in any vector space, the point is to build one.

Goal: assign ${O_i}$ to vectors in a Euclidian vector space with small amount of dimensions so that the distance matrix $E_{ij}$ build with Euclidian norm for the assigned vectors was the best possible fit for $D_{ij}$

The desired number of dimension for E is no more than 5. The expected number of objects is measured in thousands, maybe millions.

Questions: Is this problem studied in some field ? If yes, which field, how is the problem named and what should I learn to write a code solving the problem? If no, what would be the most relevant fields ?


Yes, this is studied, for example under the name multidimensional scaling. Basically, one eigenvalue decomposition of a suitable matrix (that depends on the distances) shows if the data can be realized distances between some points at all and also which dimension is needed to do so.

You may have a look at Euclidean Distance Matrices: Essential Theory, Algorithms and Applications by Ivan Dokmanic, Reza Parhizkar, Juri Ranieri, Martin Vetterli which gives more algortihms and applications.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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