Applications of Linear Alebra: PCA
====

We will explore 3 applications of linear algebra in data analysis - change of basis (for dimension reduction), projections (for solving linear systems) and the quadratic form (for optimization). The first application is the change of basis to the eigenvector basis that underlies Principal Components Analysis s(PCA).

We will review the following in class:

- The standard basis
- Orthonormal basis and orthgonal matrices
- Change of basis
- Similar matrices
- Eigendecomposition
- Sample covariance
- Covariance as a linear transform
- PCA and dimension reduction
- PCA and "explained variance"
- SVD


```python
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
```

Variance and covariance
----

Remember the formula for covariance

$$
\text{Cov}(X, Y) = \frac{\sum_{i=1}^n(X_i - \bar{X})(Y_i - \bar{Y})}{n-1}
$$

where $\text{Cov}(X, X)$ is the sample variance of $X$.


```python
def cov(x, y):
    """Returns covariance of vectors x and y)."""
    xbar = x.mean()
    ybar = y.mean()
    return np.sum((x - xbar)*(y - ybar))/(len(x) - 1)
```


```python
X = np.random.random(10)
Y = np.random.random(10)
```


```python
np.array([[cov(X, X), cov(X, Y)], [cov(Y, X), cov(Y,Y)]])
```




    array([[ 0.08255874, -0.009372  ],
           [-0.009372  ,  0.08437116]])




```python
# This can of course be calculated using numpy's built in cov() function
np.cov(X, Y)
```




    array([[ 0.08255874, -0.009372  ],
           [-0.009372  ,  0.08437116]])




```python
# Extension to more variables is done in a pair-wise way
Z = np.random.random(10)
np.cov([X, Y, Z])
```




    array([[ 0.08255874, -0.009372  ,  0.02351863],
           [-0.009372  ,  0.08437116, -0.02369603],
           [ 0.02351863, -0.02369603,  0.12269876]])



Eigendecomposition of the covariance matrix
----


```python
mu = [0,0]
sigma = [[0.6,0.2],[0.2,0.2]]
n = 1000
x = np.random.multivariate_normal(mu, sigma, n).T
```


```python
A = np.cov(x)
```


```python
m = np.array([[1,2,3],[6,5,4]])
ms = m - m.mean(1).reshape(2,1)
np.dot(ms, ms.T)/2
```




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




```python
e, v = np.linalg.eig(A)
```


```python
plt.scatter(x[0,:], x[1,:], alpha=0.2)
for e_, v_ in zip(e, v.T):
    plt.plot([0, 3*e_*v_[0]], [0, 3*e_*v_[1]], 'r-', lw=2)
plt.axis([-3,3,-3,3])
plt.title('Eigenvectors of covariance matrix scaled by eigenvalue.');
```

Covariance matrix as a linear transformation
----

The covariance matrix is a linear transformation that maps $\mathbb{R}^n$ in the direction of its eigenvectors with scaling factor given by the eigenvalues. Here we see it applied to a collection of random vectors in the box bounded by [-1, 1].

### We will assume we have a covariance matrix


```python
covx = np.array([[1,0.6],[0.6,1]])
```

### Create random vectors in a box


```python
u = np.random.uniform(-1, 1, (100, 2)).T
```

### Apply covariance matrix as linear transformation


```python
y = covx @ u
```


```python
e1, v1 = np.linalg.eig(covx)
```

### The linear transform maps the random vectors as described.


```python
plt.scatter(u[0], u[1], c='blue')
plt.scatter(y[0], y[1], c='orange')
for e_, v_ in zip(e1, v1.T):
    plt.plot([0, e_*v_[0]], [0, e_*v_[1]], 'r-', lw=2)
plt.xticks([])
plt.yticks([])
pass
```

PCA
----

Principal Components Analysis (PCA) basically means to find and rank all the eigenvalues and eigenvectors of a covariance matrix. This is useful because high-dimensional data (with $p$ features) may have nearly all their variation in a small number of dimensions $k$, i.e. in the subspace spanned by the eigenvectors of the covariance matrix that have the $k$ largest eigenvalues. If we project the original data into this subspace, we can have a dimension reduction (from $p$ to $k$) with hopefully little loss of information.

Numerically, PCA is typically done using SVD on the data matrix rather than eigendecomposition on the covariance matrix. The next section explains why this works.

### Data matrices that have zero mean for all feature vectors

\begin{align}
\text{Cov}(X, Y) &= \frac{\sum_{i=1}^n(X_i - \bar{X})(Y_i - \bar{Y})}{n-1} \\
  &= \frac{\sum_{i=1}^nX_iY_i}{n-1} \\
  &= \frac{XY^T}{n-1}
\end{align}

and so the covariance matrix for a data set X that has zero mean in each feature vector is just $XX^T/(n-1)$. 

