Algorithm 3 Kernel partial order embedding (KPOE)
Input: n objects X ,
partial order C,
kernel matrix K,
β > 0 Output: mapping g : X → R
n min W,ξ tr (W K) + β |C| X
C
ξ**ijkℓ**
d(xi, xj )
.= (Ki − Kj )
T W (Ki − Kj )
d(xi, xj ) + 1 ≤ d(xk, xℓ) + ξ**ijkℓ**
ξijkℓ ≥ 0 ∀(i, j, k, ℓ) ∈ C
W  0 First, we observe that the i-th column, Ki, of the kernel matrix K can be expressed in terms of K and the i standard basis vector ei:
Ki = Kei.

From this, it follows that distance computations in Algorithm 3 can be equivalently expressed as

$$d(x_{i},x_{j})=(K_{i}-K_{j})^{\mathsf{T}}W(K_{i}-K_{j})$$ $$=(K(e_{i}-e_{j}))^{\mathsf{T}}W(K(e_{i}-e_{j}))$$ $$=(e_{i}-e_{j})^{\mathsf{T}}K^{\mathsf{T}}WK(e_{i}-e_{j}).$$
$$(8)^{\frac{1}{2}}$$
TKTW K(ei − ej ). (8)
If we consider the extremal case where K = I, *i.e.*, we have no prior feature-based knowledge of similarity between points, then Equation 8 simplifies to d(xi, xj **) = (**ei − ej )
T
IW I(ei − ej ) = Wii + Wjj − Wij − Wji.

Therefore, in this setting, rather than defining a feature transformation, W directly encodes the inner products between embedded training points. Similarly, the regularization term becomes

tr(W K) = tr(W I**) = tr(**W).

Minimizing the regularization term can be interpreted as minimizing a convex upper bound on the rank of W (Boyd and Vandenberghe, 2004), which expresses a preference for low-dimensional embeddings. Thus, by setting K = I in Algorithm 3, we directly recover the GNMDS algorithm.

Note that directly learning inner products between embedded training data points rather than a feature transformation does not allow a meaningful out-of-sample extension, to embed unseen data points. On the other hand, by Equation 7, it is clear that the algorithm optimizes over the entire cone of PSD matrices. Thus, if C defines a DAG, we could exploit the fact that a partial order over distances always allows an embedding which satisfies all constraints in C (see Appendix A) to eliminate the slack variables from the program entirely.