Algorithm 2 Linear partial order embedding (LPOE)
Input: n objects X ,
partial order C,
data matrix X ∈ R
D×n, β > 0 Output: mapping g : X → R
d min W,ξ tr (W) + β |C| X
C
ξ**ijkℓ**
d(xi, xj )
.= (Xi − Xj )
T W (Xi − Xj )
d(xi, xj ) + 1 ≤ d(xk, xℓ) + ξ**ijkℓ**
ξijkℓ ≥ 0 ∀(i, j, k, ℓ) ∈ C
W  0 More precisely, we consider M as being comprised of d elements of H, *i.e.*, {ω1, ω2, . . . , ωd} ⊆
H. The embedding g can thus be expressed as g(x) = (hωp, φ(x)iH)
d p=1 ,
where (·)
d p=1 denotes concatenation over d vectors.

Note that in general, H may be infinite-dimensional, so directly optimizing M may not be feasible. However, by appropriately regularizing M, we may invoke the generalized representer theorem (Schölkopf et al., 2001). Our choice of regularization is the Hilbert-Schmidt norm of M,
which, in this case, reduces to

$$\|M\|_{\mathrm{HS}}^{2}=\sum_{p=1}^{a}\langle\omega_{p},\omega_{p}\rangle_{\mathcal{H}}.$$
d
With this choice of regularization, it follows from the generalized representer theorem that at an optimum, each ωp must lie in the span of the training data, *i.e.*,

$$\omega_{p}=\sum_{i=1}^{n}N_{p i}\phi(x_{i}),\quad p=1,\ldots,d,$$

for some real-valued matrix N ∈ R
d×n. If Φ is a matrix representation of X in H (*i.e.*, Φi = φ(xi)
for xi ∈ X ), then the projection operator M can be expressed as

$$M=N\Phi^{\mathsf{T}}.$$
. (5)
We can now reformulate the embedding problem as an optimization over N rather than M.

Using (5), the regularization term can be expressed as kMk 2HS **= tr(Φ**N
TNΦ
T
**) = tr(**N
TNΦ
T**Φ) = tr(**N
TNK),