Let’s say that we have a bunch of d-dimensional vectors
xi∈Rd, i∈{1,…,n} (throughout this
text we will assume n≥d, i.e. the number of vectors is at least
equal to the size of the vectors). We can put all of these vectors
side-by-side in the form of a matrix
X=[x1,…,xn]∈Rd×n.
We call this matrix X as the “data matrix,” and the vectors
xi as “data samples” or just “samples.” We represent the
“labels” with the symbol yi∈{1,0}, for i∈{1,…,n}.
Also stacking these together in the form of a vector
y=[y1,…,yn]⊤∈Rn, we call this the
“label vector”.
The “dimension” of a vector is the number of elements in it. For
example, the dimension of all the vectors xi∈Rd
in the above section is d. Sometimes, we might want to reduce the
dimension of a vector, but still retain the “essence” of the vector. We
can represent these smaller vectors as zi∈Rp,
p<d. And we call these smaller vectors as “representations/features”
of xi. We will discuss later how we can get zi
given some xi (and maybe also yi). The definition of
“essence” can pretty much be anything, but we will discuss 2 main ideas
in Sections 4 and 5 that correspond to orthogonal linear representations.
In the context of orthogonal linear representations, we might also be
interested in a representation that separates out a mixture of signals
into its ‘independent’ components. We discuss this in Section 6.
Eigen Value Decomposition (EVD)
For any square matrix X∈Rn×n, we have n
“eigenvalues” λi∈R and corresponding “eigenvectors”
ui∈Rn. Eigenvalues and eigenvectors are
special in the sense that for each pair the following equation holds
Xui=λiui.(1)
To get an intuitive understanding of the equation (1),
watch this video. It turns out that
matrix X can be “decomposed” into the product of (square)
matrices of its eigenvalues and eigenvectors.
where U and V are “orthonormal” matrices, which
just means that U⊤U=Id, or in other
words U⊤=U−1 and Σ is a
diagonal matrix (not necessarily square). σi are called
“singular values” and ui∈Rd and
vi∈Rn are called left and right “singular
vectors” respectively. And, interestingly, there is a descending order
to the singular values in Σ and they are also all
non-negative, i.e. σ1≥⋯≥σd≥0.
SVD vs. EVD
There is a very close relationship between EVD and SVD. This can be seen
by substituting the SVD of X from
(3) in
XX⊤ and X⊤X.
Here, we have used the fact that
(AB)⊤=B⊤A⊤.
Equations (4) and
(2) are similar. Therefore, U is the matrix of eigenvectors of
XX⊤ and, similarly, V is the matrix
of eigenvectors of X⊤X. In each case,
Σ2 is the eigenvalue matrix.
Principal Component Analysis (PCA)
Principal Component Analysis (PCA) is a special (and arguably the most
famous) dimensionality reduction technique. Let’s first go over the
steps of PCA and we shall discuss the intuition and motivation behind it
shortly after.
Given a data matrix
X=[x1,…,xn]∈Rd×n,
we wish to reduce the dimension of the data from d to k<d to get
smaller versions zi of each sample xi. We carry
out the following steps to get the so called “principal components" and
“score matrix" of the data.
Beyond this point, it would be better for the reader
to consider X and Xˉ as essentially the
same for ease of understanding.
Perform the SVD on
Xˉ=UΣV⊤.
Throw away all but the first k “singular vectors” (columns) from
U=[u1…ud] to get a smaller
matrix Uk=[u1…uk]∈Rd×k.
This matrix is called the matrix of k “principal components” of
X.
The matrix
Z=Uk⊤Xˉ=[z1…zn]∈Rk×n
is called the “score matrix” of X, where each “score
vector” zi∈Rk is a low-dimensional version
of the corresponding data sample xi∈Rd.
One interesting thing to note here is that given Z and
Uk that were obtained from PCA, we can “reconstruct” an
“approximate” version of the original (centered) data matrix
Xˉ as
Xˉ=UkZ=UkUk⊤Xˉ=[xˉ1…xˉn]∈Rd×n.
These “approximations” xˉi of samples
xˉi are also called the “projections” of
xˉi onto the “space spanned by the principal
components.” For a new, previously unseen sample
xnew, we perform only steps 2 and 5 to get
znew.
Now that we have discussed the precise steps of PCA, we can discuss the
intuition behind it.
Minimum residual view of PCA
Imagine we have the (centered) data samples in Rd (e.g.,
d=2). Our goal is to find a different version of this data that
instead lies in Rk, which is a lower-dimensional space for
k<d (e.g., k=1). Then, PCA can be thought of as “finding” this
low-dimensional “linear”2 space such that, on average, the difference
(also called “residual”) between any sample xˉi and its
projection xˉi onto the low-dimensional space
is as small as possible. The unit vectors (also called “basis vectors”
or just “basis”) of this low-dimensional space are precisely the
principal components ui (therefore there are k unit
vectors for a k-dimensional space).
Maximum variance view of PCA
The principal components of the data are vectors along the maximum
variance directions of the data. The first principal component lies
along the direction of highest variance. The second principal component
lies along the direction of second highest variance, and so on. The
score vectors zi are then the “projections”3xˉi of the original (centered) samples
xˉi onto a linear-subspace with unit-vectors
uj, but viewed in the sub-space instead of the original
space.
Linear Discriminant Analysis (LDA)
Linear Discriminant Analysis (LDA) is a dimensionality reduction
technique that utilizes class labels to find directions that maximize
the separability between classes. Given the data matrix
X=[x1,…,xn]∈Rd×n
and the label vector
y=[y1,…,yn]⊤∈{0,1}n, LDA aims to
project the data into a lower-dimensional space such that the projected
samples zi∈Rk (with k<d) maximize the
class separability.
The steps to perform LDA are as follows:
Compute the mean vector of the entire dataset:
μ=n1i=1∑nxi=n1X1n∈Rd.
Compute the mean vector for each class c∈{0,1}:
μc=nc1i∈Cc∑xi=nc1Xc1nc∈Rd,
where Cc={i:yi=c},
Xc∈Rd×nc contains the samples
from class c, and nc=∣Cc∣ is the number of samples
in class c.
where wi∈Rd are the
eigenvectors and λi∈R are the eigenvalues.
Sort the eigenvectors by decreasing eigenvalue magnitude.
Select the top k eigenvectors w1,…,wk
to form the projection matrix
W=[w1…wk]∈Rd×k.
Project the data into the lower-dimensional space:
Z=W⊤X∈Rk×n.
LDA ensures that the projected data Z maximizes the ratio of
between-class variance to within-class variance in the lower-dimensional
space.
Independent Component Analysis (ICA)
Independent Component Analysis (ICA) is a dimensionality reduction
technique aimed at finding a representation of the data where the
components are statistically independent. Unlike PCA or LDA, ICA does
not rely on variance or class labels but instead focuses on higher-order
statistical independence.
Given the data matrix
X=[x1,…,xn]∈Rd×n,
ICA assumes that X is a linear mixture of independent
components. This means:
X=AS,
where A∈Rd×d is the
mixing matrix, and
S=[s1,…,sn]∈Rd×n
contains the independent components si∈Rd. The
goal of ICA is to find an unmixing matrix
W∈Rd×d such that:
S=WX,
where the rows of S are as statistically independent as possible.
The steps to perform ICA are as follows:
Center the data matrix X by subtracting the mean vector
μ=n1X1n:
Xˉ=X−μ⊗1n⊤.
Whiten the data matrix Xˉ to remove correlations
between features:
Xwhite=D−21E⊤Xˉ,
where D and E are obtained
from the eigenvalue decomposition
C=XˉXˉ⊤=EDE⊤.
Use an iterative algorithm (e.g., FastICA) to estimate the unmixing
matrix W such that the components of
S=WXwhite are statistically
independent (not within the scope of this text!).
The independent components are given by:
S=WX.
ICA is commonly used in applications such as blind source separation,
where the goal is to recover original signals from mixed observations
(e.g., separating audio sources recorded by multiple microphones).
1
The “Kronecker product” of matrices A=[a1,1a2,1a1,2a2,2] and B=[b1,1b2,1b1,2b2,2] is defined as
A⊗B:=[a1,1Ba2,1Ba1,2Ba2,2B].
2
A linear space means just what it sounds like — something that
looks like a line. For example, a line drawn on a piece of paper is
a 1-dimensional linear “sub-space” that lies in a higher
2-dimensional space, the paper.
3
the orthogonal projection of some a onto a “linear
sub-space” is basically the closest point a^ to
a that lies on that linear sub-space