Principal Component Analysis

Ngoc Hoang Luong

University of Information Technology (UIT), VNU-HCM

January 13, 2025

References

The contents of the slides are from: Gaston Sanchez and Ethan
Marzban: All Models Are Wrong: Concepts of Statistical Learning -
[Link]

2 / 26
Low-dimensional Representations

● Individuals form a cloud of points in a p-dim space. Variables form

a cloud of arrows in an n-dim space.
● Suppose some data in which its cloud of points form a mug:

● Is there away to get a low-dimensional representation of this data?

3 / 26
Low-dimensional Representations

● We can look for projections of the data into sub-spaces of lower

dimension.
● Assume we take a photo of the mug from different angles. What is
the best angle to take a photo to get the images of the mug as
similar as possible to the mug?
4 / 26
Low-dimensional Representations

● Among 03 projections HA , HB , HC , the subspace HC provides the

best low-dimensional representation.
● The resulting image in low-dimensional space is not capturing the
whole pattern: there is always some loss of information.
● Choosing the right projection, we try to minimize such loss.
5 / 26
Projections

● Data points are in a p-dimensional space, and the cloud has its
centroid g.
● We first try the simplest low-dimensional space: a 1D space, which
can be displayed as one axis, denoted as dimv .

6 / 26
Projections

● Data points are in a p-dimensional space, and the cloud has its
centroid g.
● We first try the simplest low-dimensional space: a 1D space, which
can be displayed as one axis, denoted as dimv .

7 / 26
Projections

● Data points are in a p-dimensional space, and the cloud has its
centroid g.
● We first try the simplest low-dimensional space: a 1D space, which
can be displayed as one axis, denoted as dimv .
● We manipulate dimv via a vector v along this dimension.

8 / 26
Projections

● Data points are in a p-dimensional space, and the cloud has its
centroid g.
● We first try the simplest low-dimensional space: a 1D space, which
can be displayed as one axis, denoted as dimv .
● We manipulate dimv via a vector v along this dimension.
● We want to project orthogonally the individuals onto this
dimension.

9 / 26
Vector and Scalar Projections

● Take the centroid g as the origin of the clouds of points.

● The dimension that we look for has to pass through the origin.
● Obtain the orthogonal projection of the i-th individual onto dimv
is projecting xi onto any vector v along this dimension.

10 / 26
Vector and Scalar Projections

● The vector projection of xi onto v is:

v ⊺ xi
v̂ = v
v⊺ v
● The scalar projection of xi onto v is:
v ⊺ xi
zik =
∥v∥
● We would prefer the scalar projection to obtain the co-ordinate of
xi along this axis.
11 / 26
Projected Inertia

● Find the angle that give the best photo of the object ⇐⇒ Find
the subspace that the distances between the points are the most
similar to the original points.
● The overall dispersion of the original data is: ∑ni=1 ∑nl=1 d2 (i, l). We
try to find a subspace H such that:
n n n n
∑ ∑ d (i, l) ≈ ∑ ∑ dH (i, l)
2 2
i=1 l=1 i=1 l=1

12 / 26
Projected Inertia

● The overall dispersion is related to the inertia as:

n n n
1 n 2
∑ ∑ d (i, l) = 2n ∑ d (i, g) = 2n ∑ d (i, g) = 2n Inertia
2 2 2 2
i=1 l=1 i=1 n i=1

● Finding the subspace H that yields similar distances to the original

subspace corresponds to maximize the projected inertia:

1 n
max { ∑ d2H (i, g)}
H n i=1

13 / 26
Projected Inertia

● We are consider 1D case, H ⊆ R1 , the projected inertia becomes:

1 n 2 1 n ⊺ 2 1 n 2
∑ dH (i, g) = ∑(xi v) = ∑ zi
n i=1 n i=1 n i=1
● Our maximization problem becomes:
1 n
max { ∑(x⊺i v)2 } s.t. v⊺ v = 1
v n i=1
● We constraint v to be a unit vector; otherwise, the maximization
objective is unbounded.
14 / 26
Maximization Problem
● Assume mean-centered data, the centroid g of the cloud of points
is the origin g = 0.
● We are projecting onto a line spanned by a unit-vector v, the
projected inertia IH is the variance of the projected data points:

1 n 2 1 n ⊺ 2
IH = ∑ dH (i, 0) = ∑(xi v)
n i=1 n i=1
1 n 2 1 ⊺ 1 ⊺ ⊺
= ∑ zi = z z = v X Xv
n i=1 n n

where
⎡− − −x⊺ − −−⎤ v1
⎛ z1 ⎞ ⎢ ⎥
⎢− − −x⊺ − −−⎥ ⎛v ⎞
1
⎜ z2 ⎟ ⎢ ⎥ ⎜ 2⎟
z = ⎜ ⎟ = Xv = ⎢ 2 ⎥⎜ ⎟
⎜⋮⎟ ⎢− − − − − − −⎥ ⎜ ⋮ ⎟
⎝zn ⎠ ⎢ ⎥
⎢− − −x⊺ − −−⎥ ⎝vp ⎠
⎣ n ⎦

15 / 26
Maximization Problem
● The maximization problem becomes:

1
max { v⊺ X⊺ Xv} s.t. v⊺ v = 1
v n
● To solve this maximization, problem, we use Lagrange multipliers.

1 ⊺ ⊺
L= v X Xv − λ(v⊺ v − 1)
n
● Set the derivative of the Lagrangian L wrt v to 0:

