# Find Euclidean sub-distances for a given distance matrix

Assume I have a matrix $$(d_{ji})_{ij}$$ of distances between points $$i$$ and $$j$$. These distances could be anything fulfilling the triangle inequality.

Now I would like to find coordinates $$(x_i,y_i)$$ for each $$i$$, so that the Euclidean distances are always less or equal to the real ones:

$$\varepsilon_{ij} = d_{ij} - \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2} \geq 0$$

Furthermore, the sum $$\sum_{ij} \varepsilon_{ij}$$ should be minimal.

How could one approach such a non-linear problem?

EDIT: I would also be interested in other, similar objective functions that somehow minimize the $$\varepsilon_{ij}$$. The important for me is that the "approximation" fulfils the inequalities stated above.

• How large a problem (dimension) do you need to solve? How quickly do you need to solve it? Would you settle for a local optimum which may or may not be globally optimal? – Mark L. Stone May 22 at 17:34
• The matrix has the maximal size $200\times 200$. To be useful, it should solve in under one minute. A heuristic that finds good solutions would also be of interest. – J Fabian Meier May 22 at 21:04
• This looks a lot like a Euclidean Distance Matrix Completion problem (see lix.polytechnique.fr/~liberti/dgp-siam.pdf for a review). Solving it exactly is equivalent to a low-rank optimization problem, which is currently intractable, but at size 200x200 you can usually get pretty good performance from taking a semidefinite relaxation and minimizing the trace of the Gram matrix. – Ryan Cory-Wright May 23 at 18:18
• If you care about finding the underlying points in addition to the Gram matrix then this paper by Biswas and Ye might also be a good starting point optimization-online.org/DB_FILE/2006/07/1436.pdf – Ryan Cory-Wright May 23 at 18:19

Your problem seems to be similar to Multidimensional Scaling (MDS). In MDS, the goal is to represent multidimensional data as good as possible in fewer dimensions.

If high-dimensional distances are represented in $$\mathbb{R}^2$$, classical MDS corresponds to the problem $$\min_{x,y} \sum_{ij} \varepsilon_{ij}^2,$$ using your definition of $$\varepsilon_{ij}$$. This problem allows for a closed-form solution based on eigendecomposition.

In your case, there are two differences. First, you have the additional constraints $$\varepsilon_{ij} \ge 0$$, which are convex in terms of $$x$$ and $$y$$. Second, you have a different objective, which is not convex in $$x$$ and $$y$$. I don't know if there are MDS generalizations that specifically consider these things, but it could be a good starting point.

• Actually, I would also be interested in similar other objectives (like the one you gave). The conditions need to be as they were stated. – J Fabian Meier May 21 at 16:41

Your constraint defines a second order cone, which means it is convex. You can solve it with a specialized solver (for example one listed on the Wikipedia page), although any convex solver might work if the problem is not too hard.

The equivalent SOCP formulation would be: \begin{align}\min& \quad\sum_{ij} \varepsilon_{ij}\\\text{s.t.}& \quad\lVert X_i - X_j \rVert_2 \leq d_{ij} - \varepsilon_{ij}\end{align} where $$X = (x, y)$$.

EDIT: There is nothing in the above formulation that forces $$\varepsilon_{ij}$$ to be equal to $$d_i - \lVert X_i - X_j \rVert_2 \leq d_{ij}$$: it doesn't match the original problem. Such a constraint would make it non-convex. Thanks to Mark L. Stone and Paul Rubin for pointing it out in the comments.

• No. Although the constraints are (convex) SOCP constraints, the objective (as currently proposed) is concave. That makes this a Concave Programming problem. There are some specialized solvers, such as KNITRO, which have special processing for SOCP constraints, even for problems which overall are not convex. i don't know whether such specialized treatment of SOCP constraints would help for this problem. – Mark L. Stone May 22 at 17:32
• Thanks for your comment. I don't understand your assertion that the objective is non-convex: it seems to me that the goal to minimize $\sum_{ij} \varepsilon_{ij}$ makes it linear (and therefore convex) – Gabriel Gouvine May 22 at 17:38
• I edited to add the formulation. Could you please elaborate how the LINEAR objective is an issue, or how the constraint does not define a second order cone? – Gabriel Gouvine May 23 at 7:49
• NO!!!! You can not remove the non-convexity like that. Making $\epsilon_{ij}$ decision variables would make the objective linear, but you would need to add non-convex constraint(s) to relate $\epsilon_{ij}$ to the (other) decision variables $x_i,y_j$. Your proposed constraint (i.e., epigraph formulation): $\epsilon \ge d - \|x\|$ is a non-convex constraint, so it does NOT define a convex cone. The inequality is going in the wrong direction to be convex. – Mark L. Stone May 23 at 13:59
• I don't think this formulation is equivalent to the original problem. The $\epsilon$ variables must be nonnegative (else this version is unbounded). That being the case, $X=0$, $\epsilon=0$ is a trivial optimal solution here, but does not approximate the given distances. – prubin May 23 at 14:25