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).
