Singular Value Decomposition (SVD)

Singular Value Decomposition (SVD) stands out as one of the most versatile and informative matrix factorizations. While eigen-decomposition primarily applies to square matrices, SVD works for any rectangular $m \times n$ matrix. This generality makes it incredibly useful across various machine learning tasks, from dimensionality reduction to recommendation systems.

The core idea of SVD is to decompose an arbitrary matrix $A$ into the product of three other matrices:

$A = U \Sigma V^T$

Let's break down these components:

1. $U$: An $m \times m$ orthogonal matrix. Its columns, $u_1, u_2, ..., u_m$, are called the left singular vectors of $A$. Being orthogonal means its columns are orthonormal (unit length and mutually perpendicular), and $U^T U = U U^T = I_m$, where $I_m$ is the $m \times m$ identity matrix. These vectors form an orthonormal basis for the column space of $A$ (and its orthogonal complement).

2. $\Sigma$ (Sigma): An $m \times n$ rectangular diagonal matrix. This is the matrix that holds the singular values of $A$, denoted by $\sigma_i$. The diagonal entries $\Sigma_{ii} = \sigma_i$ are non-negative real numbers, typically arranged in descending order ($\sigma_1 \ge \sigma_2 \ge ... \ge \sigma_r > 0$), where $r$ is the rank of matrix $A$. All off-diagonal entries of $\Sigma$ are zero. If $m > n$, the bottom $m-n$ rows consist entirely of zeros. If $n > m$, the rightmost $n-m$ columns consist entirely of zeros. The singular values represent the "importance" or magnitude along the principal directions defined by the singular vectors.

3. $V^T$: An $n \times n$ orthogonal matrix (the transpose of $V$). The columns of $V$ (or rows of $V^T$), $v_1, v_2, ..., v_n$, are the right singular vectors of $A$. Like $U$, $V$ is orthogonal, meaning $V^T V = V V^T = I_n$. These vectors form an orthonormal basis for the row space of $A$ (and its orthogonal complement, the null space).

The SVD decomposes an $m \times n$ matrix $A$ into an $m \times m$ orthogonal matrix $U$, an $m \times n$ diagonal matrix $\Sigma$ containing singular values, and the transpose of an $n \times n$ orthogonal matrix $V$.

The existence of SVD for any matrix is a fundamental result in linear algebra. It essentially tells us that any linear transformation represented by a matrix $A$ can be thought of as a sequence of three simpler operations: a rotation or reflection ($V^T$), followed by a scaling along orthogonal axes (multiplication by $\Sigma$), followed by another rotation or reflection ($U$).

Understanding the Components

• Singular Values ($\sigma_i$): These values quantify how much the matrix $A$ stretches or shrinks space along the directions defined by the singular vectors. Larger singular values correspond to directions where the matrix has a greater effect. The number of non-zero singular values is equal to the rank of the matrix $A$.
• Singular Vectors ($u_i$ and $v_i$): The columns of $U$ (left singular vectors) form an orthonormal basis for the output space (column space) related to the transformation $A$. The columns of $V$ (right singular vectors) form an orthonormal basis for the input space (row space). They represent the principal directions along which the transformation acts.

While we won't go into the full proof of existence or the detailed algorithms for computation here (as libraries like NumPy handle this efficiently), understanding this structure is essential. In the following sections, we will explore the geometric meaning behind this decomposition and see how it leads to powerful applications like dimensionality reduction and data compression.