
$$(3)$$

Now, for a relative comparison (**i, j, k, ℓ**), we can express the distance constraint (1) between embedded points as follows:

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

These inequalities can then be used to form the constraint set of an optimization problem to solve for M. Because, in general, C may not be satisfiable by a linear projection of X , we soften the constraints by introducing a slack variable ξ**ijkℓ** ≥ 0 for each constraint, and minimize the empirical hinge loss over constraint violations 1/|C|PC
ξ**ijkℓ**. This choice of loss function can be interpreted as a generalization of ROC area (see Appendix C).

To avoid over-fitting, we introduce a regularization term tr(MTM), and a trade-off parameter β > 0 to control the balance between regularization and loss minimization. This leads to a regularized risk minimization objective:

$$\begin{array}{r l}{{\operatorname*{min}_{M\xi\geq0}}}&{{\operatorname{tr}(M^{\mathsf{T}}M)+{\frac{\beta}{|\mathcal{C}|}}\sum_{\ell}\xi_{i j k\ell}}}\\ {{\mathrm{s.t.}}}&{{(X_{i}-X_{j})^{\mathsf{T}}M^{\mathsf{T}}M(X_{i}-X_{j})+1\leq(X_{k}-X_{\ell})^{\mathsf{T}}M^{\mathsf{T}}M(X_{k}-X_{\ell})+\xi_{i j k\ell},}}\\ {{}}&{{\forall(i,j,k,\ell)\in\mathcal{C}.}}\end{array}$$
$${\mathrm{}}(4)$$

After learning M by solving this optimization problem, the embedding can be extended to out-ofsample points x
′ by applying the projection: x
′7→ Mx′.

Note that the distance constraints in (4) involve differences of quadratic terms, and are therefore not convex. However, since M only appears in the form MTM in (4), we can equivalently express the optimization problem in terms of a positive semi-definite matrix W.= MTM. This change of variables results in Algorithm 2, a *convex* optimization problem, more specifically a semi-definite programming (SDP) problem (Boyd and Vandenberghe, 2004), since objective and constraints are linear in W, including the linear matrix inequality W  0. The corresponding inner product matrix is

$$A=X^{\mathsf{T}}W X.$$

Finally, after the optimal W is found, the embedding function g can be recovered from the spectral decomposition of W:

$$W=V\Lambda V^{\mathsf{T}}\quad\Rightarrow\quad g(x)=\Lambda^{1/2}V^{\mathsf{T}}x.$$

## 3.2 Non-Linear Projection Via Kernels

The formulation in Algorithm 2 can be generalized to support non-linear embeddings by the use of kernels, following the method of Globerson and Roweis (2007): we first map the data into a reproducing kernel Hilbert space (RKHS) H via a feature map φ with corresponding kernel function k(x, y) = hφ(x), φ(y)iH; then, the data is mapped to R
d by a linear projection M : H → R
d. The embedding function g : X → R
dis the therefore the composition of the projection M with φ:

$$g(x)=M(\phi(x)).$$

Because φ may be non-linear, this allows to learn a non-linear embedding g.