I have a set of entities $\mathcal{E} = \{e_i \mid i \in [1,n]\}$, and I have a proper distance metric defined over $\mathcal{E}\times\mathcal{E}$, call it $d$, so the distance between $e_i$ and $e_j$ is $d(e_i, e_j)$.

I'd like to find some vectors $x_1, \dots, x_n$ s.t. $\mid\mid\! x_i - x_j \!\mid\mid = d(e_i, e_j)$.

Unfortunately, the system of equations constraining the $x_i$ is not easily solvable by a machine, as far as I know... I'm considering some iterative methods to compute the $x_i$ exactly, but I'm wondering if anyone can suggest any embedding techniques out there that only require a distance metric?

In other words, are there any embedding techniques that don't require there to exist an original, higher-dimensional space that you're reducing? Is it sufficient to have a distance metric?



The method you're looking for is called multidimensional scaling (MDS). MDS is a family of methods that attempt to embed a set of points into a vector space such that distances in the embedding space match a given set of input distances. Points in a vector space aren't required as input, only pairwise distances. General input distances are allowed; they don't have to be Euclidean. The details of what 'match' means lead to different algorithms within the MDS family.

It sounds like you could use a variant called nonclassical metric MDS, using the stress criterion. Let $D_{ij}$ be the input distance between points $i$ and $j$. The goal is to find a set of output points $X = \{x_1, ..., x_n\}$ in a Euclidean space, minimizing the squared error between input distances and output distances:

$$\underset{X}{\min} \sum_{i = 1}^{n} \sum_{j \ne i} (D_{ij} - \|x_i - x_j\|)^2$$

There's no general, closed-form solution to this problem, so iterative techniques must be used. Solvers are widely available. It will be possible to exactly preserve input distances when the embedding has as many dimensions as there are data points. It may also be possible to do this using fewer embedding dimensions when the data lie exactly on a low dimensional manifold (depending on the manifold and distance metric). Typically, people want to trade off some amount of accuracy to obtain a lower dimensional embedding.

Classical MDS may also be of interest. Here, input distances are converted to corresponding dot products in a Euclidean space. An embedding is then sought that preserves the dot products. Although the method is formulated in terms of dot products, it's primary purpose is to preserve distances. This problem can be solved using an eigenvalue decomposition, so it's relatively fast. It also returns a solution for all embedding dimensionalities, unlike nonclassical MDS, which requires the dimensionality to be specified a priori.


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.