Euclidean distance matrix

rdf:langString Euclidean distance matrix

rdf:langString 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).