4
$\begingroup$

For an undirected graph with one connected component and distance matrix given by the shortest path between nodes, I would like to embed the nodes in a high dimensional Euclidean space where all distances are preserved. I have no requirement on the number of dimensions.

Can classical multidimensional scaling accomplish this with sufficiently many dimensions? Why or why not?

$\endgroup$
0

2 Answers 2

6
$\begingroup$

If the double centration [1, 2] matrix of your distance (dissimilarity) matrix is gramian (positive semidefinite, that is, all eigenvalues nonnegative) with rank m, then it perfectly spans Euclidean m-dimensional space. So then Torgerson MDS can do it. Actually, this MDS method performs PCA on the double-centration matrix as if it is a covariance or correlation matrix.

Additionally, you may also check an answer describing in lay terms what causes a similarity matrix to be not positive (semi)definite.

$\endgroup$
3
  • $\begingroup$ Thank you for this answer, but the unresolved part of the question is whether the shortest path length distance matrix is Gramian. $\endgroup$ Commented Jun 17 at 2:32
  • $\begingroup$ I've just tried it with the Iris data. I computed euclidean distaces between all 150 observations. Then submitted the matrix to Floyd-Warshall algo returning me the matrix of shortest paths. Then I performed double centering of this matrix. All eigenvalues of the "double centrate" matrix appeared nonnegative. $\endgroup$
    – ttnphns
    Commented Jun 17 at 5:48
  • $\begingroup$ I also asked Floyd-Warshall to return me the matrix of easiest passes (rather than shortest paths). In this case too, eigenvalues of the "double centrate" were all nonnegative. $\endgroup$
    – ttnphns
    Commented Jun 17 at 5:52
5
$\begingroup$
  1. It can't be always true, because the embedding must satisfy the triangle inequality and your graph might not.

  2. Necessary and sufficient conditions are known, but you aren't going to like them>

$\endgroup$

Your Answer

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

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