%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{times}
\usepackage{amssymb}
\usepackage{latexsym}
%\usepackage{eufrak}
\usepackage[mathscr]{euscript}

%\newcommand\C{\mathbb C}
\newcommand\R{\mathbb R}
\newcommand\Z{\mathbb Z}


%\newcommand\dbar{\bar\partial}
%\newcommand\bd{\partial}

\newcommand\qed{\hfill $\square$}

\newcommand\commentout[1]{}

\newcounter{num}

%\renewcommand{\baselinestretch}{1.0}

\title{Graph approximations to geodesics on embedded manifolds}
\author{Mira Bernstein, Vin de Silva,\\John C. Langford, Joshua B. Tenenbaum}

\renewcommand{\baselinestretch}{0.94}

\begin{document}
\maketitle

\abstract{We analyze the problem of extracting a low-dimensional
manifold from a high dimensional space and (incidentally) prove
low-distortion low-dimension embedding by the Isomap algorithm
\cite{isomap} when 1) samples form a cover on an embedded
low-dimensional Euclidean manifold, 2) the embedded manifold has a
large branch separation, and 3) a large radius of curvature.}

\section{Introduction}

Given a set of points in a high dimensional space, how can we extract
a mapping from the high dimensional space to a low dimensional space
which preserves the relative geometry of the points?  In other words,
how can we extract a low-distortion low-dimensional representation of
points?

Some special case algorithms for extracting one or two dimensional
surfaces from two or three dimensional spaces have been analyzed
\cite{crust}, \cite{pcrust} with sufficient conditions dependent upon
a notion of local feature size.  The analysis here covers the more
general case of extracting a low dimensional space from a high
dimensional space.

This problem has been studied and various approaches exist.  The
approaches can be roughly sorted by strength and types of assumptions
which are necessary in order to successfully extract a low-distortion
low-dimensional representation.

On one end of the spectrum are the assumption free approaches of which
the Johnson-Lindenstrauss lemma \cite{JL} is typical.  The implication
of this lemma is that $m$ points in a high dimensional Euclidean space
can be mapped into an $O(\log m / \epsilon^2)$ Euclidean space in such
a way that distances are distorted by at most a factor of $1 \pm
\epsilon$.  This approach is general and can be applied to other
metrics and other notions of optimality.  See \cite{Piotyr} for a
recent survey.

The principle inadequacy of this assumption-free approach is that
$O(\log m / \epsilon^2)$ is simply too large for many practical uses.
In many cases we really do have reason to believe that some
low-dimensional structure exists and want to extract.  Successful
extraction is important for human understanding of the dataset and
because many geometric algorithms apply to only 2 or 3 dimensional
spaces.

A much more restrictive notion comes from principle component analysis
(PCA) which can extract a low-distortion low-dimensional
representation when the points are on (or near) a low dimensional
affine subspace in the high dimensional space.  The largest drawback
of PCA is that the assumption that there exists a low dimensional
affine subspace is too restrictive.  In particular, there are many
situations where the points might lie on a low dimensional manifold
which is \emph{nonlinearly} embedded in the high dimensional space.  

Problems of nonlinear dimensionality reduction arise in many
applications with natural signals, including computer vision, speech
recognition, astrophysics, climatology, and genetics. Consider the
following high-dimensional spaces of visual images (represented as
vectors of raw pixel brightness values):
\begin{enumerate}
\item Viewpoints of a scene. 
\item images of hand written letters. 
\item images of a hand in various positions.
\end{enumerate}
For each of these examples, a low dimensional nonlinearly embedded
manifold contains the points.  In the first example, the
dimensionality is $3$ (left-right/up-down/near-far) and there may be
an extra $3$ dimensions due to rotations at a fixed point of view.
The intrinsic dimensionality of hand-written letters and hand
positions is not so easy to specify a priori, but they are still
characterizable as contained in a $d$-dimensional manifold which is
nonlinearly embedded within $\R^n$ where $n$ is the number of pixels
in an image and $d \ll n$.  PCA will inherently perform poorly on
these examples because of the nonlinearity.  Assumption-free
approaches will not perform well because $O(\log m / \epsilon^2)$ is
often similar to $n$ in practice which implies that little complexity
is removed.

