fbpx
Wikipedia

Euclidean distance matrix

In mathematics, a Euclidean distance matrix is an n×n matrix representing the spacing of a set of n points in Euclidean space. For points in k-dimensional space k, the elements of their Euclidean distance matrix A are given by squares of distances between them. That is

where denotes the Euclidean norm on k.

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 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).[1][2]

Properties edit

By the fact that Euclidean distance is a metric, the matrix A has the following properties.

  • All elements on the diagonal of A are zero (i.e. it is a hollow matrix); hence the trace of A is zero.
  • A is symmetric (i.e.  ).
  •   (by the triangle inequality)
  •  

In dimension k, a Euclidean distance matrix has rank less than or equal to k+2. If the points   are in general position, the rank is exactly min(n, k + 2).

Distances can be shrunk by any power to obtain another Euclidean distance matrix. That is, if   is a Euclidean distance matrix, then   is a Euclidean distance matrix for every 0<s<1.[3]

Relation to Gram matrix edit

The Gram matrix of a sequence of points   in k-dimensional space k is the n×n matrix   of their dot products (here a point   is thought of as a vector from 0 to that point):

 , where   is the angle between the vector   and  .

In particular

  is the square of the distance of   from 0.

Thus the Gram matrix describes norms and angles of vectors (from 0 to)  .

Let   be the k×n matrix containing   as columns. Then

 , because   (seeing   as a column vector).

Matrices that can be decomposed as  , that is, Gram matrices of some sequence of vectors (columns of  ), are well understood — these are precisely positive semidefinite matrices.


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

 

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

Conversely, distances   between pairs of n+1 points   determine dot products between n vectors   (1≤in):

 

(this is known as the polarization identity).

Characterizations edit

For a n×n matrix A, a sequence of points   in k-dimensional Euclidean space k is called a realization of A in k if A is their Euclidean distance matrix. One can assume without loss of generality that   (because translating by   preserves distances).

Theorem[4] (Schoenberg criterion,[5] independently shown by Young & Householder[6]) —  A symmetric hollow n×n matrix A with real entries admits a realization in k if and only if the (n-1)×(n-1) matrix   defined by

 

is positive semidefinite and has rank at most k.

This follows from the previous discussion because G is positive semidefinite of rank at most k if and only if it can be decomposed as   where X is a k×n matrix.[7] Moreover, the columns of X give a realization in k. Therefore, any method to decompose G 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 G, see Definite matrix#Decomposition.

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

Corollary[8] —  A symmetric hollow n×n matrix A with real entries admits a realization if and only if A is negative semidefinite on the hyperplane  , that is

  for all   such that  .

Other characterizations involve Cayley–Menger determinants. In particular, these allow to show that a symmetric hollow n×n matrix is realizable in k if and only if every (k+3)×(k+3) principal submatrix is. In other words, a semimetric on finitely many points is embedabble isometrically in k if and only if every k+3 points are.[9]

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 n(n-1)/2 distances can be realized in a given dimension k 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.[10][11][12]

Uniqueness of representations edit

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.[1]

Theorem —  Let   and   be two sequences of points in k-dimensional Euclidean space k. The distances   and   are equal (for all 1≤i,jn) if and only if there is a rigid transformation of k mapping   to   (for all 1≤in).

Proof

Rigid transformations preserve distances so one direction is clear. Suppose the distances   and   are equal. Without loss of generality we can assume   by translating the points by   and  , respectively. Then the (n-1)×(n-1) Gram matrix of remaining vectors   is identical to the Gram matrix of vectors   (2≤in). That is,  , where X and Y are the k×(n-1) matrices containing the respective vectors as columns. This implies there exists an orthogonal k×k matrix Q such that QX=Y, see Definite symmetric matrix#Uniqueness up to unitary transformations. Q describes an orthogonal transformation of k (a composition of rotations and reflections, without translations) which maps   to   (and 0 to 0). The final rigid transformation is described by  .


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 edit

