Manifold learning using Euclidean k-nearest neighbor graphs [image processing examples]
Authors:
- 28 September 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 3 (15206149) , 988
Abstract
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 n 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. In previous work, we introduced a geometric probability method called the geodesic minimal spanning tree (GMST) to obtain asymptotically consistent estimates of manifold dimension and entropy. In this paper, we present a simpler method, based on the k-nearest neighbor (k-NN) graph that does not require estimation of geodesic distances on the manifold. The algorithm is applied to standard synthetic manifolds as well as real data sets consisting of images of faces.Keywords
This publication has 6 references indexed in Scilit:
- Geodesic Entropic Graphs for Dimension and Entropy Estimation in Manifold LearningIEEE Transactions on Signal Processing, 2004
- From few to many: illumination cone models for face recognition under variable lighting and poseIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Nonlinear Dimensionality Reduction by Locally Linear EmbeddingScience, 2000
- A Global Geometric Framework for Nonlinear Dimensionality ReductionScience, 2000
- Probability Theory of Classical Euclidean Optimization Problems1998
- Riemannian Geometry1992