Euclidean distance matrix

In mathematics, a Euclidean distance matrix is an Template:Math matrix representing the spacing of a set of Template:Mvar points in Euclidean space. For points $x_1,x_2,\dots ,x_n$ in Template:Mvar-dimensional space Template:Math, the elements of their Euclidean distance matrix Template:Mvar are given by squares of distances between them. That is

$\begin{array}{cc}A& =(a_{ij});\\ a_{ij}& =d_{ij}^2=\Vert x_i-x_j{\Vert }^2\end{array}$

where $\Vert \cdot \Vert$ denotes the Euclidean norm on Template:Math.

$A=\left[\begin{array}{ccccc}0& d_{12}^2& d_{13}^2& \dots & d_{1n}^2\\ d_{21}^2& 0& d_{23}^2& \dots & d_{2n}^2\\ d_{31}^2& d_{32}^2& 0& \dots & d_{3n}^2\\ ⋮& ⋮& ⋮& \ddots & ⋮& \\ d_{n1}^2& d_{n2}^2& d_{n3}^2& \dots & 0\end{array}\right]$

In the context of (not necessarily Euclidean) distance matrices, the entries are usually defined directly as distances, not their squares. However, in the Euclidean case, squares of distances are used to avoid computing square roots and to simplify relevant theorems and algorithms.

Euclidean distance matrices are closely related to Gram matrices (matrices of dot products, describing norms of vectors and angles between them). The latter are easily analyzed using methods of linear algebra. This allows to characterize Euclidean distance matrices and recover the points $x_1,x_2,\dots ,x_n$ that realize it. A realization, if it exists, is unique up to rigid transformations, i.e. distance-preserving transformations of Euclidean space (rotations, reflections, translations).

In practical applications, distances are noisy measurements or come from arbitrary dissimilarity estimates (not necessarily metric). The goal may be to visualize such data by points in Euclidean space whose distance matrix approximates a given dissimilarity matrix as well as possible — this is known as multidimensional scaling. Alternatively, given two sets of data already represented by points in Euclidean space, one may ask how similar they are in shape, that is, how closely can they be related by a distance-preserving transformation — this is Procrustes analysis. Some of the distances may also be missing or come unlabelled (as an unordered set or multiset instead of a matrix), leading to more complex algorithmic tasks, such as the graph realization problem or the turnpike problem (for points on a line).

Properties

By the fact that Euclidean distance is a metric, the matrix Template:Mvar has the following properties.

• All elements on the diagonal of Template:Mvar are zero (i.e. it is a hollow matrix); hence the trace of Template:Mvar is zero.
• Template:Mvar is symmetric (i.e. $a_{ij}=a_{ji}$).
• $\sqrt{a_{ij}}\le \sqrt{a_{ik}}+\sqrt{a_{kj}}$ (by the triangle inequality)
• $a_{ij}\ge 0$

In dimension Template:Mvar, a Euclidean distance matrix has rank less than or equal to Template:Math. If the points $x_1,x_2,\dots ,x_n$ are in general position, the rank is exactly Template:Math

Distances can be shrunk by any power to obtain another Euclidean distance matrix. That is, if $A=(a_{ij})$ is a Euclidean distance matrix, then $({a_{ij}}^s)$ is a Euclidean distance matrix for every Template:Math.

Relation to Gram matrix

The Gram matrix of a sequence of points $x_1,x_2,\dots ,x_n$ in Template:Mvar-dimensional space Template:Math is the Template:Math matrix $G=(g_{ij})$ of their dot products (here a point $x_i$ is thought of as a vector from 0 to that point):

$g_{ij}=x_i\cdot x_j=\Vert x_i\Vert \Vert x_j\Vert \cos \theta$, where $\theta$ is the angle between the vector $x_i$ and $x_j$.

In particular

$g_{ii}=\Vert x_i{\Vert }^2$ is the square of the distance of $x_i$ from 0.

Thus the Gram matrix describes norms and angles of vectors (from 0 to) $x_1,x_2,\dots ,x_n$.

Let $X$ be the Template:Math matrix containing $x_1,x_2,\dots ,x_n$ as columns. Then

$G=X^{\mathsf{\text{T}}}X$, because $g_{ij}=x_i^{\mathsf{\text{T}}}{x}_j$ (seeing $x_i$ as a column vector).

Matrices that can be decomposed as $X^{\mathsf{\text{T}}}X$, that is, Gram matrices of some sequence of vectors (columns of $X$), are well understood — these are precisely positive semidefinite matrices.

To relate the Euclidean distance matrix to the Gram matrix, observe that

$d_{ij}^2=\Vert x_i-x_j{\Vert }^2=(x_i-x_j{)}^{\mathsf{\text{T}}}(x_i-x_j)=x_i^{\mathsf{\text{T}}}{x}_i-2x_i^{\mathsf{\text{T}}}{x}_j+x_j^{\mathsf{\text{T}}}{x}_j=g_{ii}-2g_{ij}+g_{jj}$

That is, the norms and angles determine the distances. Note that the Gram matrix contains additional information: distances from 0.

