Editing Distance geometry (section)

== Introduction and definitions ==
The concepts of distance geometry will first be explained by describing two particular problems.[[File:Hyperbolic_Navigation.svg|thumb|219x219px|Problem of hyperbolic navigation]]

=== First problem: [[hyperbolic navigation]] ===
Consider three ground radio stations A, B, C, whose locations are known. A radio receiver is at an unknown location. The times it takes for a radio signal to travel from the stations to the receiver, <math> t_A,t_B,t_C </math>, are unknown, but the time differences, <math>t_A-t_B </math> and <math>t_A-t_C </math>, are known. From them, one knows the distance differences <math>c(t_A-t_B) </math> and <math>c(t_A-t_C) </math>, from which the position of the receiver can be found.

=== Second problem: [[Dimensionality reduction|dimension reduction]]===
In [[data analysis]], one is often given a list of data represented as vectors <math>\mathbf{v} = (x_1, \ldots, x_n)\in \mathbb{R}^n</math>, and one needs to find out whether they lie within a low-dimensional affine subspace. A low-dimensional representation of data has many advantages, such as saving storage space, computation time, and giving better insight into data.

=== Definitions ===
Now we formalize some definitions that naturally arise from considering our problems.

==== Semimetric space ====
Given a list of points on <math>R = \{P_0, \ldots, P_n\}</math>, <math>n \ge 0</math>, we can arbitrarily specify the distances between pairs of points by a list of  <math>d_{ij}> 0</math>, <math>0 \le i < j \le n</math>. This defines a [[Semi metric space|semimetric space]]: a metric space without [[triangle inequality]].

Explicitly, we define a semimetric space as a nonempty set <math>R</math> equipped with a semimetric <math>d: R\times R \to [0, \infty)</math> such that, for all <math>x, y\in R</math>,

# Positivity: <math>d(x, y) = 0</math> &nbsp; if and only if &nbsp;<math>x = y</math>.
# Symmetry: <math>d(x, y) = d(y, x)</math>.

Any metric space is [[Argumentum a fortiori|''a fortiori'']] a semimetric space. In particular, <math>\mathbb{R}^k</math>, the <math>k</math>-dimensional [[Euclidean space]], is the [[Canonical form|canonical]] metric space in distance geometry.

The triangle inequality is omitted in the definition, because we do not want to enforce more constraints on the distances <math>d_{ij}</math> than the mere requirement that they be positive.

In practice, semimetric spaces naturally arise from inaccurate measurements. For example, given three points <math>A, B, C</math> on a line, with <math>d_{AB} = 1, d_{BC} = 1, d_{AC} = 2</math>, an inaccurate measurement could give <math>d_{AB} = 0.99, d_{BC} = 0.98, d_{AC} = 2.00</math>, violating the triangle inequality.

==== Isometric embedding ====
Given two semimetric spaces, <math>(R, d), (R', d')</math>, an [[Isometry|isometric embedding]] from <math>R</math> to <math>R'</math> is a map <math>f: R \to R'</math> that preserves the semimetric, that is, for all <math>x, y\in R</math>, <math>d(x, y) = d'(f(x), f(y))</math>.

For example, given the finite semimetric space <math>(R, d)</math> defined above, an isometric embedding from <math>R</math> to <math>\mathbb{R}^k</math> is defined by points <math display="inline">A_0, A_1,\ldots, A_n \in \mathbb R^k</math>, such that <math>d(A_i, A_j) = d_{ij}</math> for all <math>0 \le i < j \le n</math>.

==== Affine independence ====
Given the points <math display="inline">A_0, A_1,\ldots, A_n \in \mathbb R^k</math>, they are defined to be [[Affine independence|affinely independent]], [[iff]] they cannot fit inside a single <math>
l</math>-dimensional affine subspace of <math> \mathbb{R}^k</math>, for any <math> \ell < n</math>, iff the <math>n</math>''-''[[simplex]] they span, <math>v_n</math>, has positive <math>n</math>-volume, that is, <math>\operatorname{Vol}_n(v_n) > 0</math>.

In general, when <math>k\ge n </math>, they are affinely independent, since a [[Generic property|generic]] ''n''-simplex is nondegenerate. For example, 3 points in the plane, in general, are not collinear, because the triangle they span does not degenerate into a line segment. Similarly, 4 points in space, in general, are not coplanar, because the tetrahedron they span does not degenerate into a flat triangle.

When <math> n > k</math>, they must be affinely dependent. This can be seen by noting that any <math>n</math>-simplex that can fit inside <math>\mathbb{R}^k</math> must be "flat".