Manifold Learning with Geodesic Minimal Spanning Trees
  In the manifold learning problem one seeks to discover a smooth low
dimensional surface, i.e., a manifold embedded in a higher dimensional linear
vector space, based on a set of measured sample points on the surface. In this
paper we consider the closely related problem of estimating the manifold's
intrinsic dimension and the intrinsic entropy of the sample points.
Specifically, we view the sample points as realizations of an unknown
multivariate density supported on an unknown smooth manifold. We present a
novel geometrical probability approach, called the
geodesic-minimal-spanning-tree (GMST), to obtaining asymptotically consistent
estimates of the manifold dimension and the R\'{e}nyi $\alpha$-entropy of the
sample density on the manifold. The GMST approach is striking in its simplicity
and does not require reconstructing the manifold or estimating the multivariate
density of the samples. The GMST method simply constructs a minimal spanning
tree (MST) sequence using a geodesic edge matrix and uses the overall lengths
of the MSTs to simultaneously estimate manifold dimension and entropy. We
illustrate the GMST approach for dimension and entropy estimation of a human
face dataset.
