patternMinor
Is there an algorithm to find the minimal number of dimensions, given the distances between points?
Viewed 0 times
thenumberpointsalgorithmbetweendimensionsfindminimaldistancesthere
Problem
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$?
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$?
Solution
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.
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.
Context
StackExchange Computer Science Q#103559, answer score: 5
Revisions (0)
No revisions yet.