7
$\begingroup$

We all know that Principal Component Analysis is executed on a Covariance/Correlation matrix, but what if we have a very high dimensional data, assuming 75 features and 157849 rows? How does PCA tackle this?

  • Does it tackle this problem in the same way as it does for correlated datasets?
  • Will my explained variance be equally distributed among the 75 features?
  • I came across BARTLETT'S Test and KMO Test which helps us:
    • in identifying the wether there is any correlation present or not, and
    • the proportion of variance that might be a common variance among the variables

respectively. I can certainly leverage these two tests in making a controlled decision, but I am still looking for an answer towards:

  • How does PCA behave when there is no correlation in the dataset?

I want to get an interpretation of this in a way that I could explain it to my non-technical brother.

Practical example using Python:

s = pd.Series(data=[1,1,1],index=['a','b','c'])
diag_data = np.diag(s) 
df = pd.DataFrame(diag_data, index=s.index, columns=s.index)
# Normalizing
df = (df.subtract(df.mean())).divide(df.std())

Which looks like:

        a            b          c
a   1.154701    -0.577350   -0.577350
b   -0.577350   1.154701    -0.577350
c   -0.577350   -0.577350   1.154701

Covariance Matrix looks like this:

Cor = np.corrcoef(df.T)
Cor

array([[ 1. , -0.5, -0.5],
       [-0.5,  1. , -0.5],
       [-0.5, -0.5,  1. ]])

Now, calculating PCA Projections:

eigen_vals,eigen_vects = np.linalg.eig(Cor)
projections = pd.DataFrame(np.dot(df,eigen_vects))

And projections are:

        0             1             2
0   1.414214    -2.012134e-17   -0.102484
1   -0.707107   -2.421659e-16   -1.170283
2   -0.707107   -1.989771e-16   1.272767

The explained Ratio seems to be equally distributed among two features:

[0.5000000000000001, -9.680089716721685e-17, 0.5000000000000001]

Now, when I tried calculating the Q-Residual error in order to find the reconstruction error, I got zero for all the features:

a    0.0
b    0.0
c    0.0
dtype: float64

This would indicate that PCA on a non-correlated dataset like identity matrix gives us the projections which are very close to the original data-points. And the same results are obtained with the DIAGONAL MATRIX.

If the reconstruction error is very low, this would suggest that, in a single pipeline, we can fix the PCA method to execute and even if the dataset is not carrying much correlation we will get the same results after PCA transformation, but for the dataset which has high correlated features, we can prevent our curse of dimensionality.

Public views on this?

$\endgroup$
8
  • 2
    $\begingroup$ Think about what happens when you go to diagonalize a diagonal matrix. $\endgroup$
    – Dave
    Jul 19 at 9:58
  • $\begingroup$ Well, i get the same matrix back. $\endgroup$ Jul 19 at 10:24
  • 3
    $\begingroup$ So when you apply PCA in a setting where the covariance matrix is diagonal, what happens? $\endgroup$
    – Dave
    Jul 19 at 10:26
  • 1
    $\begingroup$ M = PDP_inv. So this means if i have no correlation between my features, PCA will give me back the original dataset? One thing i found till now is that "If my 75 features have no information in common, i would need 75 components to capture 100% of the information". $\endgroup$ Jul 19 at 10:27
  • $\begingroup$ Unless you have perfect multicollinearity (not necessarily any two variables with perfect correlation), I think you need all of the features to get $100\%$ of the information…assuming correlation is the correct dependence structure. // Do you mean zero population covariance or zero sample (observed) covariance? $\endgroup$
    – Dave
    Jul 19 at 10:32
18
$\begingroup$

If you have no observed correlation, then your covariance matrix is diagonal, and the PCA diagonalizes a matrix that is already diagonal (so it does nothing).

If you have no population correlation but observe small sample correlations due to sampling variability, then the PCA is diagonalizing a covariance matrix that is nearly diagonal, and the result will be a minimally different set of features from the PCA.

$\endgroup$
2
  • $\begingroup$ Let me try this in terms of hands on. Please do share a hands on example if you can too. $\endgroup$ Jul 19 at 10:47
  • $\begingroup$ This is not correct if your original matrix has duplicate eigenvalues (e.g. if all variables have unit variance). Then sampling variation can "mix" the eigenvectors arbitrarily. $\endgroup$ Jul 25 at 15:14
2
$\begingroup$

