Singular Value Decomposition › Mathematical Formulation

To understand SVD, it helps to start with a simpler case you may already know: eigendecomposition. For a square symmetric matrix $\mathbf{A}$, eigendecomposition gives us $\mathbf{A} = \mathbf{Q} \mathbf{\Lambda} \mathbf{Q}^T$, where $\mathbf{Q}$ is an orthogonal matrix of eigenvectors and $\mathbf{\Lambda}$ is diagonal with eigenvalues. This works beautifully when $\mathbf{A}$ is square and symmetric, but our word-context matrix $\mathbf{M}$ is rectangular: it has one row per word in the vocabulary and one column per context word, and those two sets need not have the same size.

SVD is the generalization of eigendecomposition to rectangular matrices. For any matrix $\mathbf{M}$ of dimensions $m \times n$, SVD produces an exact decomposition:

$$\mathbf{M} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T$$

where:

• $\mathbf{U}$ is an $m \times m$ orthogonal matrix whose columns are the left singular vectors
• $\mathbf{\Sigma}$ is an $m \times n$ diagonal matrix containing the singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r \geq 0$ on the diagonal, where $r = \min(m, n)$
• $\mathbf{V}^T$ is the transpose of an $n \times n$ orthogonal matrix whose columns are the right singular vectors

The singular values measure how much variance each corresponding direction explains. A large $\sigma_i$ means the $i$-th pair of left and right singular vectors captures a strong, consistent pattern in the data. A small $\sigma_i$ corresponds to a weak pattern that may be statistical noise arising from the finite sample of text.

For a word-context matrix $\mathbf{M}$ where rows represent vocabulary words and columns represent context words:

• The left singular vectors $\mathbf{U}$ define a coordinate system in word space: each column of $\mathbf{U}$ is a direction in the space of vocabulary words
• The right singular vectors $\mathbf{V}$ define a coordinate system in context space: each column of $\mathbf{V}$ is a direction in the space of context words
• The singular values $\mathbf{\Sigma}$ tell you how important each coordinate axis is in explaining the data

The entire matrix $\mathbf{M}$ can be reconstructed exactly from the full SVD. The SVD says: $\mathbf{M}$ can be written as a sum of $r$ rank-1 matrices, each formed by the outer product of one left singular vector and one right singular vector, weighted by the corresponding singular value:

$$\mathbf{M} = \sum_{i=1}^{r} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^T$$

where $\mathbf{u}_i$ is the $i$-th column of $\mathbf{U}$ and $\mathbf{v}_i$ is the $i$-th column of $\mathbf{V}$. Each term $\sigma_i \mathbf{u}_i \mathbf{v}_i^T$ is a rank-1 matrix describing one coherent pattern: it says "the set of words characterized by $\mathbf{u}_i$ tend to co-occur with the set of contexts characterized by $\mathbf{v}_i$, and this tendency has strength $\sigma_i$." The full matrix is the superposition of all these patterns. The real power comes from the truncated version, where we keep only the largest-magnitude terms.

The orthogonality constraints on $\mathbf{U}$ and $\mathbf{V}$ are a technical constraint with direct consequences for the quality of the embeddings.

Orthogonality means the columns of $\mathbf{U}$ form an orthonormal basis: $\mathbf{U}^T \mathbf{U} = \mathbf{I}$, and similarly $\mathbf{V}^T \mathbf{V} = \mathbf{I}$. In practical terms, this means each SVD dimension is completely uncorrelated with every other. In a raw co-occurrence matrix, the dimensions (context words) are highly correlated: "cat" and "kitten" often appear in the same contexts, so their corresponding dimensions carry redundant information. Any vector in the raw PPMI space is tangled up with this redundancy. SVD finds a new basis where this redundancy has been removed.

The first SVD dimension captures the single most important source of variation in the data. The second dimension captures the most important variation that remains after removing the first. The third captures what remains after removing the first two, and so on. This greedy structure, where each dimension is chosen to be maximally informative given the previous ones while remaining orthogonal to all of them, is exactly what makes the truncated SVD an optimal low-rank approximation. You cannot do better with the same number of dimensions, given the orthogonality constraint.

A useful geometric picture: the SVD is finding the principal axes of an ellipsoid. If you imagine the rows of $\mathbf{M}$ as points in $n$-dimensional space, they form some cloud with an elongated shape. The first left singular vector points along the longest axis of this ellipsoid, the direction of maximum spread. The second points along the next longest axis, perpendicular to the first. SVD is essentially fitting an ellipsoid to the data and reading off its axes.

There is a clean algebraic relationship between SVD and the eigendecomposition of the symmetric matrices $\mathbf{M} \mathbf{M}^T$ and $\mathbf{M}^T \mathbf{M}$. Multiplying out the SVD factorization:

$$\mathbf{M} \mathbf{M}^T = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T \mathbf{V} \mathbf{\Sigma}^T \mathbf{U}^T = \mathbf{U} \mathbf{\Sigma} \mathbf{\Sigma}^T \mathbf{U}^T$$

Since $\mathbf{V}$ is orthogonal, $\mathbf{V}^T \mathbf{V} = \mathbf{I}$, so the middle terms collapse. This shows that the columns of $\mathbf{U}$ are exactly the eigenvectors of the $m \times m$ matrix $\mathbf{M} \mathbf{M}^T$, and the squared singular values $\sigma_i^2$ are the corresponding eigenvalues. Similarly, the columns of $\mathbf{V}$ are the eigenvectors of the $n \times n$ matrix $\mathbf{M}^T \mathbf{M}$.

In NLP terms, $\mathbf{M} \mathbf{M}^T$ is the word-by-word similarity matrix: entry $(i,j)$ is the dot product of the PPMI profiles of words $i$ and $j$, measuring how similar their co-occurrence patterns are. The eigenvectors of this matrix are the directions that best explain word-to-word similarity. The left singular vectors of $\mathbf{M}$ are precisely these eigenvectors, which is why SVD gives you meaningful word embeddings.