There are two general nonlinear manifold extraction algorithms which
have recently been proposed, Isomap \cite{isomap} and LLE \cite{LLE}.
Both of these algorithms behave well on datasets of the above form.
It is not clear when and how these algorithms will fail.  The
assumption free results imply they \emph{must} fail in some cases.
In what cases will these algorithms work?  Where will they fail?

An ideal result would have the form: ``Natural assumption A and B are
necessary and sufficient conditions for manifold extraction up to
error tolerance $\epsilon$.'' We have achieved half of this:
sufficient conditions for extraction with the Isomap algorithm given
some natural assumptions.  A similar result is not known for the LLE
algorithm.

Isomap works in 3 simple stages starting with a set of points in
$\R^n$ (for $n$ typically large):
\begin{enumerate}
\item Construct a graph $G$ where every point is connected to every
nearby\footnote{The exact algorithm used was either ``within some
$\epsilon$'' or ``$K$ nearest neighbors'' in the high dimensional
Euclidean space.} point.
\item Compute all points shortest path on the graph $G$.
\item Use MDS (MultiDimensional Scaling) to embed this graph into some
$\R^d$ for $d$ small.  
\end{enumerate}
The output of Isomap is an embedding of the input points in $\R^d$ for
$d$ small (typically $2$, $3$, or $4$).  The essential goal of this
paper is analyzing when the Isomap algorithm works.  Roughly, we show
that if:
\begin{enumerate}
\item The input points have a small cover scale (defined later) for a
Euclidean manifold $M$,
\item The radius of curvature for the embedding of the manifold $M$
into $\R^d$ is not too small,
\item The branch separation (distance between different ``arms'' of
the manifold) is large enough
\end{enumerate}
then the distance between two points in $\R^d$ will be near to the
\emph{geodesic} distance (in $M$).  As the scale of the covering
approaches $0$, the distortion goes to $0$.  

The paper is organized into $4$ sections.
\begin{itemize}
\item In Section \ref{sec-defn} we state formal definitions.
\item In Section \ref{sec-upper} we show half of a two-step
convergence.
\item In Section \ref{sec-lower} we show the other half of two-step
convergence and state the main theorem.
\item In Section \ref{sec-iso} we discuss the relationship of the
results here with the Isomap algorithm.
\end{itemize}

\section{Finite samples on submanifolds}
\label{sec-defn}
Let $M = M^d$ be a compact $d$-dimensional
smooth submanifold of the Euclidean space $\R^n$.
Boundary and boundary corners are permitted, so for
instance $M$ may be a $d$-dimensional cube.

The natural Riemannian structure on $M$ (induced
from the Euclidean metric on $\R^n$) gives rise to a
manifold metric $d_M$ defined by:
\[
d_M(x,y) = \inf_\gamma \{\textrm{length}(\gamma)\}
\]
where $\gamma$ varies over the set of (piecewise) smooth arcs
connecting $x$ to $y$ in $M$.
Note that $d_M(x,y)$ is generally
different from the Euclidean distance $\|x-y\|$.

Let $\{x_i\} \subset M$ be a finite set, whose
elements we will refer to as ``data points'' or
``sample points''. These
points may be chosen randomly, or obtained in some
other manner. The Isomap algorithm attempts to
recover the manifold distances $d_M(x_i,x_j)$, given only the
data points $\{x_i\} \subset \R^n$. Of course,
this can only be done approximately.

The construction makes use of a graph $G$ on the data
points. Given such a graph we can define two further
metrics, just on the set of data points. Let $x,y$
belong to the set $\{x_i\}$. We define:
%
\begin{eqnarray*}
d_G(x,y)&=& \min_P
\left(
	\|x_0 - x_1\| + \dots + \|x_{p-1}-x_p\|
\right)
\\
d_S(x,y)&=& \min_P \left( d_M(x_0,x_1) + \dots + d_M(x_{p-1},x_p) \right)
\end{eqnarray*}
%
where $P = (x_0, \dots, x_p)$ varies over all paths along the edges of
$G$ connecting $x$ ($ \equiv x_0$) to $y$ ($\equiv x_p$).

Given the data points and graph $G$, one can compute $d_G$ without
knowledge of the manifold $M$. This is a key stage in the Isomap
algorithm. Since the real goal is to estimate $d_M$, we must show that
$d_G$ is a good approximation to $d_M$, under favorable circumstances.

