1 Principal Component Analysis (PCA)

11 Problem

Сrumbs on the floor: Each data point is represented by three coordinates , but is always . Therefore, the data can be represented by just two coordinates:

It is straightforward to find the linear transformations and :

• Principal Component Analysis (PCA) is a feature transformation method that converts the original features into a new set of transformed features , ensuring their linear independence:

  If the original features are linearly dependent, the data resides in a lower-dimensional space, meaning . For clarity, we will assume explicitly.

• The new representation is constructed as a linear combination of the original features :

  the coefficients form the matrix , which defines the linear transformation from to .

• The new, usually lower-dimensional, representation must still be informative. This is achieved by ensuring that can approximately restore the original features linearly and with minimal error:

  the coefficients form the matrix , which defines the linear transformation from back to .

• The objective of PCA is to minimize the reconstruction error by finding the optimal linear transformations and :

Сrumbs on the table.: Now, the third coordinate equals the table height :

Here, is the same as before, but no can restore the original vector exactly.

Formally, if exists, we could write the system of equations:

• The coefficients in the first two equations are determined by the identities and .
• The third equation cannot yield for all since it lacks a bias term.

Approximate solution.: In the example above, we could find as the pseudoinverse , but:

• The original vector will only be restored approximately, so .
• Since the choice of is arbitrary, the choice of is also arbitrary. This freedom allows us to impose additional constraints on the transformations.

12 Linear Maps

Matrices (dimension reducer) and (dimension adder) are linear maps that work oppositely: reduces the dimension of the original features to the dimension of the principal components , and restores, as closely as possible, the original features from the principal components.

This can be written as:

13 Matrix Formulation

The feature matrix and the principal component matrix are formed by stacking the row vectors and :

In matrix form, the linear maps and are applied as follows:

or equivalently, by transposing:

Substituting into yields the following equation:

The approximation equals exactly if . Ideally, would equal , but in general, and are non-square and therefore non-invertible.

14 Pseudoinverse matrix

holds if is the pseudoinverse of :

is exact if has full rank, but in general, it does not, so the solution is only approximate:

15 Geometric Interpretation

Basis Transition Matrix.: If in vector space , there are two bases: the old one and the new one , the vectors of the new basis can be represented as linear combinations of the old basis vectors:

The coefficients are the coordinates of the new basis vectors in the coordinate system of the old basis. These coefficients form the basis transition matrix (by columns!):

This matrix transforms coordinates between bases:

• transforms vectors from the original basis of features into a new space with the basis of principal components . However, since these bases are in different dimensional spaces, this is only an analogy.

• performs the reverse transformation, converting from the principal component basis back to the original basis (approximately).

Since and are related by the pseudoinverse operation and perform inverse transformations, we can focus on one of the matrices. Let it be .

The basis transition matrix stores the vectors of the new basis in the coordinates of the old basis. As the linear map transforms principal components into the original features (approximately):

it acts similarly to a basis transition matrix from to , storing the orthogonal basis of principal axes in the coordinates of the original space.

The choice of matrix is flexible, allowing us to impose additional constraints. For example, we can require that be diagonal or even the identity matrix:

Any basis consists of linearly independent, or orthogonal, vectors, meaning that stores orthogonal vectors, and is diagonal.

Since the choice of is not unique, we can use this freedom to demand that be not just diagonal , but the identity matrix :

This implies that stores not just orthogonal vectors but an orthonormal basis of principal components.

16 Risk Minimization

The objective of PCA is to minimize the restoration error. In this notation, the empirical risk depends on and :

We can reformulate the objective in terms of the new coordinates and the transition matrix by substituting , which at least reduces one matrix multiplication:

By differentiating with respect to and , we can find the values of and at the extremum:

is symmetric, i.e.

The objective depends only on the product , which can result from multiplying any number of different pairs of matrices:

Earlier, we showed that could be chosen to store an orthonormal basis, but this wasn’t strictly necessary.

It can be demonstrated analytically that it is sufficient to choose such that is diagonal, which is enough to ensure . This will determine the form of , which can then be interpreted as a matrix storing an orthonormal basis.

As the proof involves boring linear algebra, we relied on geometric intuition instead (though formal proof is possible!).

We will use the freedom in choosing and let and be diagonal:

• stores the principal components in their respective coordinates.
• stores the orthonormal “basis” of principal components in the coordinates of the original space, so .

Now, we can further simplify the expressions for and :