5
$\begingroup$

Suppose that we have $N$ points, and a distance matrix $D \in \mathbb{R}^{N \times N}$ describing the Euclidean distance among those points. For now, assume that we do not necessarily know how many dimensions the original points lived in.

Is there a general way to construct a new matrix $B \in \mathbb{R}^{N \times P}$, which has a distance matrix equal to $D$?

Initially, we can suppose that we are free to make $P$ as large as we want. Is there a way to estimate the minimum $P$ for a given $D$? Does the problem change if we know $P$ in advance?

Please note that a given matrix $B$ will likely not be a unique solution, particularly at small $N$. I am just looking for a general way to construct any $B$ consistent with $D$.

Improve this question
$\endgroup$
4
  • $\begingroup$ It is surely possible. You can simply zero-pad your original vectors with $P-N$ zeros, for example. But probably that's not what you want, right? So, there seems to ba an additional condition missing. $\endgroup$
    – davidhigh
    Jan 15, 2022 at 14:17
  • $\begingroup$ Besides, you can apply a random orthgonal matrix $\in \mathbb R^{P\times P}$ to the padded vectors, which will leave their distance invariant. $\endgroup$
    – davidhigh
    Jan 15, 2022 at 14:35
  • 1
    $\begingroup$ @davidhigh I believe they mean they have the distances, but not the original vectors they came from. $\endgroup$
    – Tyberius
    Jan 15, 2022 at 14:54
  • 2
    $\begingroup$ you might also want to have a look here: math.stackexchange.com/questions/156161/… $\endgroup$
    – Thijs Steel
    Jan 16, 2022 at 9:57

1 Answer 1

Reset to default
7
$\begingroup$

This is more generally known as the distance geometry problem where we are trying to reconstruct data points given distances between all or some of the points with respect to some distance metric.

A common application for $D=3$ is in chemistry/biology where certain experimental techniques can help determine the distance between atoms and the goal is to determine some molecular/protein structure. See for example this question on Matter Modeling. An added complication in this case is that the distance measurements can be noisy.

The case of unknown dimensionality is becoming more common in the context of machine learning. Some examples of this are given in Section 9 of Distance Geometry and Data Science, for which a preprint is also freely available.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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