Matrix Decompositions: SVD, Eigen Decomposition, and LU Decomposition

Vocabulary flashcards covering Singular Value Decomposition (SVD), Eigen Decomposition, and LU Decomposition along with their mathematical definitions and real-world computer science applications.

Singular Value Decomposition (SVD)

The factorization of a matrix $A$ into the product of three matrices A = U \frac{}{} \times \text{or } A = U \boldsymbol{\text{\tau}} V^T expressed as A = U \boldsymbol{\text{\tau}} V^T or $A = U \boldsymbol{\text{S}} V^T$ or A = U \boldsymbol{\text{\textSigma}} V^T (written as A = U \boldsymbol{\text{\textSigma}} V^T), where $U$ and $V$ are orthogonal matrices and \boldsymbol{\text{\textSigma}} is a diagonal matrix containing singular values.

Matrix U (in SVD)

An orthogonal matrix whose columns are the normalized eigenvectors of $A A^T$.

Matrix V (in SVD)

An orthogonal matrix whose columns are the normalized eigenvectors of $A^T A$.

Matrix \boldsymbol{\text{\textSigma}} (in SVD)

A diagonal matrix containing singular values, which quantify the strength of each underlying concept or latent feature and represent the square roots of the eigenvalues from $A A^T$ or $A^T A$.

Latent Semantic Analysis (LSA)

A natural language processing application of SVD that decomposes a document-term matrix into underlying concepts to discover hidden relationships between words and documents.

Zero Singular Value

A singular value equal to zero which implies that the dataset contains a redundant or linearly dependent dimension, allowing data to be represented in a lower-dimensional subspace.

Eigen Decomposition

The factorization (or diagonalization) of a square matrix A \boldsymbol{\text{\textin}} \boldsymbol{\text{\textR}}^{n \boldsymbol{\text{\times}} n} with $n$ linearly independent eigenvectors into $A = V D V^{-1}$, where $V$ contains the eigenvectors of $A$ as columns and $D$ is a diagonal matrix of eigenvalues.

Spectral Theorem

A theorem stating that if a real matrix A \boldsymbol{\text{\textin}} \boldsymbol{\text{\textR}}^{n \boldsymbol{\text{\times}} n} is symmetric ($A = A^T$), it is orthogonally diagonalizable as $A = P D P^T$, where $P$ is an orthogonal matrix of orthonormal eigenvectors and $D$ is a diagonal matrix of real eigenvalues.

Principal Component Analysis (PCA)

A dimensionality reduction method that uses eigen-decomposition on a data covariance matrix to find new, uncorrelated features called principal components (eigenvectors), where corresponding eigenvalues indicate the variance captured by each component.

Dominant Eigenvector

The eigenvector corresponding to the largest eigenvalue of a matrix, representing the most influential or central nodes in a network analysis.

State Transition Matrix (Malware Analysis)

A matrix modeling transitions between malware behavior states (e.g., idle, spreading, attacking), where eigen-decomposition reveals large, stable eigenvalues corresponding to predictable long-term states.

LU Decomposition

The factorization of a square matrix $A$ into the product A = L \boldsymbol{\text{\times}} U, where $L$ is a lower triangular matrix and $U$ is an upper triangular matrix.

Lower Triangular Matrix ($L$)

A square matrix in LU decomposition where all entries above the main diagonal are zero, typically constructed with principal diagonal elements equal to $1$.

Upper Triangular Matrix ($U$)

A square matrix in LU decomposition where all entries below the main diagonal are zero.

Determinant Calculation via LU Decomposition

A computational method where the determinant of a matrix $A$ is found by calculating the product of all diagonal elements of its upper triangular matrix $U$.

Method of Triangularisation

The multi-step process of solving a system of linear equations $A X = B$ by setting $A = L U$, solving $L Y = B$ for $Y$, and subsequently solving $U X = Y$ for $X$.