Learning vector embeddings from distances

So...

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?

Thanks!

• Did the technique proposed by @user20160 work for you? Have you managed to find the vectors you were looking for? Commented Oct 6, 2016 at 22:18
• Maybe you are looking for the Metric embeddings mentioned in this paper: Approximate Nearest Neighbor Search in High Dimensions. Commented Mar 23, 2020 at 13:09

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$$