When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations

The Euclidean Distance Matrix (EDM) is a matrix containing the squared Euclidean distances between points in a set. A central problem in Distance Geometry is determining whether a given matrix is an EDM [5, 25, 11, 13]. That is, the task is to identify whether a given distance space can be isometrically embedded into ${\mathrm{\ell }}_2$-spaces, or equivalently, the pairwise Euclidean distances among points in ${ℝ}^d$ ($d\ge 1$). This problem has a rich history, originating with Cayley [7], whose observations were formalized by Menger [28], leading to Cayley-Menger determinants. Schoenberg [30] further advanced the field by characterizing ${\mathrm{\ell }}_2$-embeddable distances using negative type inequalities. Blumenthal’s monograph [5] remains a foundational text, documenting the theoretical underpinnings of this area.

This problem has numerous applications, including sensor network localization [29, 14], molecular conformation [21], data visualization [6], statistics [17], psychology [34, 31], learning image manifolds [36], handwriting recognition [24], studying musical rhythms [12], and signal processing [15]. The complexity of determining whether a matrix is an EDM is well understood, and it can be efficiently addressed using Singular Value Decomposition (SVD) [6, 35].

In many practical applications involving EDMs, errors due to noise, missing values, or approximation inaccuracies are common. To address these challenges, several heuristic approaches based on Multidimensional Scaling, Low-Rank Matrix Approximation, and Semidefinite Programming have been developed to reconstruct the matrix and create an embedding that minimizes the impact of these errors. We refer readers to [6, 15] for a comprehensive overview of the extensive literature on this topic.

Despite the importance and numerous practical applications of the EDM recognition problem with noise and errors, little was known about its computational complexity until recently. A notable exception is the work of Sidiropoulos, Wang, and Wang [32], which initiates the study of EDM in the presence of outliers. The work of Sidiropoulos et al. serves as the initial foundation for our studies.

In this paper, we address the algorithmic question of minimizing the number of edits required to transform a given distance matrix into EDM. Specifically, we aim to apply the minimum number of modifications to a given distance space $(X,\rho )$ with distance function $\rho$, such that the resulting distance space can be isometrically embedded into a $d$-dimensional Euclidean space ${ℝ}^d$. We consider two types of editing operations.

The first operation is element deletion. In matrix terms, this operation corresponds to deleting the row and column associated with the element we choose to remove. Following Sidiropoulos, Wang, and Wang [32], we refer to the elements removed from the distance space as outliers.

The second operation is distance modification. Let $X^{(2)}$ denote the set of unordered pairs of distinct elements in $X=\{x_1,x_2,\mathrm{\dots }\}$. For a pair of elements $x_i,x_j\in X$, the modification operation alters the distance $\rho (x_i,x_j)$. In terms of the distance matrix, this operation changes the $ij$-th and the $ji$-th entries. The problem of minimizing the number of modification operations to embed the resulting distance space in general metric spaces was studied in [18, 9], and embedding into ultrametric spaces was investigated in [9, 8].

Our primary algorithmic question is as follows: given integers $k_O$ and $k_M$, can a distance space $(X,\rho )$ be transformed into a distance space that is embeddable in ${ℝ}^d$ by removing at most $k_O$ outliers and performing at most $k_M$ modifications? In fact, we address an even more general weighted version of this problem, where each operation (outlier deletion or distance modification) is assigned a specific weight. More precisely, we study:

Two special cases of Euclidean Embedding Editing are of particular importance. The variant of the problem with $k_M=0$, that is, of placing all but $k_O$ outlier points of a distance space $(X,\rho )$ into a Euclidean space ${ℝ}^d$ of a given dimension $d$ such that the Euclidean distance between any pair of points $x,$ is equal to $\rho (x,y)$, is called Euclidean Embedding with Outliers [32]. For the variant with $k_O=0$, that is, without deletion of outliers, following [18], we use the name Euclidean Metric Violation Distance.

EXAMPLE: The distance space $𝒳=(X,\rho )$ with $X=\{1,\mathrm{\dots },9\}$ and $\rho$ defined by distance matrix $D$, where the $ij$-th entry of $D$ is ${\rho }^2(i,j)$