In other words, we can also get the eigendecomposition of the covariance matrix from the positive semi-definite matrix $XX^T$.

### Note that zeroing the feature vector does not affect the covariance matrix


```python
np.set_printoptions(precision=3)
```


```python
X = np.random.random((5,4))
X
```




    array([[ 0.224,  0.136,  0.364,  0.189],
           [ 0.79 ,  0.007,  0.486,  0.682],
           [ 0.349,  0.013,  0.484,  0.094],
           [ 0.771,  0.924,  0.636,  0.692],
           [ 0.33 ,  0.01 ,  0.439,  0.183]])




```python
### Subtract the row mean from each row
```


```python
Y = X - X.mean(1)[:, None]
```


```python
Y.mean(1)
```




    array([  0.000e+00,  -2.776e-17,   0.000e+00,   2.776e-17,   0.000e+00])




```python
Y
```




    array([[-0.004, -0.092,  0.136, -0.039],
           [ 0.298, -0.484, -0.005,  0.191],
           [ 0.114, -0.222,  0.249, -0.141],
           [ 0.015,  0.168, -0.119, -0.064],
           [ 0.089, -0.23 ,  0.199, -0.058]])




```python
### Calculate the covariance
```


```python
np.cov(X)
```




    array([[ 0.01 ,  0.012,  0.02 , -0.01 ,  0.017],
           [ 0.012,  0.12 ,  0.038, -0.029,  0.042],
           [ 0.02 ,  0.038,  0.048, -0.019,  0.04 ],
           [-0.01 , -0.029, -0.019,  0.016, -0.019],
           [ 0.017,  0.042,  0.04 , -0.019,  0.035]])




```python
np.cov(Y)
```




    array([[ 0.01 ,  0.012,  0.02 , -0.01 ,  0.017],
           [ 0.012,  0.12 ,  0.038, -0.029,  0.042],
           [ 0.02 ,  0.038,  0.048, -0.019,  0.04 ],
           [-0.01 , -0.029, -0.019,  0.016, -0.019],
           [ 0.017,  0.042,  0.04 , -0.019,  0.035]])



Eigendecomposition of the covariance matrix
----


```python
e1, v1 = np.linalg.eig(np.dot(x, x.T)/(n-1))
```


```python
plt.scatter(x[0,:], x[1,:], alpha=0.2)
for e_, v_ in zip(e1, v1.T):
    plt.plot([0, 3*e_*v_[0]], [0, 3*e_*v_[1]], 'r-', lw=2)
plt.axis([-3,3,-3,3]);
```

Change of basis via PCA
----

### We can transform the original data set so that the eigenvectors are the basis vectors and find the new coordinates of the data points with respect to this new basis

This is the change of basis transformation covered in the Linear Alegebra module. First, note that the covariance matrix is a real symmetric matrix, and so the eigenvector matrix is an orthogonal matrix. 


```python
e, v = np.linalg.eig(np.cov(x))
v.dot(v.T)
```




    array([[ 1.,  0.],
           [ 0.,  1.]])



### Linear algebra review for change of basis

Graphical illustration of change of basis
----



Suppose we have a vector $u$ in the standard basis $B$ , and a matrix $A$ that maps $u$ to $v$, also in $B$. We can use the eigenvalues of $A$ to form a new basis $B'$. As explained above, to bring a vector $u$ from $B$-space to a vector $u'$ in $B'$-space, we multiply it by $Q^{-1}$, the inverse of the matrix having the eigenvctors as column vectors. Now, in the eigenvector basis, the equivalent operation to $A$ is the diagonal matrix $\Lambda$ - this takes $u'$ to $v'$. Finally, we convert $v'$ back to a vector $v$ in the standard basis by multiplying with $Q$.


```python
ys = np.dot(v1.T, x)
```

#### Principal components

Principal components are simply the eigenvectors of the covariance matrix used as basis vectors. Each of the original data points is expressed as a linear combination of the principal components, giving rise to a new set of coordinates. 


```python
plt.scatter(ys[0,:], ys[1,:], alpha=0.2)
for e_, v_ in zip(e1, np.eye(2)):
    plt.plot([0, 3*e_*v_[0]], [0, 3*e_*v_[1]], 'r-', lw=2)
plt.axis([-3,3,-3,3]);
```

For example, if we only use the first column of `ys`, we will have the projection of the data onto the first principal component, capturing the majority of the variance in the data with a single feature that is a linear combination of the original features.

#### Transform back to original coordinates

We may need to transform the (reduced) data set to the original feature coordinates for interpretation. This is simply another linear transform (matrix multiplication).


```python
zs = np.dot(v1, ys)
```


