I've worked with observations as vectors with both continuous and categorical variables. In both cases one can use dimensionality reduction techniques such as PCA (in the latter case through Correspondence Analysis).

This has been very useful for me to draw the observations in the plane (by taking the 2 first components).

But I don't know an equivalent method for drawing points from a distance matrix. I know the result won't preserve all distances in general, but just an approximation is fine (as when removing components from PCA). To put a concrete example, words with "edit distance" (there are variations which are true metrics).

Is it reasonable to just do PCA on the distance matrix itself and draw the first 2 components? Or is there a better way?

Bonus: in the best case scenario, I would like to work without evaluating my distance function for all pairs (I've read there are space partitioning data structures, but haven't tried them; this is related to the efficient solution to kNN I believe).

  • 2
    $\begingroup$ Mapping distances between a set of objects in euclidean space is known as Multidimensional Scaling. $\endgroup$
    – ttnphns
    Jul 2, 2014 at 4:54
  • $\begingroup$ Thanks, that seems to be exactly what I was looking for. $\endgroup$ Jul 2, 2014 at 6:13
  • $\begingroup$ The answer to the duplicate at stats.stackexchange.com/a/14013 explains what MDS is; the other answers compare and contrast it to PCA. $\endgroup$
    – whuber
    Jul 2, 2014 at 14:05