
$$(x_{j})\rangle_{\mathcal{H}}=k(x_{i},x_{j}).$$

where K is the kernel matrix over X :
K = ΦTΦ, with Kij = hφ(xi), φ(xj )iH = k(xi, xj ).

To formulate the distance constraints in terms of N, we first express the embedding g in terms of N
and the kernel function:

$g(x)=M(\phi(x))=N\Phi^{T}(\phi(x))=N\left(\langle\Phi_{i},\phi(x)\rangle_{\mathcal{H}}\right)_{i=1}^{n}=N\left(k(x_{i},x)\right)_{i=1}^{n}=NK_{x}$
where Kx is the column vector formed by evaluating the kernel function k at x against the training set. The inner product matrix of embedded points can therefore be expressed as

$$A=K N^{\mathsf{T}}N K,$$

which allows to express the distance constraints in terms of N and the kernel matrix K:

$$(K_{i}-K_{j})^{\mathsf{T}}N^{\mathsf{T}}N(K_{i}-K_{j})+1\leq(K_{k}-K_{\ell})^{\mathsf{T}}N^{\mathsf{T}}N(K_{k}-K_{\ell}).$$

The embedding problem thus amounts to solving the following optimization problem in N and ξ:

$$\min_{N_{\ell}\geq0}\quad\quad\text{tr}(N^{\mathsf{T}}NK)+\frac{\beta}{|\mathcal{C}|}\sum_{\mathcal{C}}\xi_{ijk\ell}$$ (6) s.t. $$(K_{i}-K_{j})^{\mathsf{T}}N^{\mathsf{T}}N(K_{i}-K_{j})+1\leq(K_{k}-K_{\ell})^{\mathsf{T}}N^{\mathsf{T}}N(K_{k}-K_{\ell})+\xi_{ijk\ell},$$ $$\forall(i,j,k,\ell)\in\mathcal{C}.$$
$$(6)$$

Again, the distance constraints in (6) are non-convex due to the differences of quadratic terms.

And, as in the previous section, N only appears in the form of inner products NTN in (6) - both in the constraints, and in the regularization term - so we can again derive a convex optimization problem by changing variables to W.= NTN  0. The resulting embedding problem is listed as Algorithm 3, again a semi-definite programming problem (SDP), with an objective function and constraints that are linear in W.

After solving for W, the matrix N can be recovered by computing the spectral decomposition W = V ΛV
T, and defining N = Λ1/2V
T. The resulting embedding function takes the form:

$$g(x)=\Lambda^{1/2}V^{\mathsf{T}}K_{x},$$

As in Schultz and Joachims (2004), this formulation can be interpreted as learning a Mahalanobis distance metric ΦWΦ
T over H. More generally, we can view this as a form of kernel learning, where the kernel matrix A is restricted to the set

$$A\in\left\{K W K\;:\;W\succeq0\right\}.$$
A ∈ {**KW K** : W  0} . (7)

## 3.3 Connection To Gnmds

We conclude this section by drawing a connection between Algorithm 3 and the generalized nonmetric MDS (GNMDS) algorithm of Agarwal et al. (2007).

$$\left(7\right)$$
