
| Accuracy   |          |       |
|------------|----------|-------|
| C          | Diagonal | Full  |
| Full       | 0.604    | 0.754 |
| Length-2   | 0.621    | 0.756 |
| Processed  | 0.629    | 0.760 |

Table 5: aset400 embedding results (Biography kernel) for three possible refinements of the constraint set. *Full* includes all similarity measurements, with no pruning for consistency or redundancy. *Length-2* removes all length-2 cycles (*i.e.*, (**i, j, k, ℓ**) and (**k, ℓ, i, j**)).

Processed finds an approximate maximal consistent subset, and removes redundant constraints.

## 6. Hardness Of Dimensionality Reduction

The algorithms given in Sections 3 and 4 attempt to produce low-dimensional solutions by regularizing W, which can be seen as a convex approximation to the rank of the embedding. In general, because rank constraints are not convex, convex optimization techniques cannot efficiently minimize dimensionality. This does not necessarily imply other techniques could not work. So, it is natural to ask if exact solutions of minimal dimensionality can be found efficiently, particularly in the multidimensional scaling scenario, *i.e.*, when K = I (Section 3.3).

As a special case, one may wonder if any instance (X , C) can be satisfied in R
1. As Figure 7 demonstrates, not all instances can be realized in one dimension. Even more, we show that it is NP-Complete to decide if a given C can be satisfied in R
1. Given an embedding, it can be verified in polynomial time whether C is satisfied or not by simply computing the distances between all pairs and checking each comparison in C, so the decision problem is in NP. It remains to show that the R

1 partial order embedding problem (hereafter referred to as *1-POE*) is NP-Hard. We reduce from the *Betweenness* problem (Opatrny, 1979), which is known to be NP-complete.

Definition 6.1 (Betweenness) Given a finite set Z and a collection T *of ordered triples* (**a, b, c**) of distinct elements from Z, is there a one-to-one function f : Z → R *such that for each* (**a, b, c**) ∈ T,
either f(a) < f(b) < f(c) or f(c) < f(b) < f(a)?

## Theorem 1 1-Poe Is Np-Hard.

Proof Let (**Z, T**) be an instance of Betweenness. Let X = Z, and for each (**a, b, c**) ∈ T, introduce constraints (**a, b, a, c**) and (**b, c, a, c**) to C. Since Euclidean distance in R
1is simply line distance, these constraints force g(b) to lie between g(a) and g(c). Therefore, the original instance
(**Z, T**) ∈ Betweenness if and only if the new instance (X , C) ∈ 1-POE. Since Betweenness is NP-Hard, 1-POE is NP-Hard as well.

Since 1-POE can be reduced to the general optimization problem of finding an embedding of minimal dimensionality, we can conclude that dimensionality reduction subject to partial order constraints is also NP-Hard.