Principal Component Analysis (PCA)

NOTE

This is part of the 10th homework, titled Dimensionality Reduction 1, for the course Machine Learning (IN2064) in the Winter Semester 2024/25 at TUM.

Problem 3

Let the matrix $\mathbf{X}\in {\mathbb{R}}^{N\times D}$ represent $N$ data points of dimension $D=10$ (samples stored as rows). We applied PCA to $\mathbf{X}$. By using the $K=5$ top principal components, we transformed/projected $\mathbf{X}$ into $\tilde{\mathbf{X}}\in {\mathbb{R}}^{N\times K}$. We computed that $\tilde{\mathbf{X}}$ preserves 70% of the variance of the original data $\mathbf{X}$.

Suppose now we apply PCA on the following matrices:

• a) ${\mathbf{Y}}_1=\mathbf{XS}$ where $\mathbf{S}=\lambda \mathbf{I}$, with $\lambda \in \mathbb{R}$ and $\mathbf{I}\in {\mathbb{R}}^{D\times D}$ is the identity matrix
• b) ${\mathbf{Y}}_2=\mathbf{XR}$ where $\mathbf{R}\in {\mathbb{R}}^{D\times D}$ and $\mathbf{R}{\mathbf{R}}^T=\mathbf{I}$
• c) ${\mathbf{Y}}_3=\mathbf{XP}$ where $\mathbf{P}=\text{diag}(+5,-5,\dots ,+5,-5)$ is a $D\times D$ diagonal matrix
• d) ${\mathbf{Y}}_4=\mathbf{XQ}$ where $\mathbf{Q}=\text{diag}(1,2,3,\dots ,D-1,D)$ is a $D\times D$ diagonal matrix
• e) ${\mathbf{Y}}_5=\mathbf{X}+1_N{\mathbf{\mu }}^T$ where $\mathbf{\mu }\in {\mathbb{R}}^D$ and $1_N$ is an $N$-dimensional column vector of all ones
• f) ${\mathbf{Y}}_6=\mathbf{XA}$ where $\mathbf{A}\in {\mathbb{R}}^{D\times D}$ and $\text{rank}(\mathbf{A})=5$

and obtain the projected data ${\tilde{\mathbf{Y}}}_1,\dots ,{\tilde{\mathbf{Y}}}_6\in {\mathbb{R}}^{N\times K}$ using the principal components corresponding to the top $K=5$ largest eigenvalues of the respective ${\mathbf{Y}}_i$. What fraction of variance of each ${\mathbf{Y}}_i$ will be preserved by each respective ${\tilde{\mathbf{Y}}}_i$? Justify your answer. The answer “cannot tell without additional information” is also valid if you provide a justification.

Solution:

a) ${\mathbf{Y}}_1=\mathbf{XS}$ where $\mathbf{S}=\lambda \mathbf{I}$, with $\lambda \in \mathbb{R}$ and $\mathbf{I}\in {\mathbb{R}}^{D\times D}$ is the identity matrix

The goal of the PCA is to decompose the data $X$ into $\Gamma \Lambda {\Gamma }^{\top }$ where $\Gamma$ is the matrix of eigenvectors and $\Lambda$ is diagonal matrix of the corresponding eigenvalues ordered in a decreasing order after taking their absolute value. As such PCA decomposition of $Y_1$ would go as follows:

$$Y_1=X\lambda I=\Gamma \Lambda {\Gamma }^{\top }\lambda I=\Gamma \lambda \Lambda {\Gamma }^{\top }$$

Now, when we do dimensionality reduction by leaving zeroing all but first $K$ columns of $\Lambda$. Recall, that the eigenvalues correspond to the variance on a given dimension. Given that the sum of top $K$ eigenvalues of $X$ was equal to the 70% of the all eigenvalues, then after multiplication by a constant $\lambda$ this property will still hold. As, such we can conclude that $\widetilde{Y_1}$ will preserve also 70% of the variance.

b) ${\mathbf{Y}}_2=\mathbf{XR}$ where $\mathbf{R}\in {\mathbb{R}}^{D\times D}$ and $\mathbf{R}{\mathbf{R}}^T=\mathbf{I}$

The description of the matrix $\mathbf{R}$ tells as that is an orthogonal matrix. We know that, orthogonal linear maps preserve the inner product of vectors. So they do not change the eigenvalues, as no scaling happens. Therefore, again $\widetilde{Y_2}$ will preserve the same proportion of variance as does $\tilde{X}$ which in the case of this question is 70%.

c) ${\mathbf{Y}}_3=\mathbf{XP}$ where $\mathbf{P}=\text{diag}(+5,-5,\dots ,+5,-5)$ is a $D\times D$ diagonal matrix

