Estimating Manifold Dimension by Inversion Error

Abstract

Video and image datasets can often be described by a small number of parameters, even though each image usually consists of hundreds or thousands of pixels. This observation is often exploited in computer vision and pattern recognition by the application of dimensionality reduction techniques. In particular, there has been recent interest in the application of a class of nonlinear dimensionality reduction algorithms which assume that an image dataset has been sampled from a manifold. From this assumption, it follows that estimating the dimension of the manifold is the first step in analyzing an image dataset. Typically, this estimate is obtained either by using a priori knowledge, or by applying one of the various statistical and geometrical methods available. Once an estimate is obtained, it is used as a parameter for the nonlinear dimensionality reduction algorithm. In this paper, we consider reversing this approach. Instead of estimating the dimension of the manifold in order to obtain a low dimensional representation, we consider producing low dimensional representations in order to estimate of the dimensionality of the manifold. By varying the dimensionality parameter, we obtain different low dimensional representations of the original dataset. The dimension of the best representation should then correspond to the actual dimension of the manifold. In order to determine the best representation, we propose a metric based on inversion. In particular, we propose that a good representation should be invertible, in that we should be able to reverse the reduction algorithm's transformation to obtain the original dataset. By coupling this metric with any reduction algorithm, we can estimate the dimensionality of an image manifold. We apply our method in the context of locally linear embedding (LLE) and Isomap to six frequently used examples and two image datasets.

Additional details