Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Euclidean distance matrix
Summary
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 Rk, the elements of their Euclidean distance matrix A are given by squares of distances between them.
That is
where denotes the Euclidean norm on Rk.
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).
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.