The linear map $P$ scales every dimension of the input space by five and inverts the evenly indexed ones. This has no impact on the magnitude of eigenvalues other than the one discussed in the point a) and as such the same proportion of variance is preserved as in the case of $\tilde{X}$.

d) ${\mathbf{Y}}_4=\mathbf{XQ}$ where $\mathbf{Q}=\text{diag}(1,2,3,\dots ,D-1,D)$ is a $D\times D$ diagonal matrix

Here linear map $Q$ scales each dimension by a different factor, this in turn scales eigenvalues by different factors too and thus we cannot tell what proportion of variance will be ultimately preserved.

e) ${\mathbf{Y}}_5=\mathbf{X}+1_N{\mathbf{\mu }}^T$ where $\mathbf{\mu }\in {\mathbb{R}}^D$ and $1_N$ is an $N$-dimensional column vector of all ones

The addition of $1_N{\mathbf{\mu }}^T$ doesn’t impact the PCA decomposition as the first step of the PCA method is to center the data.

f) ${\mathbf{Y}}_6=\mathbf{XA}$ where $\mathbf{A}\in {\mathbb{R}}^{D\times D}$ and $\text{rank}(\mathbf{A})=5$

Here, we are multiplying by a matrix A which is of rank 5, this results in a rank of $Y_6$ being at most 5. Thus it will have at most 5 eigenvectors and therefore if we decrease dimensionality of the data to 5 then we can’t lose variance, i.e. we are preservering 100% of it.

Problem 4

You are given $N=4$ data points: $\{{\mathbf{x}}_i{\}}_{i=1}^4,{\mathbf{x}}_i\in {\mathbb{R}}^3$, represented with the matrix $\mathbf{X}\in {\mathbb{R}}^{4\times 3}$.

$$\mathbf{X}=\left[\begin{array}{ccc}4& 3& 2\\ 2& 1& -2\\ 4& -1& 2\\ -2& 1& 2\end{array}\right]$$

Hint: In this task the results of all (final and intermediate) computations happen to be integers.

• a) Perform principal component analysis (PCA) of the data $\mathbf{X}$, i.e. find the principal components and their associated variances in the transformed coordinate system. Show your work.
• b) Project the data to two dimensions, i.e. write down the transformed data matrix $\mathbf{Y}\in {\mathbb{R}}^{4\times 2}$ using the top-2 principal components you computed in (a). What fraction of variance of $\mathbf{X}$ is preserved by $\mathbf{Y}$?
• c) Let ${\mathbf{x}}_5\in {\mathbb{R}}^3$ be a new data point. Specify the vector ${\mathbf{x}}_5$ such that performing PCA on the data including the new data point $\{{\mathbf{x}}_i{\}}_{i=1}^5$ leads to exactly the same principal components as in (a).

Solution

a) Perform principal component analysis (PCA) of the data $\mathbf{X}$, i.e. find the principal components and their associated variances in the transformed coordinate system. Show your work.

Step 1: Center the data: Each row is in the matrix $X$ is a data-point. As such, we center the data by subtracting an average data-point from row: $\hat{X}=\left[\begin{array}{ccc}4& 3& 2\\ 2& 1& -2\\ 4& -1& 2\\ -2& 1& 2\end{array}\right]-\left[\begin{array}{c}1\\ 1\\ 1\\ 1\end{array}\right]\left[\begin{array}{ccc}2& 1& 1\end{array}\right]=\left[\begin{array}{ccc}2& 2& 1\\ 0& 0& -3\\ 2& -2& 1\\ -4& 0& 1\end{array}\right]$

Step 2: Compute covariance matrix: Recall covariance between two random variables is given by:

$$co{v}_{x,y}=\frac{\sum (x_i-\hat{x})(y_j-\hat{y})}{N-1}$$

Then a covariance matrix is given as follows:

$${\mathbf{\Sigma }}_{\mathbf{X}}=\left[\begin{array}{cccc}\text{Var}({\mathbf{X}}_1)& \text{Cov}({\mathbf{X}}_1,{\mathbf{X}}_2)& \dots & \text{Cov}({\mathbf{X}}_1,{\mathbf{X}}_d)\\ \text{Cov}({\mathbf{X}}_2,{\mathbf{X}}_1)& \text{Var}({\mathbf{X}}_2)& \dots & ⋮\\ ⋮& ⋮& \ddots & ⋮\\ \text{Cov}({\mathbf{X}}_d,{\mathbf{X}}_1)& \dots & \dots & \text{Var}({\mathbf{X}}_d)\end{array}\right]=\frac{1}{N}{\mathbf{X}}^T\mathbf{X}-\hat{\mathbf{X}}{\hat{\mathbf{X}}}^T$$