The metric $d_S$ is an intermediate approximation. The proof that $d_G
\approx d_M$ falls naturally into two parts: $d_M \approx d_S$ and
$d_S \approx d_G$.

{\bf Proposition 1.}
We have the inequalities:
\begin{eqnarray*}
d_M(x,y) &\leq& d_S(x,y)
\\
d_G(x,y) &\leq& d_S(x,y)
\end{eqnarray*}

{\bf Proof.}  The first expression is just the triangle inequality for
the metric $d_M$. The second inequality holds because for the path $P
= x_0, \dots, x_p$ achieving the minimum in the definition of $d_S$,
we have:
\[d_S(x,y) \geq \|x_0 - x_1\| + \dots + \|x_{p-1}-x_p\| \geq d_G(x,y) \]
since $ d_M (x_i, x_{i+1}) \geq \| x_i - x_{i+1}\| $ for the left
inequality, and the right inequality follows by the minimum in
$d_G$. \qed

The main task will be to show that $d_S$ is not too much bigger than
$d_M$, and that $d_G$ is not too much smaller than $d_S$.  

\section{The sampling condition}
\label{sec-upper}

There are simple conditions on the data set $\{x_i\}$ and the graph
$G$ which guarantee that $d_S$ is a good approximation to $d_M$.

One parameter of the proof is the covering scale of the samples,
$\{x_i\}$.
\[ C(d_M, \{x_i\}) = \max_{x \in M} \min_{\{x_i\}} d_M(x_i,x) \]  
The covering scale can be thought of as an inversion of the covering
number often used in learning theory in the context of VC bounds
\cite{Vapnik}.

{\bf Theorem 2.}  {\it For all $ \epsilon>0$ and $\delta > 0$, with
$4\delta < \epsilon$.  If:
\begin{enumerate}
	\item
	The graph $G$ contains all edges $xy$ for which
	$d_M(x,y) \leq \epsilon$.

	\item 
	The covering scale is small, $C(d_M, \{x_i\}) \leq \delta$
\end{enumerate}
Then for all pairs of data points $x,y$ we have
\[
d_M(x,y)
	\leq d_S(x,y)
	\leq (1+4\delta/\epsilon) d_M(x,y)
\]
}
{\bf Proof.~}
Let $\gamma$ be any piecewise-smooth arc connecting
$x$ to $y$, with length $\ell = \textrm{length}(\gamma)$. 
We will find a path from $x$ to $y$ along
edges of $G$ whose length $d_M(x_0,x_1) + \dots + d_M(x_{p-1},x_p)$
is less than $(1+4\delta/\epsilon)\ell$.
The right-hand inequality will follow upon taking the infimum
over $\gamma$.

If $\ell \leq \epsilon-2\delta$ then $x$ and $y$ are connected by an edge,
which we can use as our path.

If $\ell > \epsilon - 2\delta$ we can write 
$\ell = \ell_0 + (\ell_1 + \ell_1 + \dots + \ell_1) + \ell_0$,
where $\ell_1 = \epsilon - 2\delta$ and
$\epsilon - 2\delta \geq \ell_0 \geq (\epsilon - 2\delta)/2$.
(There may be no $\ell_1$ terms if $\ell$ is small.)

Now cut up the arc $\gamma$ into pieces in accordance with
this decomposition of its length $\ell$. This gives us a sequence
of points $\gamma_0 = x, \gamma_1, \dots , \gamma_p = y$ along
$\gamma$, which divide the length of $\gamma$ as indicated.

Each point $\gamma_i$ (for $i = 1, \dots, p-1$) lies within distance
$\delta$ of a sample point $x_i$. We claim that the path
$x x_1 x_2 \dots x_{p-1} y$ satisfies our requirements.
%Certainly each edge has length at most $\epsilon$; indeed
We estimate the length of each edge as follows:
\begin{eqnarray*}
d_M(x_i,x_{i+1}) &\leq& d_M(x_i,\gamma_i) 
			+ d_M(\gamma_i,\gamma_{i+1})
			+ d_M(\gamma_{i+1},x_{i+1})
\\
&\leq&	\delta + \ell_1 + \delta
\\
&=& \epsilon\\
&=& \ell_1\epsilon/(\epsilon-2\delta)
\end{eqnarray*}

