Finding dimensions of a point cloud - floating point issues

Question

I have $N$ data points of some dimension $D$.

I want to know the dimension of the shape that those data points represent - for instance they might be a 2 dimensional triangle, even though they are in 8 dimensional space.

A way of doing this mathematically is to pick one of the points and subtract it from all of the other points to get $N-1$ vectors.

If i make these vectors into a matrix, the rank of the matrix will tell me the dimension of the shape of the data points.

The problem though is that implementing this using floating point math, not all vectors will cancel out that should.

I was wondering, is there a better way to do this when using floating point math? Or, is there a way to get a thickness in each dimension so that very thin dimensions can be ignored?

Answer 1

One common way to do this is to apply a Principal Component Analysis (PCA) to your data. The operation essentially consists of rotating the data around the mean to align with the principal components. Most of the variance is moved to the first components. If you know the dimension of your manifold, then you can simply select the first $k$ components and reconstruct the lower dimensionality data. If you don't, there are simple criteria such as threhsolding the ratio of the variances. Of course more elaborate Bayesian methods also do exist, such as this one. I'll quickly give an overview of the simple method. Let $\mathbf{\lambda}=\{\lambda_1..\lambda_N\}$ denote the sorted eigenvalues (giving you the variances). We could create a monotonically increasing CDF-like curve:

$$ f(i) = \frac{\sum\limits_{j=1}^i \lambda_j}{\sum\limits_{j=1}^N \lambda_j} $$ where each element represents the variance explained up to that eigenvalue (or component). We could then pick a threshold $\tau$ (e.g. \tau=0.98). Then we throw out the components which remain above that (meaning low contributions)

$$ f(i)>\tau $$

Similarly, one could also threshold the difference $g(i)=max(f(i)−f(i−1))$, as this will be the value where adding a dimension really makes sense. If $g(i)$ is small, there would be no real contribution to explain the variance.

This problem sounds like 'dimensionality estimation' or 'dimension discovery'. There are also other methods available. PCA is just the most easy-to-implement and famous one. If your structure is linear (such as a triangle as you mentioned) PCA should be suitable.