and $k_O=1$, $k_M=2$, $d=2$, all weights equal to one, and $W=3$, is a yes-instance of Euclidean Embedding Editing. Indeed, the distance space ${𝒳}^{\prime }=(X^{\prime },{\rho }^{\prime })$ defined by distance matrix $D^{\prime }$ in Fig. 1 that can be obtained from $𝒳$ by modifying distances between $\{1,2\}$ and $\{3,5\}$ and deleting outlier $7$, is isometrically embedable in ${ℝ}^2$.

Let $X$ be a set. A function $\rho :X\times X\to {ℝ}_{\ge 0}$ is a distance on $X$ if: (i) $\rho$ is symmetric, that is, for any $x,y\in X$, $\rho (x,y)=\rho (y,x)$, and (ii) $\rho (x,x)=0$ for all $x\in X$. Then, $(X,\rho )$ is called a distance space. If, in addition $\rho$ satisfies a triange inequality: $\rho (x,z)\le \rho (x,y)+\rho (y,z)$, for any $x,y,z\in X$, then $\rho$ is called a semimetric on $X$. And if $\rho (x,y)=0$ only for $x=y$, then $\rho$ is called a metric, and $(X,\rho )$ a metric space.

More precisely, recall that for two points $p,q\in {ℝ}^d$, the Euclidean distance between $p$ and $q$ is ${\Vert p-q\Vert }_2=\sqrt{⟨p,p⟩+⟨q,q⟩-2⟨p,q⟩}$. We say that distance space $(X,\rho )$ is isometrically embeddable into ${ℝ}^d$ if there is a map, called isometric embedding, $\phi :X\to {ℝ}^d$ such that $\rho (x,y)={\Vert \phi (x)-\phi (y)\Vert }_2$ for all $x,y\in X$. Notice that we do not require $\phi$ to be injective, that is, several points of $(X,\rho )$ may be mapped to the same point of ${ℝ}^d$. Throughout the paper, whenever we mention an embedding, we mean an isometric embedding. Moreover, when we use the term $d$-embedding, we are referring to embedding into ${ℝ}^d$. A $d$-embeddable distance space is strongly $d$-embeddable if it is not $(d-1)$-embeddable. We use $X^{(2)}$ to denote the set of unordered pairs of two distinct elements of $X$. As convention, we assume that the empty set of points is $d$-embeddable for every $d$.

Let $𝒳=(X,\rho )$ be a distance space where $X=\{x_1,\mathrm{\dots },x_n\}$, and let ${\rho }_{i,j}=\rho (x_i,x_j)$ for all $i,j\in \{1,\mathrm{\dots },n\}$. Then $𝒳$ is equivalently defined by the distance matrix $D(\rho )$, where $D{(\rho )}_{i,j}={\rho }_{i,j}^2$.

We drop the explicit reference to $\rho$ when it is clear from the context and instead of $D(\rho )$, simply write $D$. Suppose that $𝒳$ is embeddable into ${ℝ}^d$. The ordered set $P=(p_1,\mathrm{\dots },p_n)$ of points in ${ℝ}^d$ is said to be a realization of $𝒳$ if there is an embedding $\phi :X\to {ℝ}^d$ such that $\phi (x_i)=p_i$ for all $i\in \{1,\mathrm{\dots },n\}$. We use the well-known property (see e.g. [15]) that a realization is unique up to rigid transformations of ${ℝ}^d$, that is, distance-preserving transformations of Euclidean space (rotations, reflections, translations).

A realization can be constructed (if it exists) in polynomial time.

We will use the well-known characteristic of strong embeddability of a distance space into a Euclidean space. For $r+1$ points $x_0,x_1,\mathrm{\dots },x_r$ of distance space $(X,\rho )$ the Cayley-Menger determinant is the determinant of the matrix obtained from the distance matrix by prepending a row and a column whose first element is zero and the other elements are one. Formally, let ${\rho }_{i,j}=\rho (x_i,x_j)$, $i,j\in \{0,\mathrm{\dots },r\}$. Then the Cayley-Menger determinant is

Thus, the embedding of the distance space $𝒳=(X,\rho )$ into ${ℝ}^d$ is essentially characterized by $d+1$ “anchor” points of $X$. Note that in a realization of $𝒳$ that is strongly $d$-embeddable, the anchor points correspond to a set of $d+1$ points in general position in ${ℝ}^d$.