and similarly:
\begin{eqnarray*}
d_M(x,x_1) &\leq& \ell_0\epsilon/(\epsilon-2\delta)
\\
d_M(x_{p-1},y) &\leq& \ell_0\epsilon/(\epsilon-2\delta)
\end{eqnarray*}

Since $\ell_0\epsilon/(\epsilon-2\delta) \leq \epsilon$, we find
that each edge has length at most $\epsilon$ and so belongs to $G$.
Adding the inequalities, we obtain:
\begin{eqnarray*}
d_M(x_0,x_1) + \dots + d_M(x_{p-1},x_p) &\leq&
			\ell\epsilon/(\epsilon-2\delta)
\\
&<& \ell(1+4\delta/\epsilon)
\end{eqnarray*}
The last step makes use of the general fact that $1/(1-t) < 1 +2t$
when $0<t<1/2$. This completes the proof.  \qed

It follows that the distance $d_S$ can approximates $d_M$ arbitrarily
well, as the neighborhood range $\epsilon$ and the covering scale
approach zero.

\section{Parameters of the manifold embedding}
\label{sec-lower}
The assertion that $d_S \approx d_G$ requires us to
consider various parameters of the embedded manifold.

The \emph{minimum radius of curvature} $r_0 = r_0(M)$ is defined
by:
\[
\frac{1}{r_0} = \max_{\gamma,t}
\left\{ \|\ddot\gamma(t)\| \right\}
\]
where $\gamma$ varies over all unit-speed geodesics in $M$ and $t$
is in the domain $D$ of $\gamma$. The second derivative is computed
by regarding $\gamma$ as a map $D \rightarrow \R^n$.

Any Euclidean sphere of radius $r_0$ has minimum radius of curvature
equal to $r_0$; in particular this is true of circles of radius $r_0$
contained in some 2-dimensional plane. Intuitively, geodesics in $M$
curl around ``less tightly'' than circles of radius less than $r_0(M)$.

The \emph{minimum branch separation} $s_0 = s_0(M)$ is defined to
be the largest positive number for which $\|x-y\| < s_0$ implies
$d_M(x,y) \leq \pi r_0$, for $x,y \in M$.

The existence of $r_0$ and $s_0$ is guaranteed by the compactness
of $M$. We now make use of these quantities.

{\bf Lemma 3.}
{\it
If $\gamma$ is a geodesic in $M$ connecting
points $x$ and $y$, and if
$\ell = \mathrm{length}(\gamma) \leq \pi r_0$
then:
\[
2r_0\sin(\ell/2r_0) \leq \| x - y \| \leq \ell
\]
}

The right-hand inequality is just the fact that the line segment
between $x$ and $y$ is the shortest arc connecting $x$ to $y$.  The
proof of the left-hand inequality is omitted, but see \cite{isotech}
for the proof.  Equality on the left is achieved in the case where
$\gamma$ is an arc of a circle of radius $r_0$. Thus Lemma~3
crystallizes the notion that geodesics in $M$ curl around less tightly
than circles of radius $r_0$.

Using the fact that $\sin(t) \geq t - t^3/6$ for $t \geq 0$,
we can write down a weakened form of Lemma~3:
\[
(1 - \ell^2/24r_0^2)\ell \leq \|x-y\| \leq \ell
\]
We make this change purely for cosmetic purposes; it
makes it easy to see that when $\ell$ is small,
all three terms are approximately equal.

There is also the ``first-order'' weakening
\[
(2/\pi)\ell \leq \|x-y\| \leq \ell,
\]
which is valid in the range $\ell \leq \pi r_0$.

We now have the main ingredients required to show
$d_G \approx d_S$. 

{\bf Corollary 4} {\it For all $\lambda>0$, if points $x,y$ in $M$
satisfy:
\begin{eqnarray*}
\| x  - y \| &<& s_0	\\
\| x - y \| &\leq& (2/\pi)r_0\sqrt{24\lambda}
\end{eqnarray*}
and $x,y$ is connected by a geodesic of length $d_M(x,y)$,
then
\[
(1-\lambda)d_M(x,y)
	\leq \| x - y \| 
	\leq d_M(x,y)
\]
}