Conversely, distances $d_{ij}$ between pairs of Template:Math points $x_0,x_1,\dots ,x_n$ determine dot products between Template:Mvar vectors $x_i-x_0$ (Template:Math):

$g_{ij}=(x_i-x_0)\cdot (x_j-x_0)=\frac{1}{2}(\Vert x_i-x_0{\Vert }^2+\Vert x_j-x_0{\Vert }^2-\Vert x_i-x_j{\Vert }^2)=\frac{1}{2}(d_{0i}^2+d_{0j}^2-d_{ij}^2)$

(this is known as the polarization identity).

Characterizations

For a Template:Math matrix Template:Mvar, a sequence of points $x_1,x_2,\dots ,x_n$ in Template:Mvar-dimensional Euclidean space Template:Math is called a realization of Template:Mvar in Template:Math if Template:Mvar is their Euclidean distance matrix. One can assume without loss of generality that $x_1=\mathrm{𝟎}$ (because translating by $-x_1$ preserves distances).

Template:Math theorem This follows from the previous discussion because Template:Mvar is positive semidefinite of rank at most Template:Mvar if and only if it can be decomposed as $G=X^{\mathsf{\text{T}}}X$ where Template:Mvar is a Template:Math matrix. Moreover, the columns of Template:Mvar give a realization in Template:Math. Therefore, any method to decompose Template:Mvar allows to find a realization. The two main approaches are variants of Cholesky decomposition or using spectral decompositions to find the principal square root of Template:Mvar, see Definite matrix#Decomposition.

The statement of theorem distinguishes the first point $x_1$. A more symmetric variant of the same theorem is the following: Template:Math theorem

Other characterizations involve Cayley–Menger determinants. In particular, these allow to show that a symmetric hollow Template:Math matrix is realizable in Template:Math if and only if every Template:Math principal submatrix is. In other words, a semimetric on finitely many points is embedabble isometrically in Template:Math if and only if every Template:Math points are.

In practice, the definiteness or rank conditions may fail due to numerical errors, noise in measurements, or due to the data not coming from actual Euclidean distances. Points that realize optimally similar distances can then be found by semidefinite approximation (and low rank approximation, if desired) using linear algebraic tools such as singular value decomposition or semidefinite programming. This is known as multidimensional scaling. Variants of these methods can also deal with incomplete distance data.

Unlabeled data, that is, a set or multiset of distances not assigned to particular pairs, is much more difficult to deal with. Such data arises, for example, in DNA sequencing (specifically, genome recovery from partial digest) or phase retrieval. Two sets of points are called homometric if they have the same multiset of distances (but are not necessarily related by a rigid transformation). Deciding whether a given multiset of Template:Math distances can be realized in a given dimension Template:Mvar is strongly NP-hard. In one dimension this is known as the turnpike problem; it is an open question whether it can be solved in polynomial time. When the multiset of distances is given with error bars, even the one dimensional case is NP-hard. Nevertheless, practical algorithms exist for many cases, e.g. random points.

Uniqueness of representations

Given a Euclidean distance matrix, the sequence of points that realize it is unique up to rigid transformations – these are isometries of Euclidean space: rotations, reflections, translations, and their compositions.

Template:Math theorem Template:Collapse top Rigid transformations preserve distances so one direction is clear. Suppose the distances $\Vert x_i-x_j\Vert$ and $\Vert y_i-y_j\Vert$ are equal. Without loss of generality we can assume $x_1=y_1=\mathbf{\text{0}}$ by translating the points by $-x_1$ and $-y_1$, respectively. Then the Template:Math Gram matrix of remaining vectors $x_i=x_i-x_1$ is identical to the Gram matrix of vectors $y_i$ (Template:Math). That is, $X^{\mathsf{\text{T}}}X=Y^{\mathsf{\text{T}}}Y$, where Template:Mvar and Template:Mvar are the Template:Math matrices containing the respective vectors as columns. This implies there exists an orthogonal Template:Math matrix Template:Mvar such that Template:Math, see Definite symmetric matrix#Uniqueness up to unitary transformations. Template:Mvar describes an orthogonal transformation of Template:Math (a composition of rotations and reflections, without translations) which maps $x_i$ to $y_i$ (and 0 to 0). The final rigid transformation is described by $T(x)=Q(x-x_1)+y_1$. Template:Collapse bottom

In applications, when distances don't match exactly, Procrustes analysis aims to relate two point sets as close as possible via rigid transformations, usually using singular value decomposition. The ordinary Euclidean case is known as the orthogonal Procrustes problem or Wahba's problem (when observations are weighted to account for varying uncertainties). Examples of applications include determining orientations of satellites, comparing molecule structure (in cheminformatics), protein structure (structural alignment in bioinformatics), or bone structure (statistical shape analysis in biology).

See also

• Adjacency matrix
• Coplanarity
• Distance geometry
• Hollow matrix
• Distance matrix
• Euclidean random matrix
• Classical multidimensional scaling, a visualization technique that approximates an arbitrary dissimilarity matrix by a Euclidean distance matrix
• Cayley–Menger determinant
• Semidefinite embedding

References

• Template:Cite journal
• Template:Cite book
• Template:Cite thesis
• Template:Cite journal
• Template:Cite book