Feasibility and a fast algorithm for Euclidean distance matrix optimization with ordinal constraints

Abstract

Euclidean distance matrix optimization with ordinal constraints (EDMOC) has found important applications in sensor network localization and molecular conformation. It can also be viewed as a matrix formulation of multidimensional scaling, which is to embed n points in a r-dimensional space such that the resulting distances follow the ordinal constraints. The ordinal constraints, though proved to be quite useful, may result in only zero solution when too many are added, leaving the feasibility of EDMOC as a question. In this paper, we first study the feasibility of EDMOC systematically. We show that if $r\ge n-2$, EDMOC always admits a nontrivial solution. Otherwise, it may have only zero solution. The latter interprets the numerical observations of ’crowding phenomenon’. Next we overcome two obstacles in designing fast algorithms for EDMOC, i.e., the low-rankness and the potential huge number of ordinal constraints. We apply the technique developed in Zhou et al. (IEEE Trans Signal Process 66(3):4331–4346 2018) to take the low rank constraint as the conditional positive semidefinite cone with rank cut. This leads to a majorization penalty approach. The ordinal constraints are left to the subproblem, which is exactly the weighted isotonic regression, and can be solved by the enhanced implementation of Pool Adjacent Violators Algorithm (PAVA). Extensive numerical results demonstrate the superior performance of the proposed approach over some state-of-the-art solvers.

Appendix: Readmap of proof

Due to the fact that ${\mathcal {K}}_+^n(n-2)\subset {\mathcal {K}}_+^n(n-1)={\mathcal {K}}_+^n$, we only need to show the result holds for $r=n-2$. For any ordinal constraints, we consider the situation when $r=n-2$. We will construct n points in $\mathbb {R}^{n-2}$ satisfying that the largest pairwise distance is strictly larger than the others and the rest are equal to each other. By relabelling the vertices properly, the resulting EDM can satisfy the required ordinal constraints.

To construct the points as required, inspired by the regular simplex whose edges are equal to each other, we start from a regular simplex in $\mathbb {R}^{n-3}$, and add two extra vertices in a higher dimensional space such that each of the extra vertices together with the original regular simplex form a regular simplex in a higher dimensional space $\mathbb {R}^{n-2}$. In this way, the distance between the two additional vertices is proved to be larger than the rest distances. It results in a polyhedron which is formed by two regular simplices in $\mathbb {R}^{n-1}$ who share $n-2$ vertices. The n vertices of the polyhedron are the points that we are looking for. Figures. 10, 11 and 12 demonstrate the process when $n=5$.

Before we give the details of the proof of Theorem 3, we start with the following lemmas.

Lemma 2

Let$\{b_k\}$be a nonnegative sequence generated as follows

