# Classical Multidimensional Scaling

Hi,
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 ?

Thanks!

-
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 www.bonneel.com/sqDist.zip (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