A paper I wrote with Shawn Martin, published in the 2005 ACM Symposium on Applied Computing.

Summary for lay people:

We can make countless observations of any object in the world. Yet after we have made enough different observations, we know all there is to know. This number is typically known as the dimensionality of the object. For example, to know the location of a point on a screen, we need only know two numbers: column and row. To completely specify a point in a RGB color screen, we need know five numbers: column, row, and intensity for each of three primary colors.

A variety of applications (MP3s, DVDs, Internet transmission, etc.) benefit from describing an object in as little information as possible. It is thus of interest to know the dimensionality of an object, to know how to encode it and how much information one can expect to need. Yet today, no automated methods to determine the dimensionality of an object exist.

We describe a method to compute the dimensionality of objects. The method works by attempting to represent an object with less information (reducing its dimensionality) and then trying to reconstruct the original object from it. If there is no error, no information was lost, and the reduced dimensionality was at least as high as that of the object represented. On the contrary, if information was lost, the dimensionality was likely higher than that of the reduced dimensionality representation. Repeating this process for different dimensions tells us the dimensionality of the object.

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.

The full text of the paper