{\bf Proof.}  The first assumption implies that $\ell = d_M(x,y) \leq
\pi r_0$.  Since we assume that this distance is represented by a
geodesic arc, we can apply the weak form of Lemma~3. First of all we
have
\[
\ell \leq (\pi/2)\| x_i - x_{i+1} \|
	\leq r_0 \sqrt{24 \lambda},
\]
using the first-order approximation. It follows that
$1-\lambda \leq 1 - \ell^2/24 r_0^2$
and so Lemma~3 implies the desired result.
\qed

Corollary~4 relates to the crucial inequality $(1-\lambda)d_S \leq d_G
\leq d_S$, since $d_S$ and $d_G$ are defined in terms of lengths of
geodesics and lengths of straight line segments,
respectively. However, one must be careful to ensure that all relevant
graph edges have a corresponding geodesic arc.

This last assumption is not always valid. If $M$ is a convex
domain in $\R^n$ with a hole punched out of its interior, then
points on opposite sides of the hole are not connected
by a shortest geodesic.

It is useful to have a criterion to identify when this assumption
is valid. We say that $M$ is \emph{geodesically convex} if any
two points $x,y$ in $M$ are connected by a geodesic of
length $d_M(x,y)$.

{\bf Examples.}
Convex domains in $\R^n$ are geodesically
convex, as are compact Riemannian manifolds without
boundary. In general, if $M$ is a
compact Riemannian manifold, then $M$ is
geodesically convex if and only if its boundary is convex,
in an appropriate sense.

This notion can be put to use in theorems of the following
kind.

{\bf Main Theorem A.}  {\it Let $M$ be a compact submanifold of $\R^n$
with minimum radius of curvature, $r_0$ and branch separation $s_0$.
Let $\{x_i\}$ be a finite set of data points in $M$.  Let $G$ be a
graph with vertices $\{x_i\}$, and $0 < \lambda_1, \lambda_2
<1$. Suppose

\newcounter{foo}
\begin{enumerate}
\item
The graph $G$ contains all edges $xy$ s.t.
$\|x -y\| \leq 4 C(d_M, \{x_i\}) / \lambda_2$;
\item
All edges of $G$ have length 
$\|x-y\| \leq (2/\pi) r_0\sqrt{24 \lambda_1} < s_0$;
\item
The submanifold $M$ is geodesically convex.
\setcounter{foo}{\value{enumi}}
\end{enumerate}
then for all $x,y$ in $\{x_i\}$:
\[
(1-\lambda_1)d_M(x,y)
	\leq d_G(x,y)
	\leq (1+\lambda_2)d_M(x,y)
\]
}

The theorem gives us conditions for ensuring that $d_G \approx d_M$ to
any given degree of accuracy, by setting $\lambda_1$ and $\lambda_2$
as small as required.  Note that if conditions (1) and (2) can not be
simultaneously satisfied, the theorem says nothing.  This implies that
our covering scale must be smaller than the scales implied by the
radius of curvature and branch separation.


{\bf Proof.}  

Let $\epsilon_{min} = 4 C(d_M, \{x_i\}) / \lambda_2$.

Since $\|x-y\| \leq d_M(x,y)$, condition~1 implies
that $G$ contains all edges $xy$ for which
$d_M(x,y)\leq \epsilon_{min}$.
We can therefore apply Theorem~2, which with
Proposition~1 gives
\[
d_G(x,y) \leq d_S(x,y)
\leq (1+4C(d_M, \{x_i\})/\epsilon_{min}) d_M(x,y)
\leq (1 + \lambda_2) d_M(x,y),
\]
establishing the right-hand inequality.

To prove the left-hand inequality, choose a path
$x_0 x_1  \dots x_p$ connecting $x$ ($= x_0$) to $y$
($= x_p$) along graph edges which minimizes
the total graph length. The conditions on $G$ and $\epsilon_{max}$
imply that each pair $x_i, x_{i+1}$ satisfies the hypotheses
of Corollary~4 with $\lambda = \lambda_1$. Then:
\begin{eqnarray*}
d_M(x,y) &\leq& d_M(x_0,x_1) + \dots + d_M(x_{p-1},x_p)\\
	&\leq&	(1-\lambda_1)^{-1} \|x_0-x_1\| +
		\dots +
		(1-\lambda_1)^{-1} \|x_{p-1}-x_p\|\\
	&=& (1-\lambda_1)^{-1}d_G(x,y)
\end{eqnarray*}
This establishes the left-hand inequality.
\qed

