# Estimating the dimension of a data set

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!

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.

• +1 Nice find! The paper also has a brief discussion of the PCA approach (as well as some other methods).
– whuber
Jan 6, 2011 at 23:08
• Thanks very much, I think that this is the closest to what my colleague was looking for.
– user1157
Jan 8, 2011 at 19:17

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.

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').

• I'd even say box-counting dimension for a more practical statistic. Jan 6, 2011 at 22:01

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