Is there an algorithm to find the minimal number of dimensions, given the distances between points?

Question

Given some finite set $S := \{x_1,x_2,\ldots,x_k\} \subset \mathbb R^n$ we can define a distance matrix $D = (d(i,j))_{ij}$ with $$d(i,j) = \Vert{x_i - x_j}\Vert$$

where $\Vert \cdot \Vert$ is the euclidean norm.

Is there an algorithm to determine the minimal $m$ just from $D$ such that there are $\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$ with $d(i,j) = \Vert{y_i -y_j}\Vert$?

Or equivalently: Given $D$ as well as some $m$, can we determine whether $D$ can stem from $k$ points in $\mathbb R^m$?

Answer 1

This problem of minimal dimensionality has been studied intensively.

Here is a slightly-edited excerpt from Learning metrics via discriminant kernels and multidimensional scaling: Toward expected euclidean representation by Zhihua Zhang, Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.

Definition 1 (Gower & Legendre, 1986) An $m ×ばつ m$ matrix $[a_{ij} ]$ is Euclidean if $m$ points $P_i$ $(i = 1, . . . , m)$ can be embedded in an Euclidean space such that the Euclidean distance between $P_i$ and $P_j$ is $a_{ij}$.

The following theorem provides the conditions for a matrix to be Euclidean.

Theorem 1 (Gower & Legendre, 1986) The matrix $[a_{ij}]$ is Euclidean if and only if $H^{\text{tr}}BH$ is positive semi-definite, where $B$ is the matrix with elements ${-\frac12}{a_{ij}}^2$ and $H = (I − \mathcal 1_ms)$ is a centering matrix where $I$ is the identity matrix, $\mathcal 1_m$ is the $m \times 1$ vector $(1, 1, \cdots , 1)$ and $s$ is a 1ドル\times m$ vector satisfying $s\mathcal 1_m = 1$.

Note that in theorem 1, if the condition is true for one choice of $s$ (say $s=e_i$, the vector whose entry is 1 at $i$-th position and whose entries are 0 otherwise), it is true for every valid choice of $s$. That fact is included in Metric and Euclidean properties of dissimilarity coefficients by Gower & Legendre, 1986.

Thanks to theorem 1, we know the minimal $m$ such that there are $\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$ with $d(i,j) = \Vert{y_i -y_j}\Vert$ is one less than the minimum order of non-Eucidean sub-square-matrix of $[d(i,j)]$. A simple algorithm to compute that minimum order is to iterate through all submatrix (that allow non-consecutive rows or columns) of $[d(i,j)]$, checking whether each submatrix is Euclidean.

For more related information, we can read that article and dig further.

• flawr: Thanks that is exactly what I'm looking for!
• flawr: Unfortunately this is an instance where the formulation of the theorem does not allow to determine whether it has to hold for one $s$ or every $s$.
• flawr: Apparently it is sufficient to hold for just one such $s$: "It is easy to show that if the result is true for one choice of s (say $s = e_i$) it is true for every valid choice of $s$." (from the original "Metric and Euclidean properties of dissimilarity coefficients" by Gower & Legendre,1986)