PCA Algorithm

Frederik Mallmann-Trenn
6CCS3AIN

c Frederik Mallmann-Trenn, King’s College London 1

PCA Algorithm - Data

Let’s say this is our data matrix (say our houses), where each data point is an
d-dimensional row vector.
¨ ˛
˚ xT1 ‹
˚ ‹
˚ ‹
xT2
˚ ‹
˚ ‹
X“˚ ‹
..
˚ ‹
˚ ‹
˚
˚ . ‹
‹
˝ ‚
xTn
The dimensions are n ˆ d

c Frederik Mallmann-Trenn, King’s College London 2

PCA Algorithm

1
řn
Step 1: Compute the mean row vector x̄ “ n i“1 xi
¨ ˛ ¨ ˛
˚1‹ ˚ x̄T ‹
˚ ‹ ˚ ‹
˚ ‹ ˚ ‹
x̄T
˚ ‹ ˚ ‹
˚1‹ T ˚ ‹
Step 2: Compute the mean row matrix X̄ “ ˚ ‹ ¨ x̄ “ ˚
˚ ‹ ‹
˚ .. ‹ ..
˚ ‹
˚ ‹
˚.‹ ˚ . ‹
˚ ‹ ˚ ‹
˝ ‚ ˝ ‚
1 x̄T
The dimensions are n ˆ d

c Frederik Mallmann-Trenn, King’s College London 3

PCA Algorithm

Step 3: Subtract mean (obtain mean centred data)

B “ X ´ X̄

The dimensions are n ˆ d

Example:

50 50
40 40
30 30
20 20
10 10

-3 -2 -1 1 2 3 4 5 6 7 -3 -2 -1 1 2 3 4 5 6 7
-10 -10
-20 -20
-30 -30

c Frederik Mallmann-Trenn, King’s College London 4

PCA Algorithm

Step 4: Compute the covariance matrix of rows of B

1 T
C“ B B
n
The dimensions are pn ˆ dqT ˆ pn ˆ dq “ pd ˆ nq ˆ pn ˆ dq “ d ˆ d

c Frederik Mallmann-Trenn, King’s College London 5

PCA Algorithm

Step 5: Compute the k largest eigenvectors v1 , v1 , . . . , vk of C (not covered how

to do this in this module. You use Python or WolframAlpha).
Each eigenvector has dimensions 1 ˆ d
Pro tip: Python doesn’t sort the eigenvectors for you. Sort eigenvectors by decreasing order of eigenvalues.

Step 6: Compute matrix W of k-largest eigenvectors

¨ ˛
˚ ‹
˚ ‹
˚ ‹
W“˚
˚ v1 v2 ...
‹
vk ‹
˚ ‹
˝ ‚

Dimensions of W are pd ˆ kq.

c Frederik Mallmann-Trenn, King’s College London 6

PCA Algorithm

Step 7: Multiply each datapoint xi for i P t1, 2, . . . , nu with WT

yi “ WT ¨ xi

Dimensions of yi are pk ˆ dq ˆ pd ˆ 1q “ k ˆ 1

c Frederik Mallmann-Trenn, King’s College London 7

PCA Algorithm

Step 7: Multiply each datapoint xi for i P t1, 2, . . . , nu with WT

yi “ WT ¨ xi

Dimensions of yi are pk ˆ dq ˆ pd ˆ 1q “ k ˆ 1
Congratulations! You’ve reduced the number of dimensions from d to k!

c Frederik Mallmann-Trenn, King’s College London 8

Why do we compute the covariance matrix?

50
40
v1
30
20 λ1

10

-3 -2 -1 λ2 1 2 3 4 5 6 7
-10 v2
-20
Example illustration: -30

The covariance matrix measures the correlation between pairs of features.

Finding the largest eigenvectors allows us to explain most of the variance in data
The more variance is explained by the eigenvectors, the more important they are

c Frederik Mallmann-Trenn, King’s College London 9

Why do we compute the covariance matrix?

We can measure the explained variance by considering the quantity

řr
i“1 λi
řd
i“1 λi

Example:

c Frederik Mallmann-Trenn, King’s College London 10