Singular Value Decomposition › Truncated SVD for Dimensionality Reduction

The key insight of Latent Semantic Analysis is that most of the informative structure in a word-context matrix lives in the top few hundred singular values. The rest is statistical noise arising from the finite, imperfect sample of text. By keeping only the $k$ largest singular values and their corresponding vectors, we obtain a rank-$k$ approximation:

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

where:

• $\mathbf{U}_k$ is the $m \times k$ matrix formed from the first $k$ columns of $\mathbf{U}$ (the $k$ most important left singular vectors)
• $\mathbf{\Sigma}_k$ is the $k \times k$ diagonal matrix containing the $k$ largest singular values
• $\mathbf{V}_k^T$ is the $k \times n$ matrix formed from the first $k$ rows of $\mathbf{V}^T$ (the $k$ most important right singular vectors)

This approximation $\mathbf{M}_k$ is the closest rank-$k$ matrix to $\mathbf{M}$ under the Frobenius norm. The Frobenius norm of a matrix $\mathbf{A}$ is the square root of the sum of all squared entries:

$$\|\mathbf{A}\|_F = \sqrt{\sum_{i=1}^{m} \sum_{j=1}^{n} A_{ij}^2}$$

No other rank-$k$ matrix provides a better approximation under this metric. This result, known as the Eckart-Young-Mirsky theorem, gives the truncated SVD a rigorous optimality guarantee. You are not just compressing the data: you are computing the mathematically optimal compression at any given target rank $k$. The approximation error is:

$$\|\mathbf{M} - \mathbf{M}_k\|_F^2 = \sum_{i=k+1}^{r} \sigma_i^2$$

This says the squared error of the rank-$k$ approximation equals the sum of squared singular values that were dropped. If the singular values decay rapidly, the error from truncation is small even for modest $k$.

The word embeddings in LSA are the rows of $\mathbf{U}_k \mathbf{\Sigma}_k$: each word gets a $k$-dimensional vector. You can also use just $\mathbf{U}_k$ (the rows of the left singular matrix without scaling by singular values), but $\mathbf{U}_k \mathbf{\Sigma}_k$ is more common because it preserves the relative importance of each dimension. A dimension with a large singular value should contribute more to the distance between embeddings than a dimension with a small one.

The Eckart-Young-Mirsky theorem is worth pausing on, because it explains why truncated SVD is so natural for NLP. Consider the noise model for a co-occurrence matrix: we believe the true signal is a low-rank structure (a few dominant semantic themes), overlaid with high-rank noise from sampling variability, rare co-occurrences, and corpus-specific quirks. The theorem says that the best way to recover the signal, in a least-squares sense, is to keep only the top $k$ singular vectors and values. There is no other rank-$k$ matrix that comes closer to the observed data. This means truncated SVD is simultaneously a compression algorithm and a denoising algorithm. It removes the noisy high-rank components and retains the structured low-rank signal.

This is precisely analogous to smoothing a noisy signal by keeping only its low-frequency Fourier components. In Fourier analysis, the important structure is in the low frequencies and noise is in the high frequencies. In SVD analysis of co-occurrence matrices, the important structure is in the top singular values and noise is in the bottom ones. The analogy is not just metaphorical: both operations minimize mean squared error under their respective optimality criteria.

Why does the approximation work so well for language? Because human vocabulary is not independent. A text about biology uses many words together: "cell," "protein," "DNA," "gene," "enzyme." A text about finance uses a different cluster: "equity," "bond," "interest," "dividend," "portfolio." These thematic co-occurrences create low-rank structure in the word-context matrix: the vast majority of variation can be explained by a relatively small number of underlying semantic dimensions.

Consider what "low rank" means concretely. A rank-$k$ matrix can be written as the sum of $k$ outer products. For language, this means the entire co-occurrence behavior of the vocabulary can be approximated as a superposition of $k$ independent patterns. Pattern 1 might capture "biology words co-occurring with biology contexts." Pattern 2 might capture "finance words co-occurring with finance contexts." Pattern 3 might capture "sports words co-occurring with sports contexts." The actual patterns are more abstract and intertwined than this, but the point is that a relatively small number of them suffices to explain most of the variance.

For a vocabulary of 100,000 words, the raw PPMI matrix has 10 billion entries. But if the true rank is 300, then it can be described by $300 \times (100{,}000 + 100{,}000)$, which is just 60 million numbers: a compression ratio of 167:1. The fact that this compressed description is also semantically meaningful is not a coincidence: it is because meaningful semantic categories are precisely the kind of coherent, repeating patterns that SVD is designed to discover.

SVD discovers these latent patterns automatically, without any supervision. Dimension 1 might correspond roughly to "living things vs. inanimate objects." Dimension 2 might separate "technical vs. everyday language." Dimension 3 might track "formal vs. informal register." These dimensions are not cleanly interpretable in the way a topic model produces explicit word lists, but they capture real semantic structure measurable in downstream tasks.