We will use the right most part of the equality, especially since we can disregard $\hat{\mathbf{X}}{\hat{\mathbf{X}}}^T$ having centered the data in the step one. Thus,

$$\begin{array}{r}{\mathbf{\Sigma }}_{\hat{\mathbf{X}}}=\frac{1}{N}{\mathbf{X}}^T\mathbf{X}=\\ =\frac{1}{4}\left[\begin{array}{cccc}2& 0& 2& -4\\ 2& 0& -2& 0\\ 1& -3& 1& 1\end{array}\right]\left[\begin{array}{ccc}2& 2& 1\\ 0& 0& -3\\ 2& -2& 1\\ -4& 0& 1\end{array}\right]=\\ =\frac{1}{4}\left[\begin{array}{ccc}4+0+4+16& 4+0-4+0& 2+0+2-4\\ 4+0-4+0& 4+0+4+0& 2+0-2+0\\ 2+0+2-4& 2+0-3+0& 1+9+1+1\end{array}\right]=\\ =\frac{1}{4}\left[\begin{array}{ccc}24& 0& 0\\ 0& 8& 0\\ 0& 0& 12\end{array}\right]=\\ =\left[\begin{array}{ccc}6& 0& 0\\ 0& 2& 0\\ 0& 0& 3\end{array}\right]\end{array}$$

Step 3: find the eigenvector as and perform the decomposition. Normally we would use the power Iteration a.k.a Von Mises iteration, however since our covariance matrix is already diagonal we get the eigenvectors and their eigenvalues for free! The eigenvalues:

$${\lambda }_1=6,{\lambda }_2=2,{\lambda }_3=3$$

and their corresponding eigenvectors:

$$v_1=\left[\begin{array}{c}1\\ 0\\ 0\end{array}\right],v_2=\left[\begin{array}{c}0\\ 1\\ 0\end{array}\right],v_3=\left[\begin{array}{c}0\\ 0\\ 1\end{array}\right]$$

One thing to remember when decomposing $X$ into $c$ is that the eigenvalues in the $\Lambda$ matrix have to ordered in decreasing oder with respect to their absolute values. So the final decomposition is given by:

$${\mathbf{\Sigma }}_{\hat{\mathbf{X}}}=\Gamma \Lambda {\Gamma }^T=\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}6& 0& 0\\ 0& 3& 0\\ 0& 0& 2\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]$$

b) Project the data to two dimensions, i.e. write down the transformed data matrix $\mathbf{Y}\in {\mathbb{R}}^{4\times 2}$ using the top-2 principal components you computed in (a). What fraction of variance of $\mathbf{X}$ is preserved by $\mathbf{Y}$? The projection comes down to multiplication of the centered data with the first two columns of the of the $\Gamma$ matrix:

$$Y=\hat{X}\Gamma =\left[\begin{array}{ccc}2& 2& 1\\ 0& 0& -3\\ 2& -2& 1\\ -4& 0& 1\end{array}\right]\left[\begin{array}{cc}1& 0\\ 0& 0\\ 0& 1\end{array}\right]=\left[\begin{array}{cc}2& 1\\ 0& -3\\ 2& 1\\ -4& 1\end{array}\right]$$

Now, the $\Lambda$ matrix is a covariance matrix of the new space. We can use this fact with to calculate the percentage of preserved variance:

$$\begin{array}{rl}\text{Total variance}& ={\lambda }_1+{\lambda }_2+{\lambda }_3=11\\ \text{Preserved variance}& ={\lambda }_1+{\lambda }_3=9\\ \text{Fraction of preserved variance}& =\frac{9}{11}\approx 82\%\end{array}$$

c) Let ${\mathbf{x}}_5\in {\mathbb{R}}^3$ be a new data point. Specify the vector ${\mathbf{x}}_5$ such that performing PCA on the data including the new data point $\{{\mathbf{x}}_i{\}}_{i=1}^5$ leads to exactly the same principal components as in (a).

The idea here is to choose a vector such that it doesn’t change the eigenvalues of the covariance matrix, i.e. at most it scales the values of the covariance matrix. We can do that by choosing the vector that is the mean of the all the pre-existing vectors. In our case that would be:

$$x_5=\left[\begin{array}{ccc}2& 1& 1\end{array}\right]$$

Then after centering it will be zeroed-out, and thus it will not impact covariance matrix other than rescaling its values as we have increased number of data-points by one so the preceding scaling factor of the covariance matrix is no longer $\frac{1}{4}$ but $\frac{1}{5}$.