Notes edit

  1. ^ a b Dokmanic et al. (2015)
  2. ^ So (2007)
  3. ^ Maehara, Hiroshi (2013). "Euclidean embeddings of finite metric spaces". Discrete Mathematics. 313 (23): 2848–2856. doi:10.1016/j.disc.2013.08.029. ISSN 0012-365X. Theorem 2.6
  4. ^ So (2007), Theorem 3.3.1, p. 40
  5. ^ Schoenberg, I. J. (1935). "Remarks to Maurice Fréchet's Article "Sur La Definition Axiomatique D'Une Classe D'Espace Distances Vectoriellement Applicable Sur L'Espace De Hilbert"". Annals of Mathematics. 36 (3): 724–732. doi:10.2307/1968654. ISSN 0003-486X. JSTOR 1968654.
  6. ^ Young, Gale; Householder, A. S. (1938-03-01). "Discussion of a set of points in terms of their mutual distances". Psychometrika. 3 (1): 19–22. doi:10.1007/BF02287916. ISSN 1860-0980. S2CID 122400126.
  7. ^ So (2007), Theorem 2.2.1, p. 10
  8. ^ So (2007), Corollary 3.3.3, p. 42
  9. ^ Menger, Karl (1931). "New Foundation of Euclidean Geometry". American Journal of Mathematics. 53 (4): 721–745. doi:10.2307/2371222. JSTOR 2371222.
  10. ^ Lemke, Paul; Skiena, Steven S.; Smith, Warren D. (2003). "Reconstructing Sets From Interpoint Distances". In Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.). Discrete and Computational Geometry. Vol. 25. Berlin, Heidelberg: Springer Berlin Heidelberg. pp. 597–631. doi:10.1007/978-3-642-55566-4_27. ISBN 978-3-642-62442-1.
  11. ^ Huang, Shuai; Dokmanić, Ivan (2021). "Reconstructing Point Sets from Distance Distributions". IEEE Transactions on Signal Processing. 69: 1811–1827. arXiv:1804.02465. doi:10.1109/TSP.2021.3063458. S2CID 4746784.
  12. ^ Jaganathan, Kishore; Hassibi, Babak (2012). "Reconstruction of Integers from Pairwise Distances". arXiv:1212.2386 [cs.DM].

References edit

  • Dokmanic, Ivan; Parhizkar, Reza; Ranieri, Juri; Vetterli, Martin (2015). "Euclidean Distance Matrices: Essential theory, algorithms, and applications". IEEE Signal Processing Magazine. 32 (6): 12–30. arXiv:1502.07541. doi:10.1109/MSP.2015.2398954. ISSN 1558-0792. S2CID 8603398.
  • James E. Gentle (2007). Matrix Algebra: Theory, Computations, and Applications in Statistics. Springer-Verlag. p. 299. ISBN 978-0-387-70872-0.
  • So, Anthony Man-Cho (2007). A Semidefinite Programming Approach to the Graph Realization Problem: Theory, Applications and Extensions (PDF) (PhD).
  • Liberti, Leo; Lavor, Carlile; Maculan, Nelson; Mucherino, Antonio (2014). "Euclidean Distance Geometry and Applications". SIAM Review. 56 (1): 3–69. arXiv:1205.0349. doi:10.1137/120875909. ISSN 0036-1445. S2CID 15472897.
  • Alfakih, Abdo Y. (2018). Euclidean Distance Matrices and Their Applications in Rigidity Theory. Cham: Springer International Publishing. doi:10.1007/978-3-319-97846-8. ISBN 978-3-319-97845-1.

