Introduction
Principal Component Analysis (PCA).
PCA is a linear dimensionality reduction technique that finds new directions in the data along which the variation is greatest. By projecting the data onto a smaller number of these directions, we can obtain a more compact representation.
For example, a dataset containing 100 tissue samples and 10,000 genes would have 100 rows and 10,000 columns. Working with 10,000 features is difficult to visualize, and some genes may exhibit similar expression patterns. PCA helps by transforming the original features into a smaller set of new features called principal components.
Principal components tries to re-express the data as a sum of uncorrelated components.
Geometric Intuition Behind PCA :
Given
- Input dataset with points:
- No a-priori knowledge about data needed (e.g., cluster labels)
- Statistically interpretable as observations of random variables.
Objectives of PCA
-
Structure identification in the data.
-
Extraction of meaningful features.
-
Data reduction to the most expressive information.
-
PCA is a good tool for data reduction and feature extraction.
-
Can be interpreted as linear transformation of input data to a feature space.
Computing PCA
- Data Centering : Centering the Data at the Origin
- Step 1: Compute the mean value
- Step 2: Center the data
- This shifts the entire dataset so that its mean is at the origin .
- The relative distances and directions between data points remain unchanged.
- The centered dataset has zero mean.
- Computing the Covariance Matrix
For centered data points , the covariance matrix is:
The unbiased sample covariance estimator instead uses
Where:
- = Covariance matrix.
- = Number of observations.
- = Number of features.
- = Centered data vector.
- = Dyadic (outer) product.
Dyadic Product Multiplying a column vector by its transpose produces a matrix:
- Result: An matrix.
- Each entry is the product of two feature values.
Individual Covariance Matrix Entries
For features and :
Since the data is centered, its mean is zero:
Equivalently:
Properties of the Covariance Matrix
- Represents important statistical information about the data.
- Describes variance and linear relationships between features.
- Real: All entries are real numbers.
- Square: .
- Symmetric:
- Positive semi-definite:
- All eigenvalues are non-negative.
- Diagonalisation of C
Aim of PCA: Transform centered data from dimensions into dimensions:
- Use orthogonal vectors as new coordinate axes.
- Align these vectors with the directions of highest variance.
- Ensure the transformed features are uncorrelated.
- Achieve this through diagonalisation of the covariance matrix .
(Finite-dimensional) Spectral Theorem
Let be a real, symmetric matrix.
Then there exists an orthogonal matrix , such that:
- are the eigenvalues of .
- The columns of are orthonormal eigenvectors of .
- Solving the Eigenvalue Problem
We get the wanted alternative data representation by computing eigenvalues and respective eigenvectors of .
Solve the eigenvalue problem:
A solution can be found by various methods:
- Roots of characteristic polynomial
- QR algorithm
- Jacobi eigenvalue algorithm
- Singular value decomposition
We get
- positive semi-definite only non-negative eigenvalues.
- = data variance along direction of eigenvector .
- Eigenvectors form a new local coordinate system.
Example
-
Data is distributed within a hyperplane parallel to the plane , data is a flat sheet of points inside 3D space.
→ No variance in direction -
Easy to recognize from eigenvalue , because leads to:
- Selection of eigenvalues leads to data reduction.
Applying Principal Component Analysis
Define Transformation Matrix
For which are the respective eigenvectors of the largest eigenvalues.
- Transform the data:
- contains the most relevant information (features) of the input data.
- The components are called principal components.
- If is quadratic () PCA is simply a rotation in .
The principal components of the input data are typically used as features in classification or clustering tasks.
Summary of PCA
For given input data , the PCA can be computed as:
- Compute mean value of data:
- Center data via:
- Compute covariance matrix:
-
Determine the eigenvalues and eigenvectors of numerically.
-
Select respective eigenvectors of the largest non-vanishing eigenvalues.
-
Assemble selected eigenvectors columnwise to matrix:
- Compute principal components for each input point via:
Data Reconstruction
Reconstructing the input data from its principal components is (partially) possible via:
It is clear that:
Otherwise: Loss of information
Problems with PCA
- Computational complexity mainly depends on dimension of data space.
- PCA is restricted to linear features.
- Computational complexity is .
- → Eigenproblem.
- → Covariance matrix.
- Numerically expensive for large (dimension of data space).
- Amount of principal components (and hence possible features) is bounded by . For