The subject of this talk is motivated by a fundamental result of Johnson and Lindenstrauss which says the following: Let $0<\varepsilon<1$ and $D\geq 1$. Let us be given a set $E$ of $k\geq 1$ points in $\mathbb R^D$ and a number $D'\geq 4(\varepsilon^2/2-\varepsilon^3/3)^{-1}\log k$. Then, there exists a Lipchitz function $f:\mathbb R^D\to \mathbb R^{D'}$ such that

\[

(1-\varepsilon)\leq\frac{|f(u)-f(v)|^2}{|u-v|^2}\leq (1+\varepsilon)

\]

for all $u,v\in E$. This says that any $k\geq 1$ point subset of Euclidean space can be embedded into $n=O(\log k/\varepsilon^2)$ dimensions without distorting the distances between any pair of points by more than a factor of $(1\pm \varepsilon)$, for any $0<\varepsilon<1$.

Besides being of mathematical interest, the result above has important uses in several applied computer vision subjects such as bi-lipchitz embeddings of graphs into normed spaces, compressed sensing, manifold learning and dimensionality reduction. For example, data stored and manipulated on computers, including text and images, as is well known, may be represented as points in a high-dimensional space. However, the essential algorithms for working with such data tend to become bogged down very quickly as dimension increases. This phenomenon is often referred to as the "`curse of dimensionality"' It is therefore desirable to reduce the dimensionality of the data in a way that preserves its relevant structure.

Throughout this talk, we work in $\mathbb R^D$ where $D\geq 1$ is fixed.

We are interested in the following question. Let $\varepsilon>0$ and suppose we are given sets of distinct labeled points of size $k$, $E:=y_1,...,y_k$ and $E':=z_1,...,z_k$ in $\mathbb R^{D}$. Assume that $|y_i|=1$ for all $i$ and that the points are distorted by a aprori fixed amount, ie for all $i,j$

\[

(1-\varepsilon)\leq \frac{|y_i-y_j|}{|z_i-z_j|}\leq (1+\varepsilon).

\]

Do there exist rigid motions $\Phi$ which approximately or exactly align the the two sets of labeled points? As it turns out, the answer to this question leads us to prove several new theoretical results on the alignment of labeled data in euclidean space via euclidean motions and extensions of diffeomorphisms with small distortion.

We will also discuss how our results may be used in numerous applications in medical and hyperspectral imaging and also how they are related to Whitneys interpolation extension problems.