1
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks that is exactly what I'm looking for! $\endgroup$ – flawr Jan 29 at 22:15
  • $\begingroup$ 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$. $\endgroup$ – flawr Jan 29 at 22:24
  • $\begingroup$ 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) $\endgroup$ – flawr Jan 29 at 22:24

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.