```python
plt.scatter(zs[0,:], zs[1,:], alpha=0.2)
for e_, v_ in zip(e1, v1.T):
    plt.plot([0, 3*e_*v_[0]], [0, 3*e_*v_[1]], 'r-', lw=2)
plt.axis([-3,3,-3,3]);
```


```python
u, s, v = np.linalg.svd(x)
u.dot(u.T)
```




    array([[ 1.,  0.],
           [ 0.,  1.]])



Dimension reduction via PCA
----

We have the sepctral decomposition of the covariance matrix

$$
A = Q^{-1}\Lambda Q
$$

Suppose $\Lambda$ is a rank $p$ matrix. To reduce the dimensionality to $k \le p$, we simply set all but the first $k$ values of the diagonal of $\Lambda$ to zero. This is equivalent to ignoring all except the first $k$ principal components.

What does this achieve? Recall that $A$ is a covariance matrix, and the trace of the matrix is the overall variability, since it is the sum of the variances.


```python
A
```




    array([[ 0.605,  0.202],
           [ 0.202,  0.209]])




```python
A.trace()
```




    0.81349656039067819




```python
e, v = np.linalg.eig(A)
D = np.diag(e)
D
```




    array([[ 0.69 ,  0.   ],
           [ 0.   ,  0.124]])




```python
D.trace()
```




    0.81349656039067819




```python
D[0,0]/D.trace()
```




    0.84806267856011852



Since the trace is invariant under change of basis, the total variability is also unchanged by PCA. By keeping only the first $k$ principal components, we can still "explain" $\sum_{i=1}^k e[i]/\sum{e}$ of the total variability. Sometimes, the degree of dimension reduction is specified as keeping enough principal components so that (say) $90\%$ of the total variability is explained.

### Using Singular Value Decomposition (SVD) for PCA

SVD is a decomposition of the data matrix $X = U S V^T$ where $U$ and $V$ are orthogonal matrices and $S$ is a diagnonal matrix. 

Recall that the transpose of an orthogonal matrix is also its inverse, so if we multiply on the right by $X^T$, we get the follwoing simplification

\begin{align}
X &= U S V^T \\
X X^T &= U S V^T (U S V^T)^T \\
 &= U S V^T V S U^T \\
 &= U S^2 U^T
\end{align}

Compare with the eigendecomposition of a matrix $A = W \Lambda W^{-1}$, we see that SVD gives us the eigendecomposition of the matrix $XX^T$, which as we have just seen, is basically a scaled version of the covariance for a data matrix with zero mean, with the eigenvectors given by $U$ and eigenvealuse by $S^2$ (scaled by $n-1$)..



```python
u, s, v = np.linalg.svd(x)
```


```python
e2 = s**2/(n-1)
v2 = u
plt.scatter(x[0,:], x[1,:], alpha=0.2)
for e_, v_ in zip(e2, v2):
    plt.plot([0, 3*e_*v_[0]], [0, 3*e_*v_[1]], 'r-', lw=2)
plt.axis([-3,3,-3,3]);
```


```python
v1 # from eigenvectors of covariance matrix
```




    array([[ 0.922, -0.387],
           [ 0.387,  0.922]])




```python
v2 # from SVD
```




    array([[-0.922, -0.387],
           [-0.387,  0.922]])




```python
e1 # from eigenvalues of covariance matrix
```




    array([ 0.693,  0.124])




```python
e2 # from SVD
```




    array([ 0.693,  0.124])




```python
a0 = np.random.normal(0,1,100)
a1 = a0 + np.random.normal(0,.5,100)
a2 = 2*a0 + a1 + np.random.normal(5,0.01,100)
xs = np.vstack([a0, a1, a2])
xs.shape
```




    (3, 100)




```python
U, s, V = np.linalg.svd(xs)
```


```python
(s**2)/(99)
```




    array([ 36.809,   1.658,   0.125])




```python
U
```




    array([[-0.099, -0.675, -0.731],
           [-0.113, -0.723,  0.682],
           [-0.989,  0.149, -0.005]])



51109fcd07c1caaebed2b45f6804943e3e486561
ipynb
Jupyter Notebook
notebook/13D_PCA.ipynb
cliburn/sta-663-2017
89e059dfff25a4aa427cdec5ded755ab456fbc16
MIT
2017-01-11T03:16:00.000Z
2021-01-15T05:28:48.000Z
notebook/13D_PCA.ipynb
slimdt/Duke_Stat633_2017
89e059dfff25a4aa427cdec5ded755ab456fbc16
MIT
2017-04-16T17:10:49.000Z
2017-04-16T19:13:03.000Z
notebook/13D_PCA.ipynb
slimdt/Duke_Stat633_2017
89e059dfff25a4aa427cdec5ded755ab456fbc16
MIT
2017-01-13T04:50:54.000Z
2021-06-23T11:48:33.000Z
Qwen/Qwen-72B
1. YES
2. YES