1
$\begingroup$

Suppose we're given the data set $\{x_1 \dots x_n\}$ in $\mathbb{R}^D$ the $D$-dimensional Euclidean space, and assume this data has intrinsic dimension $d < D.$ N.B. this just means that data is lying on a $d$-dimensional connected manifold which can be very flat or very curved but certainly it doesn't assume the manifold is a hyperplane, i.e. linear; and assume we've no idea about the curvature of this manifold: we just know that the manifold is $d$-dimensional.

Suppose we're interested in determining whether the above manifold, or equivalently the data has an linear structure or not, i.e. if the manifold above is a $d$-dimensional hyperplane or not. This means, we want to test, does this manifold have zero curvature and is it homeomorphic to an open subset of a Euclidean space? To ease things, assume the manifold is homeomorphic to an open subset of a Euclidean space, then test if the sectional curvature of this manifold is identically zero.

Is it possible to test, and if yes, what test(s) do we need? More specifically: what I want is a test of hypothesis following the steps:

(1) Construct a suitable statistic $\Theta(X_1, \dots X_n)$ that's representative of the linearity of the data.

(2) Determine the sampling distribution of the statistic, and if needed, the limiting distribution of $\Theta(X_1, \dots X_n)$ as $n \to \infty.$

(3) Accept the null hypothesis $H_0:$ the data is linear if for a chosen threshold $\theta, \Theta(X_1, \dots X_n) \le \theta, $ and reject it otherwise.

Let's consider two specific examples of data, where I'd like to find whether the data is linear or not, with certain confidence from the test described above. I'd rather prefer the answer for the second example.

Example I: You may consider the the data coming from the $2$-sphere and then embedded by zero padding in $\mathbb{R}^{50}$, so consider the data $x_i$ sampled from $M:=\{(x, y, z, 0, \dots 0): x^2 + y ^2 + z^2 =1\}, 0$ occurring $47$ times in this expression so that $M \subset \mathbb{R}^{50}.$ Now clearly in this case, $M$ is two dimensional, and not a linear subspace of $\mathbb{R}^{50},$ so the test I'm asking for would answer in the negative - it'd tell us that the samples came from a nonlinear manifold, and not a linear hyperplane.

Example II: Perhaps Example I above was a bit easy, so consider instead $100$ data points $x_i \in \mathbb{R}^{50}, x_i= (y_i, 0), 0$ occurs $47$ times, and $y_i$'s come from the manifold $\{(x,y,z): x^2 y^3 z + sin(xy) cos(yz) + tan(y-z +1) - xy^2 e^z - xyz + cos(yz) - xy + z - 5=0\}$. The reason to cite this example is that unlike the Example I, it's not a linear function of functions of one variables, as the example I was a linear/affine function of $x^2, y^2, z^2.$

So I see that many of you've suggested PCA, and perhaps because of my own background, I'm having trouble to understand how exactly it helps us infer if the manifold $M$ is linear or not. Say, given $d,$ I do the PCA, and find the best approximating $d$-dimensional hyperplane approximating the data (or equivalently, maximizing the variance). I'm okay with this so far - but what do we do next? What's the statistic in question that'd help me accept or reject the null hypothesis that the data was linear?

$\endgroup$
33
  • 1
    $\begingroup$ This is probably not the kind of answer you are hoping for, but if $D$ is not huge, $<30$, say, what I'd do is run a "grand tour" in GGobi (www.ggobi.org), i.e., a flexible "rotation" through D-dimensional space, and see whether a low-d linear structure shows up. Chances are there's also other software doing this. $\endgroup$ – Lewian May 20 '20 at 9:23
  • 1
    $\begingroup$ Another thought: The way you present the problem it is actually dependent on the choice of $dist$, and if $dist$ is Euclidean (or many other distances but not Mahalanobis, with which this could work) it is dependent on scaling, meaning that whatever nonlinear or high-d structure you have can be made to fulfil your $\epsilon$-condition with suitable rescaling (be it multiplying all values by $10^{-10}$), without actually making the data "more linear". Not sure whether you really want that. $\endgroup$ – Lewian May 20 '20 at 9:35
  • 1
    $\begingroup$ This method is so spectacularly non-robust that it wouldn't make sense to apply it to most actual datasets. A more statistical way of thinking about it would be in terms of the whole distribution of distances to the affine subspace $H.$ That puts us squarely into the domain of PCA, as evidenced by the closely related questions at stats.stackexchange.com/questions/5922, stats.stackexchange.com/questions/35185, stats.stackexchange.com/questions/16327, etc. $\endgroup$ – whuber May 20 '20 at 11:23
  • 3
    $\begingroup$ I did years of research in differential geometry and understand all the terms, concepts, and notation in this question, but still cannot make sense of the question due to the inherent contradictions and lack of meaning of parts of the question. For instance, your Example I of an embedded 2-sphere obviously is confined to a 3D affine subspace. Moreover, it makes no sense to state that a (finite) dataset "is" a hyperplane. I think we will remain at an impasse unless you can describe the underlying statistical problem you face in non-mathematical terms. $\endgroup$ – whuber May 25 '20 at 18:50
  • 2
    $\begingroup$ A connected manifold with minimum dimension containing the data is any non-self-intersecting curve passing through all the data. (Such curves always exist in three or more dimensions.) It has dimension $1$ and has zero intrinsic curvature. $\endgroup$ – whuber May 25 '20 at 20:41