euclidean, distance, matrix, mathematics, matrix, representing, spacing, points, euclidean, space, points, displaystyle, ldots, dimensional, space, ℝk, elements, their, given, squares, distances, between, them, that, dij2, displaystyle, begin, aligned, lvert, . In mathematics a Euclidean distance matrix is an n n matrix representing the spacing of a set of n points in Euclidean space For points x1 x2 xn displaystyle x 1 x 2 ldots x n in k dimensional space ℝk the elements of their Euclidean distance matrix A are given by squares of distances between them That is A aij aij dij2 xi xj 2 displaystyle begin aligned A amp a ij a ij amp d ij 2 lVert x i x j rVert 2 end aligned where displaystyle cdot denotes the Euclidean norm on ℝk A 0d122d132 d1n2d2120d232 d2n2d312d3220 d3n2 dn12dn22dn32 0 displaystyle A begin bmatrix 0 amp d 12 2 amp d 13 2 amp dots amp d 1n 2 d 21 2 amp 0 amp d 23 2 amp dots amp d 2n 2 d 31 2 amp d 32 2 amp 0 amp dots amp d 3n 2 vdots amp vdots amp vdots amp ddots amp vdots amp d n1 2 amp d n2 2 amp d n3 2 amp dots amp 0 end bmatrix 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 x1 x2 xn displaystyle x 1 x 2 ldots 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 1 2 Contents 1 Properties 2 Relation to Gram matrix 3 Characterizations 4 Uniqueness of representations 5 See also 6 Notes 7 ReferencesProperties editBy the fact that Euclidean distance is a metric the matrix A has the following properties All elements on the diagonal of A are zero i e it is a hollow matrix hence the trace of A is zero A is symmetric i e aij aji displaystyle a ij a ji nbsp aij aik akj displaystyle sqrt a ij leq sqrt a ik sqrt a kj nbsp by the triangle inequality aij 0 displaystyle a ij geq 0 nbsp In dimension k a Euclidean distance matrix has rank less than or equal to k 2 If the points x1 x2 xn displaystyle x 1 x 2 ldots x n nbsp are in general position the rank is exactly min n k 2 Distances can be shrunk by any power to obtain another Euclidean distance matrix That is if A aij displaystyle A a ij nbsp is a Euclidean distance matrix then aijs displaystyle a ij s nbsp is a Euclidean distance matrix for every 0 lt s lt 1 3 Relation to Gram matrix editThe Gram matrix of a sequence of points x1 x2 xn displaystyle x 1 x 2 ldots x n nbsp in k dimensional space ℝk is the n n matrix G gij displaystyle G g ij nbsp of their dot products here a point xi displaystyle x i nbsp is thought of as a vector from 0 to that point gij xi xj xi xj cos 8 displaystyle g ij x i cdot x j x i x j cos theta nbsp where 8 displaystyle theta nbsp is the angle between the vector xi displaystyle x i nbsp and xj displaystyle x j nbsp In particular gii xi 2 displaystyle g ii x i 2 nbsp is the square of the distance of xi displaystyle x i nbsp from 0 Thus the Gram matrix describes norms and angles of vectors from 0 to x1 x2 xn displaystyle x 1 x 2 ldots x n nbsp Let X displaystyle X nbsp be the k n matrix containing x1 x2 xn displaystyle x 1 x 2 ldots x n nbsp as columns Then G XTX displaystyle G X textsf T X nbsp because gij xiTxj displaystyle g ij x i textsf T x j nbsp seeing xi displaystyle x i nbsp as a column vector Matrices that can be decomposed as XTX displaystyle X textsf T X nbsp that is Gram matrices of some sequence of vectors columns of X displaystyle X nbsp are well understood these are precisely positive semidefinite matrices To relate the Euclidean distance matrix to the Gram matrix observe that dij2 xi xj 2 xi xj T xi xj xiTxi 2xiTxj xjTxj gii 2gij gjj displaystyle d ij 2 x i x j 2 x i x j textsf T x i x j x i textsf T x i 2x i textsf T x j x j textsf T x j g ii 2g ij g jj nbsp That is the norms and angles determine the distances Note that the Gram matrix contains additional information distances from 0 Conversely distances dij displaystyle d ij nbsp between pairs of n 1 points x0 x1 xn displaystyle x 0 x 1 ldots x n nbsp determine dot products between n vectors xi x0 displaystyle x i x 0 nbsp 1 i n gij xi x0 xj x0 12 xi x0 2 xj x0 2 xi xj 2 12 d0i2 d0j2 dij2 displaystyle g ij x i x 0 cdot x j x 0 frac 1 2 left x i x 0 2 x j x 0 2 x i x j 2 right frac 1 2 d 0i 2 d 0j 2 d ij 2 nbsp this is known as the polarization identity Characterizations editFor a n n matrix A a sequence of points x1 x2 xn displaystyle x 1 x 2 ldots x n nbsp in k dimensional Euclidean space ℝk is called a realization of A in ℝk if A is their Euclidean distance matrix One can assume without loss of generality that x1 0 displaystyle x 1 mathbf 0 nbsp because translating by x1 displaystyle x 1 nbsp preserves distances Theorem 4 Schoenberg criterion 5 independently shown by Young amp Householder 6 A symmetric hollow n n matrix A with real entries admits a realization in ℝk if and only if the n 1 n 1 matrix G gij 2 i j n displaystyle G g ij 2 leq i j leq n nbsp defined by gij 12 a1i2 a1j2 aij2 displaystyle g ij frac 1 2 a 1i 2 a 1j 2 a ij 2 nbsp is positive semidefinite and has rank at most k This follows from the previous discussion because G is positive semidefinite of rank at most k if and only if it can be decomposed as G XTX displaystyle G X textsf T X nbsp where X is a k n matrix 7 Moreover the columns of X give a realization in ℝk Therefore any method to decompose G 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 G see Definite matrix Decomposition The statement of theorem distinguishes the first point x1 displaystyle x 1 nbsp A more symmetric variant of the same theorem is the following Corollary 8 A symmetric hollow n n matrix A with real entries admits a realization if and only if A is negative semidefinite on the hyperplane H v Rn eTv 0 displaystyle H v in mathbf R n colon e textsf T v 0 nbsp that is vTAv 0 displaystyle v textsf T Av leq 0 nbsp for all v Rn displaystyle v in mathbf R n nbsp such that i 1nvi 0 displaystyle textstyle sum i 1 n v i 0 nbsp Other characterizations involve Cayley Menger determinants In particular these allow to show that a symmetric hollow n n matrix is realizable in ℝk if and only if every k 3 k 3 principal submatrix is In other words a semimetric on finitely many points is embedabble isometrically in ℝk if and only if every k 3 points are 9 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 n n 1 2 distances can be realized in a given dimension k 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 10 11 12 Uniqueness of representations editGiven 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 1 Theorem Let x1 x2 xn displaystyle x 1 x 2 ldots x n nbsp and y1 y2 yn displaystyle y 1 y 2 ldots y n nbsp be two sequences of points in k dimensional Euclidean space ℝk The distances xi xj displaystyle x i x j nbsp and yi yj displaystyle y i y j nbsp are equal for all 1 i j n if and only if there is a rigid transformation of ℝk mapping xi displaystyle x i nbsp to yi displaystyle y i nbsp for all 1 i n ProofRigid transformations preserve distances so one direction is clear Suppose the distances xi xj displaystyle x i x j nbsp and yi yj displaystyle y i y j nbsp are equal Without loss of generality we can assume x1 y1 0 displaystyle x 1 y 1 textbf 0 nbsp by translating the points by x1 displaystyle x 1 nbsp and y1 displaystyle y 1 nbsp respectively Then the n 1 n 1 Gram matrix of remaining vectors xi xi x1 displaystyle x i x i x 1 nbsp is identical to the Gram matrix of vectors yi displaystyle y i nbsp 2 i n That is XTX YTY displaystyle X textsf T X Y textsf T Y nbsp where X and Y are the k n 1 matrices containing the respective vectors as columns This implies there exists an orthogonal k k matrix Q such that QX Y see Definite symmetric matrix Uniqueness up to unitary transformations Q describes an orthogonal transformation of ℝk a composition of rotations and reflections without translations which maps xi displaystyle x i nbsp to yi displaystyle y i nbsp and 0 to 0 The final rigid transformation is described by T x Q x x1 y1 displaystyle T x Q x x 1 y 1 nbsp 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 editAdjacency 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 embeddingNotes edit a b Dokmanic et al 2015 So 2007 Maehara Hiroshi 2013 Euclidean embeddings of finite metric spaces Discrete Mathematics 313 23 2848 2856 doi 10 1016 j disc 2013 08 029 ISSN 0012 365X Theorem 2 6 So 2007 Theorem 3 3 1 p 40 Schoenberg I J 1935 Remarks to Maurice Frechet s Article Sur La Definition Axiomatique D Une Classe D Espace Distances Vectoriellement Applicable Sur L Espace De Hilbert Annals of Mathematics 36 3 724 732 doi 10 2307 1968654 ISSN 0003 486X JSTOR 1968654 Young Gale Householder A S 1938 03 01 Discussion of a set of points in terms of their mutual distances Psychometrika 3 1 19 22 doi 10 1007 BF02287916 ISSN 1860 0980 S2CID 122400126 So 2007 Theorem 2 2 1 p 10 So 2007 Corollary 3 3 3 p 42 Menger Karl 1931 New Foundation of Euclidean Geometry American Journal of Mathematics 53 4 721 745 doi 10 2307 2371222 JSTOR 2371222 Lemke Paul Skiena Steven S Smith Warren D 2003 Reconstructing Sets From Interpoint Distances In Aronov Boris Basu Saugata Pach Janos Sharir Micha eds Discrete and Computational Geometry Vol 25 Berlin Heidelberg Springer Berlin Heidelberg pp 597 631 doi 10 1007 978 3 642 55566 4 27 ISBN 978 3 642 62442 1 Huang Shuai Dokmanic Ivan 2021 Reconstructing Point Sets from Distance Distributions IEEE Transactions on Signal Processing 69 1811 1827 arXiv 1804 02465 doi 10 1109 TSP 2021 3063458 S2CID 4746784 Jaganathan Kishore Hassibi Babak 2012 Reconstruction of Integers from Pairwise Distances arXiv 1212 2386 cs DM References editDokmanic Ivan Parhizkar Reza Ranieri Juri Vetterli Martin 2015 Euclidean Distance Matrices Essential theory algorithms and applications IEEE Signal Processing Magazine 32 6 12 30 arXiv 1502 07541 doi 10 1109 MSP 2015 2398954 ISSN 1558 0792 S2CID 8603398 James E Gentle 2007 Matrix Algebra Theory Computations and Applications in Statistics Springer Verlag p 299 ISBN 978 0 387 70872 0 So Anthony Man Cho 2007 A Semidefinite Programming Approach to the Graph Realization Problem Theory Applications and Extensions PDF PhD Liberti Leo Lavor Carlile Maculan Nelson Mucherino Antonio 2014 Euclidean Distance Geometry and Applications SIAM Review 56 1 3 69 arXiv 1205 0349 doi 10 1137 120875909 ISSN 0036 1445 S2CID 15472897 Alfakih Abdo Y 2018 Euclidean Distance Matrices and Their Applications in Rigidity Theory Cham Springer International Publishing doi 10 1007 978 3 319 97846 8 ISBN 978 3 319 97845 1 Retrieved from https en wikipedia org w index php title Euclidean distance matrix amp oldid 1193296545, wikipedia, wiki, book, books, library,

article

, read, download, free, free download, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, picture, music, song, movie, book, game, games.