Estimating the dimension of a data set

Question

A colleague in applied statistics sent me this:

"I was wondering if you know any way to find out the true dimension of the domain of a function. For example, a circle is a one dimensional function in a two dimensional space. If I do not know how to draw, is there a statistic that I can compute that tells me that it is a one dimensional object in a two dimensional space? I have to do this in high dimensional situations so cannot draw pictures. Any help will be greatly appreciated."

The notion of dimension here is obviously ill-defined. I mean, I could run a curve through any finite collection of points in high dimensional space, and say that my data is one-dimensional. But, depending on the configuration, there may be an easier or more efficient way to describe the data as a higher dimensional set.

Such issues must have been considered in the statistics literature, but I'm not familiar with it. Any pointers or suggestions? Thanks!

Answer 1

Principal Components Analysis of local data is a good point of departure. We have to take some care, though, to distinguish local (intrinsic) from global (extrinsic) dimension. In the example of points on a circle, the local dimension is 1, but overall the points within the circle lie in a 2D space. To apply PCA to this, the trick is to localize: select one data point and extract only those that are close to it. Apply PCA to this subset. The number of large eigenvalues will suggest the intrinsic dimension. Repeating this at other data points will indicate whether the data exhibit a constant intrinsic dimension throughout. If so, each of the PCA results provides a partial atlas of the manifold.

Answer 2

See

Levina, E. and Bickel, P. (2004) “Maximum Likelihood Estimation of Intrinsic Dimension.” Advances in Neural Information Processing Systems 17

http://books.nips.cc/papers/files/nips17/NIPS2004_0094.pdf

Their idea is that if the data are sampled from a smooth density in $R^m$ embedded in $R^p$ with $m < p$, then locally the number of data points in a small ball of radius $t$ behaves roughly like a poisson process. The rate of the process is related to the volume of the ball which in turn is related to the intrinsic dimension.

Answer 3

I highly recommend to read this survey: Camastra, F. (2003). Data dimensionality estimation methods: a survey. Pattern recognition, 36(12), 2945-2954.

For performing this estimation, I found very good toolbox in matlab Matlab Toolbox for Dimensionality Reduction. In addition to the techniques for dimensionality reduction, the toolbox contains implementations of 6 techniques for intrinsic dimensionality estimation

Answer 4

I'm not sure about the 'domain of a function' part, but Hausdorff Dimension seems to answer this question. It has the odd property of agreeing with simple examples (e.g. the circle has Hausdorff Dimension 1), but of giving non-integral results for some sets ('fractals').