# Finding dimensions of a point cloud - floating point issues

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?

• People who do computational geometry seem to be fond of arbitrary-precision rational numbers. – Rodrigo de Azevedo Apr 16 '17 at 17:17

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.
• Well, due to numerical issues you will never get a perfect separation between PCA components, i.e. %100 of the variance will not be exactly explained by first $k$ components. Some of it will be found in the following components. This is why we use a threshold and not an exact selection. The threshold handles conditions like small noise or numerical inaccuracy. Outliers are not handled though. One could maybe use probabilistic PCA to do that. – Tolga Birdal Apr 16 '17 at 18:41