1
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ Cool! I notice the question is asking about numerical stability issues. Can you offer any explanation how/why PCA deals with numerical stability issues? Why don't the same numerical stability problems affect PCA, too? I believe you that it works, it just might be nice to have some understanding of why it works. $\endgroup$ – D.W. Apr 16 '17 at 17:36
  • $\begingroup$ 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. $\endgroup$ – Tolga Birdal Apr 16 '17 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.