I have some arbitrary pairwise similarity metric for some objects, and I am considering trying to find the best way to position the objects onto a line segment such that the pairwise euclidean distances between points on the segment are best representative of the pairwise similarities between the objects. The application is for part of an experimental visualization technique.

As an optimization problem, maybe it could formulated something like this?

$$argmin_f \sum_{e_1, e_2 \in E} | \frac{ S(e_1,e_2) } { \max_{ a, b\in E }S(a,b) }-|f( e_1 ) - f(e_2)||$$ $$f: E \longrightarrow [0,1] $$

In short, if two points are close on the line segment, they should be similar. Is this an existing problem that people have studied? Anyone know anything about it?

  • 1
    $\begingroup$ Sounds like you're looking for a low-distortion embedding into $\mathbb{R}$ with the $\ell_1$ metric. You might want to do a literature search to look at known methods for low-distortion graph embeddings. See also cs.stackexchange.com/q/28642/755 and cs.stackexchange.com/q/14609/755 and cs.stackexchange.com/q/48949/755. $\endgroup$
    – D.W.
    Jan 22, 2016 at 5:11
  • $\begingroup$ I haven't looked at any of those links, but some such methods may depend on S being a metric. ​ ​ $\endgroup$
    – user12859
    Jan 22, 2016 at 5:23
  • $\begingroup$ Also, have you tried applying gradient descent or some other optimization routine to try to minimize that objective function (where the variables are the $f(e)$-values)? $\endgroup$
    – D.W.
    Jan 22, 2016 at 5:41


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.