{\bf Aside.}
It may seem that geodesic convexity is a much stronger
condition than we really need for our proof. We could
say that $M$ is $\epsilon$-geodesically convex if whenever
$\|x - y\| \leq \epsilon$ there is a geodesic of length
$d_M(x,y)$ connecting $x$ to $y$.
Taking $\epsilon = \epsilon_{max}$, this is all that is
required in the proof. Curiously enough, it
turns out that $\epsilon$-geodesic convexity implies
full geodesic convexity for a metrically complete manifold,
such as a compact manifold, so nothing is really gained by
doing this.


%In the next section, we discuss how to satisfy these
%many conditions when the data set is chosen randomly,
%with a sufficiently high density $\alpha$ of points.

\section{Relationship to the Isomap Algorithm}
\label{sec-iso}

One piece of theoretical work is necessary in order to show that the
Isomap algorithm works.  In particular, it is necessary to show that
the graph constructed by the Isomap algorithm satisfies the properties
required in Main Theorem A.  This is relatively simple when the notion
of neighborhood is $\epsilon$ nearest neighbor and somewhat more
complicated when the $K$ nearest neighbors.  For reasons of space,
this is not included, but see \cite{isotech} for details.

There are two main claims in \cite{isomap}: that $d_G$ converges
asymptotically to $d_M$, and therefore that Isomap asymptotically
recovers the true structure for data manifolds that are isometric to a
convex domain of Euclidean space.  We consider each of these pieces in
turn.

The claim that $d_G$ converges asymptotically to $d_M$ is an
application of Theorem A for an appropriate $\epsilon$ nearest
neighbor rule.  

The assertion that Isomap asymptotically recovers the true structure of
intrinsically Euclidean data sets is really a statement about how the
$d$-dimensional Euclidean embedding $Y$ produced by Isomap relates to
a hypothetical Euclidean configuration that can be thought of as the
first stage of a generative model of the data.  We imagine that the
data were generated by first sampling points from $V$, a convex region
of $d$-dimensional Euclidean space, and then mapping those points
isometrically (and in general, nonlinearly) into a high-dimensional
observation space $X$.  The observed points in $X$ (or more properly,
their distances $d_X$) are then the inputs to Isomap, and the goal of
the algorithm is to invert the nonlinear isometric mapping $V
\rightarrow X$.  Let ${\bf v}_i$ denote the coordinates of point $i$
in the original Euclidean space $V$, which we would like to recover,
and let ${\bf y}_i$ denote the coordinates of $i$ in the embedding
produced by Isomap.  Our claim is that in the limit of infinitely many
data points, the embedding coordinates $\{{\bf y}_i\}$ produced by
applying MDS to any fixed finite set of points converge asymptotically
to their original coordinates $\{{\bf v}_i\}$, up to Euclidean
isomorphism (translation, rotation, scaling).

This claim rests on several properties of the algorithm for classical
multidimensional scaling (MDS), which serves as the final step of
Isomap.  MDS takes as input the pairwise distances for a set of points
and constructs a $d$-dimensional Euclidean embedding that captures
those distances as closely as possible.  When MDS is given as input
actual Euclidean distances for a configuration of points in a
$d$-dimensional space, it will construct a $d$-dimensional embedding
that captures those distances perfectly and thereby recovers exactly
the original configuration of the points, up to isomorphism.  
In general, any lower dimensional embedding will not capture the
distances perfectly, so it is easy to detect that $d$ is the true
dimensionality of the data.  Moreover, MDS is continuous: small
bounded variations in the input distances lead to small bounded
variations in the output embedding.  These properties are described in
detail by Cox \& Cox \cite{cox}.

The second step of Isomap produces distance estimates $d_G$ that
converge to the true geodesic distances $d_M$.  If the original
coordinates $\{{\bf v}_i\}$ were sampled from a convex Euclidean
domain $V$, then the geodesic distances $d_M$ will be equal to the
Euclidean distances in $V$.  These two facts guarantee that MDS (and
hence Isomap) will asymptotically recover the original Euclidean
configuration of the data.  We can obtain quantitative bounds on how
quickly the embedding coordinates $\{{\bf y}_i\}$ converge to the
original coordinates $\{{\bf v}_i\}$ by combining the bounds in our
Main Theorem with the perturbation analysis of MDS on page 38 of
\cite{cox}.