∂L 2 ⊺ 1
= X Xv − 2λv = 0 ⇒ X⊺ X v = λv ⇒ Sv = λv
∂v n n
´¹¹ ¹ ¹ ¹¸ ¹ ¹ ¹ ¹ ¶
S∈Rp×p

● This means that v is an eigenvector (with eigenvalue λ) of S.

● λ is the value of the projected inertia IH that we want to maximize.

16 / 26
Eigenvectors of S
● Assume X is full rank (rank(X) = p). We have p eigenvectors:
V = [v1 v2 . . . vk . . . vp ]
● We also have the matrix of eigenvalues Λ = diag{λi }ni=1
⎡λ1 0 . . . 0 ⎤
⎢ ⎥
⎢ 0 λ ... 0 ⎥
⎢ 2 ⎥
Λ=⎢ ⎥
⎢⋮ ⋮ ⋱ ⋮ ⎥
⎢ ⎥
⎢ 0 0 . . . λp ⎥
⎣ ⎦
● We then have the matrix of projected points Z (also known as the
matrix of principal components (PC’s)):
Z = [z1 z2 . . . zk . . . zp ]
where the k-th principal component zk is:
zk = Xvk = v1k x1 + v2k x2 + . . . + vpk xp
with xk denotes columns of X.
17 / 26
Eigenvalues of S

● Because the data is mean-centered, we have mean(xi ) = 0. Then,

mean(zk ) = 0.
● How about the variance of zk ?

1 ⊺ 1 1
V ar(zk ) = z z = (Xvk )⊺ (Xvk ) = vk⊺ X⊺ Xvk
n n n
= vk Svk = vk (λk vk ) = λk (vk vk ) = λk
⊺ ⊺ ⊺

● The k-th eigenvalue of S is the variance of the k-th principal

component.
● If X is mean centered, S = n1 X⊺ X is the covariance matrix of data.
● If X is standardized (mean-centered and scaled by the variance),
then S is the correlation matrix.

18 / 26
Eigenvalues of S

1 n 2 1 ⊺
Inertia = ∑ d (i, g) = ∑ λk = tr ( X X)
n i=1 k n

● ∑pk=1 λk relates to the total amount of variability in the data.

● The principal components capture different parts of the variability
in the data.

19 / 26
Principal Component Analysis (PCA)
● Given a set of p variables x1 , x2 , . . . , xp , we want to obtain new k
variables z1 , z2 , . . . , zk , called the Principal Components (PCs).
● A principal component is a linear combination of the p variables:
z = Xv.
● The first PC is a linear combination:

20 / 26
Principal Component Analysis (PCA)
● Given a set of p variables x1 , x2 , . . . , xp , we want to obtain new k
variables z1 , z2 , . . . , zk , called the Principal Components (PCs).
● A principal component is a linear combination of the p variables:
z = Xv.
● The second PC is another linear combination:

21 / 26
Principal Component Analysis (PCA)
● Given a set of p variables x1 , x2 , . . . , xp , we want to obtain new k
variables z1 , z2 , . . . , zk , called the Principal Components (PCs).
● A principal component is a linear combination of the p variables:
z = Xv.
● We compute PCs as linear combinations of original variables:

z1 = v11 x1 + v21 x2 + . . . + vp1 xp

z2 = v12 x1 + v22 x2 + . . . + vp2 xp
⋮=⋮
zk = v1k x1 + v2k x2 + . . . + vpk xp

Or:
Z = XV
where Z is an n × k matrix of principal components, and V is a
p × k matrix of weights (directional vectors of the principal axes).
22 / 26
Principal Component Analysis (PCA)

23 / 26
Finding Principal Components
● The components z1 , z2 , . . . , zk are required to capture most of the
variation in data X.
● We look for a vector vh such that a component zh = Xvh has
maximum variance:
1
max var(zh ) ⇒ max var(Xvh ) ⇒ max vh⊺ X⊺ Xvh
vh vh vh n

● If vh can be arbitrarily big, the problem is unbounded. We need to

restrict vh to be of unit norm:
∥vh ∥ = 1 ⇒ vh⊺ vh = 1
● If we denote the covariance matrix S = (1/n)X⊺ X, then

max vh⊺ Svh s.t. vh⊺ vh = 1

vh

● To avoid redundancy, we require z⊺h zl = 0 mutually orthogonal if

h ≠ l.
24 / 26
Finding Principal Components
All PCs can be found by diagonalizing S = (1/n)X⊺ X.

S = VΛV⊺

● Λ is a diagonal matrix. The diagonal elements of Λ are the

eigenvalues of S.
● The columns of V are orthonormal: V⊺ V = I
● The columns of V are the eigenvectors of S.
● V⊺ = V−1
Because S is a p × p symmetric matrix, we have:
● S has p real eigenvalues.
● The eigenvectors corresponding to different eigenvalues are
orthogonal. S is orthogonally diagonalizable (S = VΛV⊺ ).
● The set of eigenvalues of S is called the spectrum of S.
● The PCA is obtained via an Eigenvalue Decomposition of S.
25 / 26
Examples

● Principal Component Analysis - Intuitions:

[Link]
● Principal Component Analysis - Explained Visually:
[Link]
● Principal Component Analysis (PCA): Iris data: https:
//[Link]/~petersd/666/html/iris_pca.html
● Face Recognition using Principal Component Analysis:
[Link]
face-recognition-using-principal-component-analysis/

26 / 26