MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am doing an MDS with a distance matrix coming from geodesic distances between points X on a 3d mesh (ie., not euclidean distances), and try to find points Y in euclidean space which best approximate these distances.

I thus use matlab's cmdscale, which I think does the same as when the distance matrix is euclidean (I get the same result as whem I do a PCA). Matlab's help states that the distance matrix needs not be euclidean, so it should be working fine.

I now measure the goodness of fit optimized by the MDS, which is a sum of squared errors, and should thus be : sumerr2 = norm(DistMatrix-pdist(Y(:,1:NDim)))
This value decreases when going from 1 to 3 dimensions, but then monotonically increases after 4 dimensions! Why would it be so ? If the fourth dimension increases this number, the MDS should have set it to 0, isn't it ? Or did I miss something.... ?

Also, are there some variants of MDS which assume the distance matrix is geodesic instead of euclidean, and which thus don't just perform a PCA ?


share|cite|improve this question
what does your geodesic distance look like? what is the the exact manifold on which you are working? – Suvrit Jun 22 '11 at 16:19
I've put an example matrix at (each value is the matrix has been squared - warning, it's a 56Mb file). The distances in fact approximate geodesic distances by marching along edges of the mesh only, and I plan to use it for various meshes. – WhitAngl Jun 22 '11 at 16:35
(for my second question, I just tried the SMACOF method which improves things a bit - although I still have the problem that increasing the dimensionality doesn't necessarily reduce the residual) – WhitAngl Jun 22 '11 at 17:56
@Suvrit: Excuse my possible ignorance, but isn't MDS generally used when you don't know what the exact manifold is and you're trying to come up with an estimate based on data with possibly random errors? – Michael Hardy Jun 25 '11 at 20:52
@Michael: I looked at these things long ago; so maybe I am misremembering. I thought that all of this is usually done for computing Euclidean embeddings only (where the distance corresponds to $\|x-y\|$---and a different optimization problem needs to be solved if we are not seeking Euclidean embeddings. – Suvrit Jun 27 '11 at 17:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.