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!
 A: 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.
A: 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.
A: 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').
A: 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