Following [5], we define sets of independent points.

Then our “anchors” are independent sets of size $d+1$. We use the following fact that the family of independent sets has matroid-like properties (implicit in [5, Chapter IV]).

For statements marked with ($\star$), the proofs are omitted in this extended abstract and is deferred to the full version.

In this section, we show that, given an instance of Euclidean Embedding Editing, one can in polynomial time construct an equivalent instance where the number of points is upper-bounded by a polynomial of $k=k_O+k_M$ and $d$ and, moreover, the encoding of the weights is also polynomial in these parameters.

We remark that Theorem 8 does not provide a kernelization algorithm according to the standard definition [10] as the size of the output instance is not upper-bounded by a function of the parameter – the distances between the points remain the same as in the input instance. Moreover, since Euclidean Embedding Editing is a decision problem, the word “solve” in the statement of Theorem 8 technically only refers to deciding correctly whether the instance is a yes-instance. However, if the instance is determined to be a yes-instance, then our algorithm can also output a solution that witnesses this, i.e., the outlier set and modified new distance values (if any). This additional feature of our compression algorithm will be used later in our FPT algorithm for Euclidean Embedding Editing.

In the proof of Theorem 8, we first design a polynomial-time $(d+3)$-approximation algorithm (Section 3.1). This algorithm allows us, given an instance of the problem, either find a set of at most $(d+3)k$ points $A$ such that $(X\setminus A,\rho )$ is $d$-embeddable or conclude that we have a no-instance.

In the first case, we iteratively construct a sequence of metric bases $Y_1,\mathrm{\dots },Y_{\mathrm{\ell }}$ for $(Z,\rho )$ using Proposition 6, where initially $Z:=X\setminus A$ and in each iteration, we delete the points of the constructed basis from $Z$. If $X\setminus A$ is sufficiently large, then there is a subsequence of bases of the same size with at least $2(k_O+2k_M)+1$ elements. We select the first subsequence with this property. The crucial property exploited by our algorithm is that this subsequence uniquely defines embeddings of the majority of the points assuming that we have a yes-instance of the problem. We use this to give a series of reduction rules that identify points in $A$ that should be outliers in any solution and irrelevant points of $X\setminus A$ that could be deleted.

In this section, we give our FPT algorithm for Euclidean Embedding Editing.

We prepare for it by recalling the relevant definitions and facts from [4]. In what follows, let $R$ be a real closed field and $\mathrm{\ell }\in \mathbb{N}$. Let ${𝒫}_{\mathrm{\ell }}\subset R[X_1,\mathrm{\dots },X_t]$ be a finite set of $s$ polynomials each of degree at most $\mathrm{\ell }$.

In this section, we give an FPT-time 2-approximation for Unweighted Euclidean Embedding with Outliers (UEEO) parameterized by the dimension $d$. Recall that in the optmization version of this problem, the input is $(𝒳=(X,\rho ),d)$ where $(X,\rho )$ is a distance space and the goal is to output a $d$-outlier set of minimum size.

Our main idea is to give a randomized algorithm generating sequences $U_0,\mathrm{\dots },U_{d+1}$ and $A_1,\mathrm{\dots },A_{d+2}$, where each $A_i$ is a $d$-outlier set that is associated with the independent set $U_{i-1}$ of size $i-1$. The construction of these sequences is roughly as follows, starting from $U_0=\mathrm{\varnothing }$ and proceeding iteratively. For each $U_{i-1}$:

1. 1.

   Any element that cannot be $d$-embedded along with $U_{i-1}$ gets added to $A_i$.

2. 2.

   We compute those elements that can be added to $U_{i-1}$ without increasing its embedding dimension, and associate a graph with these such that every $d$-outlier set disjoint from $U_{i-1}$ includes a vertex cover of this graph. We then 2-approximate the minimum vertex cover of this graph and add it to $A_i$.

3. 3.

   For the remaining elements (call this set $W$):

   1. (a)

      Take all of $W$ in $A_i$ (which makes $A_i$ a 2-approximation if at least half of $W$ is in the solution),

   2. (b)

      Uniformly at random add an element of $W$ to $U_{i-1}$, resulting in $U_i$ (which gives an independent set with sufficiently high probability if at least half of $W$ is not in some fixed minimum $d$-outlier set).