The components are the eigenvectors of the covariance matrix. If the covariance matrix is diagonal, then the features are already eigenvectors. So PCA generally will return the original features (up to scaling), ordered in decreasing variance. If you have a degenerate covariance matrix where two or more features has the same variance, however, a poorly designed algorithm that returns linear combinations of those features would technically satisfy the definition of PCA as generally given.

$\endgroup$
1
$\begingroup$

If the true underlying covariance matrix is the identity:

  • the leading eigenvectors of the sample correlation matrix will point in random directions, rather than directions that are informative about the nature of the data.
  • the largest eigenvalues of the sample correlation matrix will still be larger than the smallest eigenvalues, by definition, and this might mislead you into thinking there's some signal. If you are afraid this is happening to you, you can try to verify that the eigenpairs you use exceed the upper bound expected from iid data. This is governed by the Marchenko-Pastur distribution (wiki). If you want to see an example, the M-P upper bound is used for principal component selection by Aviv Regev and coauthors in their analysis of gene activity during zebrafish embryogenesis (Science paper).

M-P only works for data with mean 0, variance 1. There might be some similar theory for other situations; I'm not sure.

$\endgroup$
0
$\begingroup$

It depends on the true covariance structure of population. If multiple features have the same population variance, sampling variance can actually mix up the observed features arbitrarily, whereas if all features have different population variances this cannot happen.

Let me show this through a derivation. Assume your true population covariance matrix is $A$ and your observed is $A + \epsilon B$, where $\epsilon$ is a small positive number. Basically, your can think of $B$ as the direction that the covariance matrix is perturbed in (perturbation meaning 'error' due to sampling), and $\epsilon$ is the magnitude of that perturbation.

Remember that PCA is basically looking at the eigenvectors of the covariance matrix. If the true covariance is $A = aI$, the eigenvectors of $A + \epsilon B$ are just eigenvectors $v$ of $B$. In other words, running PCA on your observed data will return features determined entirely by your sampling variation!

The reason this happens is that PCA does not have a unique solution for your true covariance matrix in the first place. That is, whenever you try to diagonalize a matrix with duplicate eigenvalues, you run into the issue that there are multiple valid ways to pick unit eigenvectors (because you have eigenspaces that have dimension greater than one). Thus even if $A$ is not of the form $aI$, but has duplicate eigenvalues, there will be some set of eigenvectors of $A + \epsilon B$ which will deviate from the original features in a way dictated entirely by the eigenvectors of $B$.

Fortunately, in reality it is rare to find variables with exactly the same population variance. In this case, we can show that the features are robust against sampling variation. This is actually true in general (i.e. regardless of the assumption that your population variables are uncorrelated).

To see this, we can just approximate the eigenvectors of $(A + \epsilon B)$ under some mild assumptions. Basically we want to show that they are just a perturbation of the eigenvectors of $A$ by a term that scales roughly linearly with $\epsilon$.

The first assumption is of course that all eigenvalues of $A$ are unique. However, second, we need to assume that the eigenspaces of $A$ and $B$ are disjoint, meaning that they have different eigenvectors. Again we can just appeal to reality -- a random matrix will almost never have the same eigenvectors as a fixed matrix (unless that fixed matrix is a multiple of $I$).

A warning that this "proof" is both very long and also not exactly valid. The key weakness is where I assume that the solution is analytic, which is sort of what we actually want to prove. Regardless, hopefully it will provide some insight.

[start of proof]

Let $u$ denote the $i^{th}$ eigenvector of $A$ for some $i$, and have eigenvalue $\alpha$. We can arbitrarily write the eigenvector of $(A + \epsilon B)$ as $(u+v)$ for some $v$ by taking an eigenvector of the matrix and then letting $v$ be that eigenvector minus $u$.

Now, what is $(A + \epsilon B)(u+v)$? It should be $\lambda (u + v)$ for some $\lambda$. For simplicity, we can rewrite this as $(\alpha + \epsilon \gamma)(u+v)$ for $\gamma = \epsilon^{-1}(\lambda - \alpha)$. This makes sense because the eigenvalues are a continuous function of the matrix entries, which can be proven by using that the determinant is a continuous function (since it is a polynomial) and then using that the eigenvalues are defined using the determinant.

