Guide: EigenDecomposition
An Overview of the Derivation and Applications of EigenValues and EigenVectors in Machine Learning
Introduction
Matrix are useful data structures in machine learning . However they could be complex in analysis. Matrix decomposition or factorization are mathematical processes of breaking down matrices. There are different types of matrix decomposition. Some examples are — Rank factorization, Cholesky decomposition, QR decomposition, Single Value Decomposition. This guide explores an important type of decomposition useful in machine learning based on the eigenvalues and eigenvectors of a matrix called eigendecomposition.
Eigendecomposition is the process of breaking a matrix into a set of eigenvalues and eigenvectors. What then are Eigen-values and Eigen-vectors? Eigenvectors are vectors when multiplied by a matrix only scale (increase in magnitude or size) but do not change direction. The amount this vectors are scaled by are refered to as their Eigenvalues. This follows that an eigenvector and matrix multiplication acts similar to an eigenvector and scalar multiplication. For a matrix M, It’s eigenvector V should follow the equation below.
MV= 𝝺V
where 𝝺 is the eigenvalue. In the equation, M is not equal to 𝝺. However, M has the same effect on V that 𝝺 has on V. It is important to note that only square matrices have eigenvectors and eigenvalues. Non-square matrices cannot be decomposed into eigenvectors and eigenvalues.
Applications
Why is it beneficial to understand eigendecomposition, eigenvalues and eigenvectors? For one, their applications are boundless. A number of machine learning problems can be resolved using Eigen-vectors and Eigen-values. Some examples include —
- Principal Component Analysis — In principal component analysis (PCA), the eigenvectors of the covariance matrix are the principal components of the dataset examined. The corresponding eigenvalues are used to sort the principal components (eigenvectors) in the order they contribute most to the variance of the data. For example — for a dataset containing information about the heights, weights, age, and gender of individuals. PCA, using eigendecomposition can be used to find the principal components that best represent the variation in the dataset, potentially reducing the dimensions from four (height, weight, age and gender) to one (a single principal component).
- Data Compression — In data compression, eigendecomposition can be used to decompose an image data into a set of its base vectors, capture the essential features and reconstruct a high quality of the version of the original data.
- Graph Theory — In social network analysis, Eigenvalues and eigenvectors provide insights into properties such as connectivity, centrality, and clustering. The eigenvalues of the adjacency matrix (the matrix representing the connection between the vertices in a network) can be used to identify influential nodes (i.e individuals with high centrality ) within a social network.
- Eigenfaces : Eigenfaces is a technique in computer vision used for facial recognition that involves representing faces as linear combinations of eigenvectors obtained from a dataset of face images. For example — a dataset of face images could be used to compute the principal components (eigenfaces) using PCA. Each face image in the dataset is then represented as a weighted sum of these eigenfaces. During recognition, new face images are projected onto the eigenface space, and similarity measures are computed to identify the closest matches.
- Anomaly Detection: Eigenvalue-based anomaly detection methods leverage the eigenvalues of covariance matrices to detect outliers or anomalies in datasets. For instance, in a system monitoring application, measurements such as temperature, pressure, and humidity are collected over time. By computing the covariance matrix of these measurements and extracting its eigenvalues, anomalies can be detected based on deviations from the expected covariance structure. Anomalies may indicate potential faults or abnormal behavior in the system.
- Natural Language Processing — Eigendecomposition can be use to identify underlying structures and patterns in textual data.Techniques like GloVe (Global Vectors for Word Representation) use eigen decompositions or similar methods on word co-occurrence matrices to learn word embeddings. These embeddings capture semantic similarities between words based on their contexts in large text corpora, enabling tasks such as word similarity calculation, analogy reasoning, and language translation.
How to Find Eigen-Values
Theory
For a matrix M, we can represent 𝝺 as the eigenvalue(s) and V as its eigenvector(s). From the definition,
MV= 𝝺V
MV- 𝝺V = 0
To factor out V which is a vector, an identity matrix I is introduced
(M- 𝝺I)V = 0
M-𝝺I = 0
Resolving resulting the system of equation would yield the eigenvalue 𝝺 of the matrix.
Example
For matrix M
Writing the equation M-𝝺I = 0
Therefore 𝝺 = 6 and 𝝺 = 2.
How to Find Eigen-Vectors
Theory
To find the eigenvectors, the equation (M- 𝝺I)V = 0 is used to derive a systems of equation which is then resolved using Cramer’s rule or elementary row transformations.
Example
Using the same example above.
For matrix M
with eigenvalues
for 𝝺 = 6
Setting up the equation (M−6I)V = 0
resolving the system of equations
from the first equation,
Substituting this into the second equation:
Therefore, any vector of the form
where 𝑥 ≠ 0 is an eigenvector corresponding to 𝝺 = 6
for 𝝺 = 2.
Setting up the equation (M−2I)V = 0
Resolving the system of equations
It’s evident from the equations that
Therefore any vector of the form
where 𝑥 ≠ 0 is an eigenvector corresponding to 𝝺 = 2
Python Implementation of Eigendecomposition
Though its beneficial to understand how to derive eigenvalues and eigenvectors, the good news is with a few lines of code, they can be derived with Python.
The linalg.eig function in the numpy library returns a list of the eigenvalues and eigenvectors of the matrix.
import numpy as np
M = np.array([[4, 2],
[2, 4]])
# Find eigenvalues and eigenvectors
eigenvalues, eigenvectors = np.linalg.eig(M)
# Print eigenvalues and eigenvectors
print("Eigenvalues:")
print(eigenvalues)
print("\nEigenvectors:")
print(eigenvectors)Similar to the example, the eigenvalues are 6 and 2.
print("First eigenvector:", eigenvectors[:,0])
print("Second eigenvector:", eigenvectors[:,1])Similar to the example, the output eigenvectors are:
Also, the linalg.eigh function is give the same output while sorting the eigenvalues.
import numpy as np
M = np.array([[4, 2],
[2, 4]])
# Find eigenvalues and eigenvectors for symmetric matrix
eigenvalues, eigenvectors = np.linalg.eigh(M)
# Print eigenvalues and eigenvectors
print("Eigenvalues:")
print(eigenvalues)
print("\nEigenvectors:")
print(eigenvectors)Eigen Properties of a Matrix
- The determinant of a matrix is the product of its eigen-values.
- If any eigenvalues are zero, it follows that the determinant is zero and hence the matrix does not have an inverse.
- The trace of a matrix is equal to the sum of its eigenvalues.
- The eigenvalues of a triangular matrix and diagonal matrices are the entries on its main diagonal.
- If a matrix has eigenvalues 𝝺, it’s inverse matrix has eigen-values 1/𝝺
Conclusion
Eigendecomposition, a process which which results in eigenvalues and eigenvectors associated with a square matrix has numerous application in machine learning. From Principal Component Analysis to Computer vision it’s usefulness in machine learning and artificial intelligence keeps growing in solving key problems. Understanding the basic concept could help unlock novel solutions to future problems.
For more on AI/ML Guides 📝, Check out other posts in this collection:
