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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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.

Improve this answer
$\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, 2024 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$ Commented Jun 17, 2024 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$ Commented Jun 17, 2024 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>

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.