On the other hand, we also have $$ (A + \epsilon B)(u+v) = Au + Av + \epsilon B (u+v) = \alpha u + Av + \epsilon B (u+v). $$ Thus \begin{align*} (A + \epsilon B)(u+v) &= (\alpha + \epsilon \gamma)(u+v) = \alpha u + \epsilon \gamma u + \alpha v + \epsilon \gamma v \\ Av + eBu + eBv &= \epsilon \gamma u + (a + \epsilon \gamma)v \\ \epsilon B u + (A + \epsilon B)v &= \epsilon \gamma u + (\alpha + \epsilon \gamma)v \\ \epsilon(B - \gamma I)u + ((A - \alpha I) + \epsilon (B - \gamma I))v &= 0 \end{align*}

Now, there are two possible ways this equation could hold. One involves having $(A - \alpha I)v = 0$. However, this is would mean that $v$ is an eigenvector of $A$ with eigenvalue $\alpha$, and thus so is $u+v$. The problem with this is that it would imply tht $(u+v)$ is an eigenvector of $B$ as well, and by assumption $B$ cannot share eigenvectors with $A$. Thus certainly $(A - \alpha I)v$ is nonzero.

However, looking at the equation, the $(A - \alpha I)v$ is the only term that does not appear proportional to $\epsilon$. Why is this interesting? Well, because if it were not dependent on $\epsilon$ at all, the equation could not have a solution -- since $\epsilon$ is essentially arbitrary, taking the limit as $\epsilon \to 0$ would create an inconsistent equation. The fix is to recognize that $v$ depends on $\epsilon$, and really it must be at least proportional. More precisely, it should be $$ v = w_{0} + \epsilon w_{1} + \epsilon^{2} w_{2} + (\mathrm{higher \ order \ terms}). $$ I am making a bold assumption that $v$ is essentially analytic in $\epsilon$, but since we are basically solving a polynomial equation ($\gamma$ is also analytic in $\epsilon$), it seems reasonable. This is where the approximation comes in anyway.

Now, note that the $w_{0}$ must be zero, since as $\epsilon \to 0$, we must have $u+v \to u$. Basically, if $\epsilon$ is quite small, then $v \approx \epsilon w$. Furthermore, \begin{align*} \epsilon(B - \gamma I)u + ((A - \alpha I) + \epsilon (B - \gamma I))v &= \epsilon(B - \gamma I)u + ((A - \alpha I) + \epsilon (B - \gamma I))\epsilon w \\ &= \epsilon(B - \gamma I)u + \epsilon (A - \alpha I) w + \epsilon^{2} (B - \gamma I) w \\ &\approx \epsilon (B - \gamma I)u + \epsilon (A - \alpha I) \end{align*} because $\epsilon^{2} \approx 0$.

Therefore, dividing out by $\epsilon$, in the end we are just solving $$ (B - \gamma I)u + (A - \alpha I) w = 0 $$ or really $$ (B - \gamma I)u = -(A - \alpha I) w. $$ Now, $-(A - \alpha I) w$ is some unknown vector in the columnspace of $(A - \alpha I)$. Knowing this allows to solve for $\gamma$. Once we have done this, the term $(B - \gamma I)u$ becomes a known vector and we are just solving a linear equation.

The value of $\gamma$ is unique because the columnspace of $(A - \alpha I)$ has smaller dimension than the whole space. In other words, it is 'difficult' to get the image of $u$ exactly into the subspace, so there is only one way to do it. However, the solution for $w$ is not unique, in the sense that $(\alpha I - A)w = y$ does not have a unique solution ($y = (B - \gamma I)u$), with the reason being that $(\alpha I - A)$ has a nontrivial nullspace, in particular containing the eigenvectors of $A$ with eigenvector $\alpha$. However, we can pick the vector $w$ solving our linear equation which minimally violates the equation we actually wanted to solve. In other words, we can pick it so the norm of $(B - \gamma I)w$ is minimal. This is unique.

[end of proof]

Ok, so what have we actually shown with all of this? Basically, for small $\epsilon$ it is possible to get a unique approximation to the eigenvectors of $(A + \epsilon B)$ that has minimal 'error'. These eigenvectors are perturbed from the eigenvectors of $A$ by a small amount which is proportional to $\epsilon$. Therefore, so long as the features of the true population would be uniquely chosen by PCA (i.e. they have distinct population variances), the features of the observed data also can be uniquely chosen by PCA and they are perturbed from the true features by an amount roughly proportional to the size of the sampling error (assuming the sampling error is small!).

$\endgroup$
1
  • $\begingroup$ If anyone knows how to add a text box that is minimized by default, that would be awesome, since my proof is way too long to just leave as is. $\endgroup$ Jul 26 at 15:04

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.