\section{Conclusion}

We have shown that it is possible to recover a low-dimensional
representation of a compact Euclidean manifold embedded in a high
dimensional space given that the manifold is embedded ``nicely'' (with
a reasonable branch separation and radius of curvature) and that the
points cover the manifold on a small enough scale.  However, many
question remain open.

If we do not insist on step 3 of the Isomap algorithm (embed the graph
in $\R^d$ using MDS), then this approach is much more general: it
works for any geodesically convex submanifold $M$ rather than just
submanifolds which are isometric to a convex subset of $\R^d$.

This paper is about \emph{sufficient} conditions allowing Isomap (or
some other algorithm) to extract a manifold from a high dimensional
space.  It is interesting to consider \emph{necessary} conditions as
well.  What are necessary conditions for manifold extraction up to
error $\epsilon$?

We have not analyzed observation noise.  Suppose the data points are
perturbed by some low-amplitude isotropic noise process.  We expect
that the asymptotic result of applying Isomap to this noisy data will
be a ``thickened'' embedding, with the top $d$ embedding dimensions
accounting for most of the variance in graph distances and the bottom
$n-d$ dimensions accounting for some small residual variance whose
amplitude can be bounded in terms of the magnitude of the noise.
Manifold reconstruction in the presence of embedding noise should be
possible, but it is not yet analyzed (see \cite{isocomment} for some
thoughts).

The theory described here was developed in tandem with the current
version of the Isomap algorithm (see \cite{iso1} for an earlier
version), and led to design changes with greatly improved performance:
significantly lower empirical error obtained in an order of magnitude
less time, using an order of magnitude less training data.

\section*{Acknowledgments}

We thank S. Dasgupta, R. Lehrer, S. Mahajan, and H. Moore for helpful comments
on this work. 

\begin{thebibliography}{10}

\bibitem{crust} Nina Amenta, Marshall Bern, David Eppstein, ``The
crust and the beta-skeleton: combinatorial curve reconstruction'',
Graphical models and image processing, 60/2:2, pages 125-135 (1998)

\bibitem{pcrust} Nina Amenta, Sunghee Choi, Ravi Kolluri. ``The Power
Crust'', Proceedings of 6th ACM Symposium on Solid Modeling, 2001,
pages 249-260.

\bibitem{isotech} Mira Bernstein, Vin de Silva, John Langford and Josh
Tenenbaum Graph approximations to geodesics on embedded manifolds
Technical report 2000, http://isomap.stanford.edu/BdSLT.ps

\bibitem{iso1} J.~B.~Tenenbaum (1998).  Mapping a manifold of
perceptual observations.  Advances in Neural Information Processing
Systems 10.

\bibitem{isomap} J.~B.~Tenenbaum, V.~de~Silva, J.~C.~Langford (2000).
A global geometric framework for nonlinear dimensionality reduction.
{\em Science} {\bf 290} (5500), 22 Dec 2000.

\bibitem{isocomment} J.~B.~Tenenbaum, V.~de~Silva, J.~C.~Langford (2000).
The Isomap Algorithm and Topological Stability.
{\em Science} {\bf 295} (5552), 4 Jan 2002.

\bibitem{chernoff}
H.~Chernoff (1952). A measure of asymptotic efficiency for test of a
hypothesis based upon the sum of observations.  {\em Annals of
Mathematical Statistics} {\bf 23}, 493-507. 

\bibitem{cox}
T.~F.~Cox and M.~A.~A.~Cox (1994).  {\em Multidimensional Scaling}. 
London: Chapman and Hall. 

\bibitem{JL} W.~Johnson and J.~Lindenstrauss ``Extensions of Lipschitz
maps into a Hilbert Space.'' Contemp. Math. 26, 1984, pp. 189-206.

\bibitem{Piotyr} Piotyr Indyk, ``Algorithmic applications of
low-distortion geometric embeddings'' FOCS2001 tutorial and survey
paper.

\bibitem{LLE} Sam Roweis and Lawrence Saul, ``Nonlinear dimensionality
reduction by locally linear embedding.''  Science, v.290 no.5500,
Dec.22, 2000. pp.2323--2326.

\bibitem{Vapnik} Vladimir N. Vapnik, ``Statistical Learning Theory'',
Wiley, December 1999.


\end{thebibliography}

\end{document}
