2003/07/16 by Jose Costa, Jose A. Costa, Costa, Jose +3
Computer Science · Mathematics · #Advanced Vision and Imaging #Artificial intelligence #Combinatorics #Computer Vision and Pattern Recognition (cs.CV) #Computer science #Dimension (graph theory) #Dimensionality reduction #Entropy (arrow of time) #F.2.2 #FOS: Computer and information sciences #Face and Expression Recognition #G.3 #Geodesic #Intrinsic dimension #Machine Learning (cs.LG) #Manifold (fluid mechanics) #Mathematical analysis #Mathematics #Minimum spanning tree #Morphological variations and asymmetry #Nonlinear dimensionality reduction #Physics #Riemannian manifold #Spanning tree #Statistics #cs.CV #cs.LG
paper · pdf · doi:10.48550/arxiv.cs/0307038
13 pages, 3 figures
arxiv created 2003/07/16 · openalex publication_date 2003/07/16 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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ényi α-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.