$$\begin{aligned} \left\{ \begin{array}{ll} b_1 \ \ = \ \ \frac{t}{2} \\ b_k^2 +(\sqrt{t^2-b_k^2}-b_{k+1})^2= & b_{k+1}^2, \quad k=1,2\ldots , \end{array} \right. \end{aligned}$$

(42)

where$t>0$. Then$\{b_k\}$is an increasing sequence and converges to$\frac{\sqrt{2}}{2}t$.

Proof of Lemma 2

The update in (42) implies that

$$\begin{aligned} 0\le b_k \le t,\quad k=1,2\ldots . \end{aligned}$$

The second equation in (42) also gives the increasing order of $\{b_k\}$, i.e.,

$$\begin{aligned} b_1<b_2<\cdots<b_k<\ldots . \end{aligned}$$

In other words, $\{b_k\}$ is an increasing sequence with upper bound t. Therefore, $\{b_k\}$ has a limit as $k\rightarrow \infty$. Suppose the limit is b. By taking limit in the second equation in (42), we can get

$$\begin{aligned} t^2=2b\sqrt{t^2-b^2}. \end{aligned}$$

This gives the solution $b=\frac{\sqrt{2}}{2}$t. The proof is finished. $\square$

Remark

Equations in (42) imply that for all $k=1,2,\ldots$,

$$\begin{aligned} b_k<\frac{\sqrt{2}}{2}t. \end{aligned}$$

Lemma 3

Let${x_1^{(k)},\ldots ,x_{k+1}^{(k)}}\subseteq \mathbb {R}^k$be a set of points satisfying

$$\begin{aligned} \Vert x_i^{(k)}-x_j^{(k)}\Vert =t,\, i\ne j, \end{aligned}$$

(43)

where the superscript stands for the dimension of vectors. Denote the centroid of$\{x_1^{(k)},\ldots , x_{k+1}^{(k)}\}$as$O^{(k)}$. Let the distance between$O^{(k)}$and$x_i^{(k)}$be$b_k$. We have the following equations

$$\begin{aligned} \left\{ \begin{array}{ll} b_1 = \frac{t}{2},& \\ b_k^2 +(\sqrt{t^2-b_k^2}-b_{k+1})^2 = b_{k+1}^2,& \ k=1,2\ldots . \end{array} \right. \end{aligned}$$

Proof of Lemma 3

Without the loss of generality, let $O^{(k)}$ lie in the origin. Then $b_k=\Vert O^{(k)}-x_i^{(k)}\Vert , \ \ i=1,\ldots ,k+1$. Now define ${x_1^{(k+1)},\ldots ,x_{k+2}^{(k+1)}}\subseteq \mathbb {R}^{k+1}$ as follows

$$\begin{aligned} x_i^{(k+1)}= \begin{bmatrix} x_i^{(k)} \\ 0 \end{bmatrix}, \quad i=1,\ldots ,k+1,\qquad {x^{(k+1)}_{k+2}}= \begin{bmatrix} {O^{(k)}} \\ {h_{k+1}} \end{bmatrix}, \ \ h_{k+1}>0. \end{aligned}$$

By letting $h_{k+1}=\sqrt{t^2-b_k^2}$, there is

$$\begin{aligned} \Vert x_i^{(k+1)}-x_j^{(k+1)}\Vert =t,\quad \forall \ \ i<j, \ \ i,\ j=1,\ldots ,k+2. \end{aligned}$$

(44)

Let the centroid of ${x_1^{(k+1)},\ldots ,x_{k+2}^{(k+1)}}$ be $O^{(k+1)}$. There is

$$\begin{aligned} O^{(k+1)}=\frac{1}{k+2}\sum _{i=1}^{k+2}x^{(k+1)}_i. \end{aligned}$$

Notice

$$\begin{aligned} {\hat{O}^{(k)}}:=\begin{bmatrix} O^{(k)}\\ 0 \end{bmatrix} =\frac{1}{k+1}\sum _{i=1}^{k+1}x^{(k+1)}_i. \end{aligned}$$

We get $O^{(k+1)}=\frac{k+1}{k+2}\hat{O}^{(k)}+\frac{1}{k+2}x_{k+2}^{(k+1)}$ which implies that $O^{(k+1)}$ lies between $\hat{O}^{(k)}$ and $x_{k+2}^{(k+1)}$. The geometric relation of $O^{(k+1)},\hat{O}^{(k)},x_i^{(k+1)},x_{k+2}^{(k+1)}$ is demonstrated in Fig. 9.

Fig. 9

Geometric relation of $O^{(k+1)},\ \hat{O}^{(k)},\ x_i^{(k+1)},\ x_{k+2}^{(k+1)}$

Consequently, we have the following relationship

$$\begin{aligned} t^2=b_k^2+(\sqrt{t^2-b_k^2}-b_{k+1})^2. \end{aligned}$$

In particular, if k=1, $b_1=\frac{t}{2}$. The proof is finished. $\square$

Next we give the proof of Theorem 3.

Proof of Theorem 3

Note that ${\mathcal {K}}_+^n(n-2)\subset {\mathcal {K}}_+^n(n-1)={\mathcal {K}}_+^n$, we only need to show the result holds for $r=n-2$.

Let $r=n-2$. To show the result, let’s first construct a nontrivial feasible solution D satisfying

$$\begin{aligned} \left\{ \begin{array}{ll} D_{12}>D_{ij},&\quad \forall \ (i,j)\ne (1,2),\ \,\ i<j, \\ D_{ij}=D_{sk},&\quad \forall \ (i,j),\ (s,k)\ne (1,2),\, i<j,\ \, s<k. \end{array} \right. \end{aligned}$$

(45)

To the end, we can first pick up a set of points $\{ x_1^{(n-3)},\ldots ,x_{n-2}^{(n-3)} \}\subseteq \mathbb {R}^{n-3}$ satisfying (see Fig. 10 for $n=5$)

$$\begin{aligned} \Vert x_i^{(n-3)}-x_j^{(n-3)}\Vert =t,\quad \forall \ \ i<j,\, i,\ j=1,\ldots ,{n-2}. \end{aligned}$$

This is already proved in Theorem 1. Moreover, denote the centroid of $x_1^{(n-3)}, \ldots , x_{n-2}^{(n-3)}$ as $O^{(n-3)}$. Suppose $O^{(n-3)}$ is located at the origin. As we defined above, let

$$\begin{aligned} b_{n-3}=\Vert O^{(n-3)}-x_i^{(n-3)}\Vert , \quad \forall \ i=1,\ldots ,n-2. \end{aligned}$$

Now let $x_i^{(n-2)}\in \mathbb {R}^{n-2},\ i=1,\ldots ,n-1$ be generated as follows (see Figs. 11 and 12 for $n=5$)

$$\begin{aligned} x_i^{(n-2)}= \begin{bmatrix} x_i^{(n-3)} \\ 0 \end{bmatrix}, \quad i=1,\ldots ,n-2,\ \ x_{n-1}^{(n-2)}= \begin{bmatrix} {O^{(n-3)}} \\ h \end{bmatrix} , \qquad x_n^{(n-2)}= \begin{bmatrix} {O^{(n-3)}} \\ -h \end{bmatrix} , \quad h>0. \end{aligned}$$

Then we have

$$\begin{aligned} (\hat{O}^{(n-3)}-x_{n-1}^{(n-2)})^T(x_i^{(n-2)}-x_j^{(n-2)})=0,\quad \forall \, i<j,\ \ i,\ j=1,\ldots ,{n-2}, \end{aligned}$$

where

$$\begin{aligned} {\hat{O}^{(n-3)}=\begin{bmatrix} O^{(n-3)}\\ 0 \end{bmatrix} \in \mathbb {R}^{n-2}.} \end{aligned}$$

By letting $h=\sqrt{t^2-b_{n-3}^2}$, we get

$$\begin{aligned} \Vert x_i^{(n-2)}-x_j^{(n-2)}\Vert =t,\quad \forall \ i<j, \ \ i,\ j=1,\ldots ,n,\ \ (i,j)\ne {(n-1,n)}. \end{aligned}$$

Next, we will show that

$$\begin{aligned} \Vert x_{n-1}^{(n-2)}-x_{n}^{(n-2)}\Vert >t. \end{aligned}$$

By Lemma 3, we have (43) for $b_k$ and $b_{k+1}$, implying that $b_{n-3}<\frac{\sqrt{2}t}{2}$ by Lemma 2. Therefore, $h=\sqrt{t^2-b_{n-3}^2}>\frac{\sqrt{2}t}{2}$ for all $n\ge 4$. In other words,

$$\begin{aligned} \Vert x_n^{(n-2)}-x_{n-1}^{(n-2)}\Vert =2h>\sqrt{2}t>t. \end{aligned}$$

Consequently, the EDM generated by $\{x_1^{(n-2)},\ldots ,x_n^{(n-2)}\}\subset \mathbb {R}^{n-2}$ satisfies (45). For any $\pi (n)=\{(i_1,j_1),\ldots ,(i_m,j_m)\}$, to get a nontrivial solution of $F(\pi (n),n-2)$, we construct

$$\begin{aligned} \hat{D}_{i_1j_1}=\Vert x_n^{(n-2)}-x_{n-1}^{(n-2)}\Vert ^2, \quad \hat{D}_{ij}=\Vert x_i^{(n-2)}-x_j^{(n-2)}\Vert ^2, \quad (i,j)\in \pi (n)\backslash (i_1,j_1). \end{aligned}$$

Then $\hat{D}$ is a nontrivial feasible solution. $\square$

Fig. 10

$x_1^{(2)},x_2^{(2)},x_3^{(2)}$

Fig. 11

$x_1^{(3)},\ldots , x_4^{(3)}$

Fig. 12

$x_1^{(3)},\ldots , x_5^{(3)}$