0
$\begingroup$

PCA gives you the answer and the reason is because when it is able to find what you call intrinsic dimension $d<D$ it also means that the manifold is linear hyperplane. In fact all that PCA does is find that hyperplane or does not find it.

So, your problem reduces to looking for a rotation of your D-dimensional data set X such that $Z=XA$, where A is D-dimensional rotation matrix and X is the variables, which produces Z with a rank $d<D$.

Now, you should see that we got to an eigen value problem. Whether you do SVD or PCA, these would be the methods that are the answer to your question. In case of PCA you look at explained variance, and if the first d PCs explain enough of the variance in the data, then you got your linear transformation.

Now, if you were interested in nonlinear transformations then things would get more interesting. What if there was a transformation $Z=f(X)$ such that matrix $Z$ has a lower rank that $X$? In this case PCA can't help you. You could run an autoencoder or something along those lines, but then your question would be valid: is there some quick diagnostic I could check before running computationally intensive techniques?

Example

Let's pick points from a 3-D sphere, i.e. $x^2+y^2+z^2=1$. Adding (padding) with zeros like in the question doesn't make any difference for eigen analysis, but I added two columns of zeros just for the sake of it.

Here, columns B-H are simulated data set from sphere using inefficient but very simple method: enter image description here We have a data matrix 100x5, where two last columns are zeros. Now, look at the covariance matrix in cells M2:Q6 - you can see how zero columns drop off of it immediately, you can see visually that the rank of the matrix is 3 or less.

Next, we apply eigen analysis, and in cells L8:L12 you get the eigen values. There are 5 of them with last two zeros. Again you see that the rank or three or less. In column S I'm showing the ratio of the eigen value to the sum of eigenvalues, which shows how much each adds to the total variance. You see that all three variables add approximately 1/3 to the variance. Hence, we can conclude that we can't drop any one the remaining three degrees of freedom. In other words, NO, your dataset does not come from a linear hyperplane.

There's no hidden linear structure beyond trivial linear (constant) columns. However, the zeros are coming from a hyperplane, namely, a trivial one - a point. So, if you were to add all 47 zeros, then eigen analysis would have shown that 47 variables are coming from the trivial hyperplane, a point; and that the first three do not.

Now, instead of using x,y,x, let's use the squares of them. Here's what you get in eigen analysis: only two explained variances are large, the third one is basically a rounding error. So, PCA picks up immediately that $x^2,y^2,z^2$ are coming from two dimensional hyperplane.

enter image description here

$\endgroup$
15
  • $\begingroup$ Thanks! If I understood correctly, PCA helps us to find the best linear approximation to the data, by minimizing the projection distance to a certain ($d$ -dim, $d < D$ given) hyperplane or equivalently maximizing the variance. So, to determine if the data is "linear enough" or not, are you talking about computing the minimum of sum of squares of projection distances for varying $d$-dimensional hyperplanes $H$, and then take the minimum $min$ of them as an indicator of linearity? So if $min$ is small enough, then data is linear, otherwise no? Is there test of hypothesis for this? $\endgroup$ – Mathmath May 20 '20 at 15:17
  • $\begingroup$ (contd.) Extending on the previous paragraph, let's first compute for a given $d < D, min(d):=$ minimum sum of squared projection distances to $H.$ Now we've the first step; if $min(d)$ is small, then infer the data is almost linear, otherwise no; but then can we design a suitable statistic following certain distribution and test its value against a threshold to accept or reject the null hypothesis $H_0:$ the data is linear. Or in other word, can we accept or reject that the data is linear with a certain confidence? $\endgroup$ – Mathmath May 20 '20 at 15:22
  • $\begingroup$ (contd.) I saw your edits only after I write my comments, although they still stand. I'm not interested in linear or nonlinear transformations. All I want to check is if the data is linear or not. It can be a quick rigorius test like: devise a test statistic, that'd take bigger/smaller values if the data is more linear and vice versa, find the distribution of that test statistic, and then accept/reject the null hypothesis: the data is linear. $\endgroup$ – Mathmath May 20 '20 at 15:47
  • $\begingroup$ I;m saying that PCA is the test. Once you get the explained variances from PCA, examing them helps you identify what is $d$, and whether it's $d<D$ $\endgroup$ – Aksakal May 20 '20 at 16:48
  • 1
    $\begingroup$ @Mathmath answer is the same: PCA. The only reason I bring up $d<D$ is because that's the test you're looking for. Your question boils down to analyzing the eigen problem of wither covariance or correlation matrix of your data set. No matter what you do, you'll end up needing to look at eigen problem. That's in the core of geometric interpretation of your variables and their linear relations. PCA happens to be the most user-friendly way of doing this. $\endgroup$ – Aksakal May 20 '20 at 17:03

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