Suppose I have a kxn array of data with columns of vectors and a distance function defined on these vectors. How do I convert the kxn array into another array of the same shape such that the euclidean norm among the converted vectors is the norm derived by the given distance function? I know you can directly calculate the distance matrix for the data by that given distance function, and derive the coordinates in R^k thereby. But this method is really expensive espesically when the distance function has a complexity O(n^2) or more. So I wonder if there is any simpler algorithm to do that.
1 Answers
It sounds like you are describing multidimension scaling (MDS). One way to do it in Python is with scikit-learn's sklearn.manifold.MDS.
MDS expects the NxN distance (or "dissimilarity") matrix as input, so that doesn't get around the cost of evaluating the distance function. The distance matrix is unavoidably needed for this conversion, so if the distance function itself is expensive, it seems the best thing to do is reduce the number of samples or look for a way to compute fast approximate distances it to speed it up. Also, beware that MDS is usually only approximate. A numerical optimization looks for the best fit of Euclidean norms to the given distances.
Related