Singular Value Decomposition: SVD, LSA, and Word Embeddings

Co-occurrence matrices and PPMI weighting, as we explored in the previous chapters, give us a way to represent words as high-dimensional vectors where each dimension corresponds to a context word. A word like "bank" might live in a space with tens of thousands of dimensions. These representations capture real associations, but they come with a serious problem: they are enormous and sparse, with substantial noise. Most entries are zero, and the non-zero entries carry substantial statistical noise from the finite size of any real corpus. The question is whether we can do better, whether there is a principled way to compress these unwieldy representations into a compact, dense representation that retains useful information.

Singular Value Decomposition (SVD) is the answer. It is a linear algebra technique that takes a large, sparse matrix and compresses it into a compact set of dense vectors that capture the most important structure while discarding noise. When applied to word-context matrices, this compression produces what are known as Latent Semantic Analysis (LSA) embeddings, an early but remarkably effective form of word embeddings that predates neural approaches by decades. Understanding SVD deeply is worth the effort not just for historical reasons. The mathematical ideas behind SVD, optimal low-rank approximation, orthogonal bases, and the spectral decomposition of data, reappear throughout modern machine learning in forms as varied as principal component analysis, matrix factorization for recommender systems, and even the theoretical analysis of what neural language models are implicitly learning.

The intuition behind SVD is that language has hidden structure. If "dog" and "cat" both appear frequently near "pet," "feed," and "veterinarian," those words are telling us something similar about both animals. But the raw co-occurrence matrix does not know this: it just sees two different rows with different column patterns. SVD discovers these latent patterns by finding directions in the high-dimensional space along which the data varies most strongly. Each direction captures a coherent theme or topic, and projecting words onto the most important directions gives dense, low-dimensional vectors that encode meaning through shared statistical patterns. The dimensions produced by SVD are not labeled with human-interpretable names. They are abstract algebraic constructs, but they encode real semantic relationships that emerge directly from distributional statistics.

This chapter builds up SVD from first principles: why matrix factorization works, what the singular values mean geometrically, how truncation produces optimal embeddings, and how the full pipeline from raw text to cosine similarities operates in practice. We then examine the practical algorithms needed to make SVD feasible at vocabulary scale, and close with an honest assessment of where LSA succeeds and where later approaches were forced to go beyond it.

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:

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:

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:

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.

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:

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:

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:

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.

LSA, introduced by Deerwester, Dumais, Furnas, Landauer, and Harshman in their landmark 1990 paper "Indexing by latent semantic analysis," applies truncated SVD to term-document or term-term co-occurrence matrices to obtain word representations. The paper proposed LSA primarily as a method for document retrieval, but its implications for semantic representation quickly became clear.

The name "latent semantic" captures the core idea: the dimensions discovered by SVD correspond to underlying (latent) semantic themes that are not visible in the raw counts. The original LSA paper demonstrated something remarkable: after SVD compression, words that never appear in the same document can still have high cosine similarity in the compressed space, if they tend to appear in documents covering similar topics. This is latent semantics: meaning inferred from indirect co-occurrence patterns, not direct co-occurrence.

For example, "physician" and "doctor" rarely appear in the same sentence. In a raw co-occurrence matrix, their co-occurrence count might be close to zero. But both frequently appear in texts about hospitals, patients, treatments, and medical care. SVD discovers that these words belong to the same semantic neighborhood by noticing that they appear with similar context words across the corpus. The shared context lifts them into the same neighborhood in the latent space, even though they were never direct co-occurrences.

The original LSA evaluation was striking. On synonym selection tests from the Test of English as a Foreign Language (TOEFL), an LSA system trained on a large text corpus achieved accuracy comparable to college-bound non-native English speakers, and substantially above chance. This was achieved without any explicit synonym dictionaries or semantic rules, purely from distributional patterns in raw text. It was early evidence that statistical structure in large corpora encodes something meaningful about semantic relationships.

LSA can be applied to either of two matrix types, and the choice matters for what kind of similarity the resulting embeddings capture.

Term-document matrices have rows for terms and columns for documents. Entry $(i, j)$ records how often term $i$ appears in document $j$, typically with TF-IDF weighting to reduce the dominance of common words. SVD on this matrix discovers patterns of which terms tend to appear together in the same documents. Two words will be similar if they tend to appear in the same kinds of documents, even if they rarely appear in the same sentence. This makes term-document LSA natural for topical similarity: "automobile" and "vehicle" are similar because they both appear in transportation articles.

Term-term co-occurrence matrices (also called word-word matrices) have rows and columns both representing vocabulary words, with entries recording how often the row word appears within a context window of the column word. The window might be 2 words to the left and right, or 5 words, or an entire document. SVD on this matrix discovers patterns of which words appear in similar local contexts. Two words will be similar if they are interchangeable in sentences, not just in documents.

Both approaches produce useful word embeddings, but they capture different aspects of similarity. Term-document matrices tend to capture topical or associative similarity: "surgeon" and "hospital" are similar because they appear in medical documents. Term-term matrices capture paradigmatic or substitutional similarity: "surgeon" and "physician" are similar because they can substitute for each other in sentences ("the surgeon/physician examined the patient"). For most NLP applications, paradigmatic similarity is more useful, which is why term-term matrices have become the standard for distributional word embeddings.

The window size in term-term matrices also matters. Narrow windows (1-2 words) capture syntactic similarity: words that fill the same grammatical role. Wide windows (5-10 words or entire documents) blend into topical similarity. This is because nearby words are constrained by local syntax, while distant words are constrained by document topic. The transition from narrow to wide windows interpolates between syntactic and topical similarity, and the right choice depends on the downstream task.

LSA is grounded in the distributional hypothesis, which holds that words with similar meanings tend to appear in similar contexts. We discussed this hypothesis in the chapter on distributional semantics, and LSA operationalizes it with mathematical precision. The PPMI matrix measures how much each word-context pair co-occurs beyond chance. SVD then finds the directions in this space along which co-occurrence patterns are most coherent and persistent.

What makes LSA's formulation powerful is that it goes beyond pairwise co-occurrence. Two words can be similar in the LSA space even if their direct co-occurrence count is zero, as long as they share indirect neighbors. If "cat" often appears near "pet" and "food," and "dog" often appears near "pet" and "food," then SVD places them near each other because they project strongly onto the same first few left singular vectors. The singular vectors aggregate co-occurrence signals across the entire vocabulary, finding the directions that simultaneously explain many words at once.

The most important hyperparameter in LSA is $k$, the number of singular values to retain. The tradeoff is fundamental: too few dimensions and the representation cannot capture enough nuance in the vocabulary; too many and you retain noise rather than signal. Getting $k$ right matters more than almost any other architectural choice in the LSA pipeline.

The primary diagnostic for choosing $k$ is a plot of the singular values in decreasing order, called a scree plot (the term comes from geology: "scree" is the debris that accumulates at the base of a cliff). The scree plot for a typical NLP co-occurrence matrix shows:

• A rapid initial decline through the first handful of dimensions, representing the dominant semantic themes
• A knee or elbow where the rate of decline slows substantially
• A long, gradually declining or flat tail representing noise and idiosyncratic patterns

The optimal $k$ is often near the elbow. Values beyond the elbow add little signal and increasingly mix noise into the representations. For tasks where you want distinct separation of major topics, choosing $k$ at or before the elbow is conservative and effective. For tasks where finer distinctions matter, you may benefit from going beyond the elbow.

In practice, the scree plot provides a floor on $k$ (include all components up to the elbow) but does not give a sharp ceiling. The right answer is usually obtained by evaluating downstream task performance across a range of $k$ values, which leads to the empirical approach described below.

Choosing $k$ by evaluating downstream task performance is the most reliable approach. Researchers have found consistent patterns across many experiments with NLP co-occurrence matrices:

• Small vocabularies and small corpora benefit from small $k$ (50-100), because there are fewer distinct semantic dimensions to capture and the matrix is not large enough to support reliable estimation of many components
• Large vocabularies with rich, diverse corpora can benefit from larger $k$ (300-500), especially when the target application requires distinguishing fine-grained semantic categories
• The original LSA paper found 100-300 dimensions worked well for document similarity and word analogy tasks
• Performance is often stable across a range of $k$ values, with a broad plateau rather than a sharp peak; a factor of 2 change in $k$ rarely produces dramatic differences

The key insight is that $k$ controls the bias-variance tradeoff. Small $k$ gives high bias (the embedding cannot distinguish closely related words or subtle semantic contrasts) but low variance (the representation is not affected by corpus-specific noise or sampling fluctuations). Large $k$ gives low bias but high variance (noise in the corpus leaks into the embedding dimensions). The optimal $k$ balances these two sources of error, and that balance point depends on the corpus size and the downstream task.

For practical recommendation: start with $k = 100$ as a baseline, evaluate on your target task, and try $k = 50$ and $k = 300$ to understand the sensitivity. If your corpus is small (fewer than 1 million tokens), prefer smaller $k$. If your corpus is large and your task requires fine-grained distinctions, larger $k$ is worth testing.

An alternative to the scree plot is to look at cumulative explained variance: what fraction of the total variance (sum of squared singular values) is captured by the first $k$ components? Common thresholds are 80-90% explained variance. In practice, the number of components needed to explain 80% of variance in a large NLP matrix can be surprisingly large, because language has many semantic dimensions. The cumulative variance curve often rises steeply at first and then flattens gradually, without a clean elbow. Using explained variance thresholds can push $k$ too high in large, diverse corpora.

Both the scree plot and cumulative variance are useful diagnostics, but neither should override direct measurement on your downstream task. The relationship between intrinsic dimensionality estimates and extrinsic task performance is not always predictable.

Computing the full SVD of an $m \times n$ matrix takes $O(mn \cdot \min(m, n))$ time. For a vocabulary of $V$ words, a word-word co-occurrence matrix is $V \times V$, making the full SVD $O(V^3)$ in time. A vocabulary of 100,000 words would require on the order of $10^{15}$ operations: completely infeasible with any current hardware.

The memory requirement for storing the full dense co-occurrence matrix is $V^2$ entries. At 100,000 words and 4 bytes per float, that is already 40 gigabytes. Larger vocabularies (500,000 words, as in some production systems) would require 1 terabyte just to store the matrix in dense form. These numbers make clear that full SVD on large NLP matrices is not just slow: it is impossible without specialized techniques.

Several strategies address this, and understanding them clarifies why LSA became computationally practical:

Sparse matrix storage: Co-occurrence matrices are extremely sparse. Even with a window of 5 words, most word pairs never co-occur in any reasonable corpus. The fraction of nonzero entries in a PPMI matrix for a 100,000-word vocabulary on a billion-word corpus is typically well below 1%. Sparse formats like compressed sparse row (CSR) store only the nonzero entries, reducing memory by 100x or more compared to dense storage.

Truncated SVD via Lanczos iteration: When you only need the top $k$ singular vectors rather than all of them, specialized algorithms exploit the structure of the problem. The Lanczos algorithm builds a sequence of orthogonal vectors that progressively refine estimates of the top singular vectors. Starting from a random vector, it applies the matrix repeatedly and uses Gram-Schmidt orthogonalization to build a Krylov subspace, a subspace that converges rapidly to the dominant singular directions. The algorithm requires only matrix-vector products with $\mathbf{M}$ and $\mathbf{M}^T$, which can be done efficiently for sparse matrices without ever constructing a dense representation. The computational cost is roughly $O(k \cdot \text{nnz})$, where nnz is the number of nonzero entries.

Vocabulary truncation: Only retaining the top $V'$ most frequent words dramatically reduces the matrix size. Words that appear very rarely (fewer than 5-10 times in the corpus) contribute mostly noise to the SVD and can safely be excluded. Keeping the top 30,000-50,000 vocabulary items is common in practice, which reduces the matrix from $V^2$ to $(V')^2$ entries, a reduction of 4-16x relative to a 100,000-word vocabulary.

PPMI matrix factorization via co-occurrence streaming: Rather than forming the full dense PPMI matrix and then applying SVD, some implementations stream through the corpus to accumulate only the co-occurrences needed, building the sparse PPMI matrix incrementally without ever materializing it fully in memory.

Even with sparse algorithms, exact SVD becomes slow for matrices with millions of rows or columns. Modern production NLP systems may want to compute embeddings for vocabularies of 500,000 to 1 million words. Randomized SVD, introduced by Halko, Martinsson, and Tropp in their influential 2011 paper "Finding structure with randomness," provides a principled approximation that dramatically reduces computation while maintaining high accuracy.

The algorithm works in two stages that together are much cheaper than direct SVD.

Stage 1: Range finding. The goal of this stage is to find a small orthonormal matrix $\mathbf{Q}$ whose columns approximately span the range (column space) of $\mathbf{M}$, restricted to the $k$ dominant directions. Generate a random matrix $\mathbf{G}$ of shape $n \times (k + p)$, where $p$ is a small oversampling parameter, typically 5 to 10. The oversampling provides insurance that the random projection does not miss any important directions. Form the sample matrix:

Compute an orthonormal basis $\mathbf{Q}$ for the column space of $\mathbf{Y}$ using QR decomposition. The key insight is that multiplying $\mathbf{M}$ by a random matrix produces a "sketch" of the column space of $\mathbf{M}$. If $\mathbf{M}$ has $k$ dominant singular directions with much larger singular values than the rest, then $\mathbf{Y}$ will be approximately a linear combination of those $k$ directions plus small random perturbations. QR decomposition extracts an orthonormal basis for this sketch.

Stage 2: SVD of the projected matrix. Form the smaller matrix:

$\mathbf{B}$ has dimensions $(k + p) \times n$. Rather than being enormous, $\mathbf{B}$ is small in its first dimension: only $k + p$ rows. Compute the exact SVD of $\mathbf{B}$:

Recover the approximate left singular vectors as $\mathbf{U} = \mathbf{Q} \hat{\mathbf{U}}$.

The computational saving is substantial. The expensive operations in the randomized algorithm are the matrix-vector products in forming $\mathbf{Y}$ and $\mathbf{B}$, each costing $O(\text{nnz})$ for a sparse matrix. The full SVD of $\mathbf{B}$ costs $O((k+p)^2 n)$, which is small when $k \ll m$. Compared to exact SVD at $O(k \cdot \text{nnz})$, the asymptotic cost is similar, but the constant factors are much smaller because the algorithm avoids the iterative Lanczos refinement. For very large matrices, the difference is an order of magnitude in wall time.

The theoretical guarantee is that the error of randomized SVD is, with high probability, only slightly larger than the error of the best rank-$k$ approximation. Specifically:

where the expectation is over the random choice of $\mathbf{G}$ and $\sigma_{k+1}$ is the $(k+1)$-th singular value. When $p$ is even modestly large (say, $p = 10$) and the singular values decay rapidly (as they do in NLP matrices), the bound is tight and the approximation is excellent.

An optional but often used power iteration step can further improve accuracy: instead of computing $\mathbf{Y} = \mathbf{M} \mathbf{G}$, compute $\mathbf{Y} = (\mathbf{M} \mathbf{M}^T)^q \mathbf{M} \mathbf{G}$ for small $q$ (typically 1 or 2). Each power iteration squares the singular values, making the dominant ones even more prominent relative to the small ones and producing a better sketch of the dominant subspace. The cost is $2q$ additional matrix-vector products.

Scikit-learn's TruncatedSVD uses randomized SVD internally for large matrices, making it the practical tool of choice for LSA at scale. The algorithm='randomized' option (the default) invokes this randomized approach.

One of the persistent challenges with SVD-based embeddings is that the resulting dimensions are not directly interpretable. Unlike topic models such as Latent Dirichlet Allocation, which produce explicit probability distributions over words for each topic, SVD dimensions are abstract linear combinations of all the original features. A dimension is defined by its loading vector: the left singular vector $\mathbf{u}_i$, which assigns a real-valued weight to every word in the vocabulary. Positive weights indicate words that are "on one side" of the dimension; negative weights indicate words on the other side.

Despite this abstractness, considerable structure is recoverable through careful inspection. For each SVD dimension, you can rank the vocabulary words by their loading in the corresponding left singular vector: the words with the highest positive loadings tell you what the dimension is "about" in the positive direction, and the words with the highest negative loadings tell you what it captures in the negative direction. A dimension might show "music, melody, harmony, song, rhythm" on one pole and "mathematics, equation, proof, theorem, algebra" on the other, suggesting it captures a technical-versus-aesthetic contrast. Another dimension might show "happy, joyful, delighted, cheerful" on one pole and "sad, gloomy, miserable, depressed" on the other, capturing an emotional valence axis.

The first dimension often captures something close to word frequency, because the most frequent words co-occur with almost everything and therefore dominate the first principal direction. This is a well-known artifact of SVD applied to count matrices. Removing or downweighting the first few dimensions can sometimes improve downstream task performance by exposing more detailed semantic structure that would otherwise be obscured by the frequency signal.

SVD dimensions are also sensitive to corpus domain. The same vocabulary represented with LSA on scientific articles will produce very different embeddings than LSA on news articles or literary fiction, because the co-occurrence statistics differ substantially across these domains. This domain sensitivity is both a limitation and a useful property. As a limitation, it means LSA embeddings do not transfer cleanly across domains: embeddings trained on medical texts may poorly represent the everyday senses of medical terms as they appear in general text. As a feature, it means embeddings can be specialized to a domain by choosing the training corpus carefully. A medical NLP system benefits from training its LSA on clinical notes, and a legal NLP system benefits from training on court documents.

Understanding which dimensions correspond to which semantic properties is a useful research exercise but not necessary for practical use. The embeddings can be used directly for cosine similarity computation, nearest-neighbor retrieval, and downstream task inputs without any interpretation of individual dimensions.

It is tempting to equate SVD dimensions with "topics," but the relationship is more complex. SVD dimensions are not topics in the sense of coherent themes with interpretable word distributions. They are mathematical abstractions that together span the semantic space of the corpus. Any individual word is represented as a weighted combination of all $k$ dimensions simultaneously. A word like "python" might have a large loading on a "programming languages" dimension, a smaller loading on a "biology/animals" dimension, and moderate loadings on several other dimensions.

The critical difference from topic models is that SVD dimensions can have negative loadings. In topic models, every word has a non-negative probability for every topic. In SVD, words can be "opposite" to a dimension: a word with a strongly negative loading on a dimension contrasts with words that have strongly positive loadings. This signed structure allows SVD to represent opposing semantic categories in a way that standard topic models cannot.

Let us trace through a small LSA example to build concrete intuition. Consider a toy PPMI matrix for six words ("cat," "dog," "python," "java," "bank," "river") against four context words ("pet," "code," "money," "water"). A plausible set of PPMI values might look like this:

This $6 \times 4$ matrix has clear block structure. SVD decomposes it as $\mathbf{M} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T$. Let's trace through what happens in each component.

The first singular value will be the largest. The corresponding left singular vector $\mathbf{u}_1$ will have large positive loadings for words with strong, concentrated co-occurrence patterns. Since "cat" and "dog" together account for most of the mass in the "pet" column, and "python" and "java" account for most of the mass in the "code" column, the first singular vector will roughly weight the animal and programming words equivalently (they both form strong clean blocks), while the first right singular vector $\mathbf{v}_1$ will split between "pet" and "code."

The second singular vector $\mathbf{u}_2$ captures the next most important contrast after removing the first component. With the dominant "frequent words co-occur a lot" effect removed, $\mathbf{u}_2$ likely separates the animal cluster from the programming cluster, or the financial/geographic words from both.

After truncating to $k=2$ dimensions, each word becomes a 2D point given by the corresponding row of $\mathbf{U}_2 \boldsymbol{\Sigma}_2$. The resulting geometry reflects the matrix structure:

• "Cat" and "dog" land near each other, because their PPMI profiles are nearly identical (both have high loading on "pet" and zero elsewhere).
• "Python" and "java" land near each other, for the same reason (both load heavily on "code").
• "Bank" lands in an intermediate region, because its PPMI profile is spread across "money" and "water" rather than concentrated in either animal or programming contexts.
• "River" lands near its dominant context "water," somewhat near "bank" but displaced toward the nature pole.

The 2D embedding has turned a 4-dimensional sparse representation into a 2-dimensional dense one. The key semantic groupings are preserved, and the intermediate position of "bank" correctly reflects its ambiguity across two contextual domains.

This toy example illustrates why SVD-based compression is often described as semantically meaningful by construction: the truncated dimensions keep the directions that explain most of the co-occurrence variance, and those directions correspond to the dominant thematic contrasts in the corpus.

Let us implement LSA from scratch to see each step clearly, then compare with scikit-learn's TruncatedSVD for practical use.

First, we install and import all required libraries:

We start with a small corpus to build a word-context co-occurrence matrix, then apply PPMI weighting as covered in the previous chapter. The corpus spans two distinct domains (animals and programming) and includes "bank" as a deliberately ambiguous word that bridges finance and geography:

Most entries are zero. This reflects the sparsity typical of real co-occurrence matrices. PPMI has converted raw counts into meaningful association scores, and now we apply SVD to compress these into dense embeddings.

We use numpy's linalg.svd to compute the full decomposition, then examine the singular value spectrum. The full_matrices=False option returns the economy (thin) SVD, which computes only $r = \min(m, n)$ components rather than the full square matrices:

The first few components capture most of the variance. The rapid drop-off in singular values tells us the PPMI matrix has measurable low-rank structure: only a few latent dimensions are needed to capture the essential patterns, and the remainder is noise.

We form the word embeddings by projecting onto the top $k$ singular vectors, scaling each coordinate by the corresponding singular value. The scaling is important: it ensures that the distance between embeddings in the truncated space reflects the contribution of each dimension to the original matrix:

The embedding coordinates directly reflect the semantic structure. Words from the same domain cluster together in the 2D space, and the ambiguous word "bank" should occupy an intermediate position. This reflects its membership in both the finance and nature clusters.

A 2D scatter plot lets us see the semantic geometry directly:

Visualizing the singular value decay curve helps guide the choice of $k$ and reveals how much low-rank structure the corpus contains:

The left panel shows the characteristic "elbow" shape: a few large singular values followed by a rapid drop to a flat tail. The right panel shows that just a few components explain the majority of variance in this small matrix. In a real corpus with hundreds of thousands of words, the number of components needed to reach 80% explained variance would be much larger, but the qualitative shape of both curves would be similar.

One of the most important tests for embedding quality is whether semantically similar words have high cosine similarity. Cosine similarity measures the angle between two vectors, ranging from -1 (opposite directions) to +1 (same direction), with 0 indicating orthogonality. Unlike Euclidean distance, cosine similarity is invariant to vector magnitude, which makes it reliable when comparing words that vary in frequency:

The similarity scores validate that LSA has captured domain structure. Within-domain pairs ("cat vs dog" and "python vs java") score much higher than cross-domain pairs ("cat vs python"). The ambiguous word "bank" shows moderate similarity to both finance-related and nature-related words, correctly reflecting its distributional ambiguity. This is LSA working as intended: the compressed representations encode the distributional patterns of the training corpus.

For real-world use with large sparse matrices, scikit-learn's TruncatedSVD is far more efficient than full SVD. It uses randomized SVD internally, handles sparse inputs natively, and provides variance explained metrics directly:

Note that TruncatedSVD.fit_transform returns the matrix $\mathbf{U}_k \mathbf{\Sigma}_k$ directly: the row embeddings already incorporate the singular value scaling. The output shape of (vocab_size, k) gives one $k$-dimensional embedding per word, ready for downstream use.

How does the choice of $k$ affect embedding quality? We can compare similarity rankings across different truncation levels to understand the tradeoff between noise reduction and semantic resolution:

The key parameters for TruncatedSVD are:

• n_components: The number of singular vectors to compute, controlling the embedding dimensionality. This is the most important parameter, and the choice follows the guidance in the section on choosing $k$ above.
• algorithm: Either 'randomized' (default, fast for large matrices) or 'arpack' (exact, better for small matrices or when high precision is needed). For most NLP applications with matrices larger than a few thousand words, 'randomized' is strongly preferred.
• n_iter: Number of power iteration steps for the randomized algorithm. More iterations improve approximation quality at the cost of computation time. The default of 4 is sufficient for most NLP matrices.
• random_state: Random seed for reproducibility when using the randomized algorithm. Always set this to ensure consistent results across runs.

To ground the abstract algebra in something concrete, let us look at how SVD dimensions correspond to semantic content in practice. The approach is to examine the top-loading words for each left singular vector: the words with the most positive and most negative loadings reveal what semantic contrast the dimension is capturing.

This analysis shows which words pull most strongly in each direction. On a toy corpus the interpretations are simple, but on a large corpus the same technique reveals meaningful semantic structure: frequency effects in early dimensions, domain contrasts in middle dimensions, and register or style contrasts in later dimensions.

Another way to understand the SVD is to visualize the loading matrix directly: plotting $\mathbf{U}_k$ as a heatmap with words on the rows and dimensions on the columns shows which words load most strongly on which components.

When introduced in 1990, LSA demonstrated that automatic, unsupervised learning could produce word representations capturing semantic similarity, without any hand-built lexicons, dictionaries, or rules. The system outperformed human performance on synonym selection tasks and enabled document retrieval that found relevant documents even when query terms did not appear in them verbatim. These results were remarkable, and they established distributional methods as a serious approach to computational semantics.

The impact extended well beyond information retrieval. LSA became a widely used tool in cognitive science: researchers used it to model how humans acquire vocabulary and how semantic memory is organized. Landauer and Dumais used LSA to argue that word co-occurrence alone, without any symbolic processing, could explain a substantial fraction of human semantic knowledge. This sparked a productive debate about the sufficiency of distributional information for capturing meaning, a debate that continues today in discussions of large language models.

Yet LSA has significant limitations that motivated the development of newer methods. The most fundamental is computational. SVD on large matrices is expensive, and even with randomized algorithms, the memory requirements for large vocabulary matrices are substantial. A production-scale vocabulary of 500,000 words produces a matrix with 250 billion potential entries. Even in sparse form with 0.1% fill, that is 250 million nonzeros at several gigabytes. The full pipeline from corpus to embeddings can take hours on modern hardware for large corpora.

More importantly, LSA operates on global co-occurrence statistics: each entry in the PPMI matrix summarizes co-occurrence across the entire corpus. This means all context is pooled together, losing positional information. The phrase "not good" co-occurs with "good" in a window, but so does "very good." LSA cannot distinguish which pattern is which because the same context word "good" gets counted in both. Negation, scope, and composition are invisible to the global count aggregation.

LSA embeddings also struggle with polysemy. The word "bank" receives a single embedding vector, regardless of whether it appears in a financial context or a geographical one. This single-vector limitation means that LSA conflates the financial sense and the riverbank sense into one mixed representation that may not be ideal for either downstream task. Word2Vec and later dense neural embeddings still share this limitation, but contextual models like ELMo and then BERT eventually solved it by producing different embeddings for each token occurrence depending on the surrounding context.

The reliance on linear algebra places a fundamental ceiling on what LSA can capture. Language meaning is not purely linear: the relationship between "not" and the words it negates requires understanding scope and semantic composition. The meaning of "kick the bucket" (idiomatically: to die) is not a linear combination of the meanings of "kick" and "bucket." Simple matrix factorization cannot capture these nonlinear relationships. Neural embedding methods, starting with Word2Vec in 2013, moved beyond these constraints by learning embeddings through prediction tasks. And transformer-based models moved even further by learning contextual, compositional representations through self-attention over the entire sequence.

Despite these limitations, LSA remains widely used today in specific applications: information retrieval, document similarity, topic exploration, and exploratory analysis of large text collections. Its theoretical guarantees (optimal rank-$k$ approximation by the Eckart-Young theorem), interpretable components, and deterministic behavior (with fixed random seed for randomized variants) make it a principled baseline against which newer methods are compared. Many practitioners find that LSA embeddings are surprisingly competitive with neural embeddings on tasks where global co-occurrence patterns are more informative than local context, particularly in domain-specific retrieval applications.

One of the most intellectually interesting aspects of LSA's legacy is its relationship to Word2Vec. In 2014, Levy and Goldberg proved that Word2Vec's skip-gram model with negative sampling is implicitly factorizing a shifted version of the PMI matrix. The neural network that Word2Vec trains is, in a precise mathematical sense, performing matrix factorization on a modified co-occurrence matrix. This result unified the statistical and neural approaches to distributional semantics, showing that the two superficially different frameworks are mathematically equivalent under certain conditions.

The implication is that the improvements of Word2Vec over LSA are not primarily due to neural networks per se, but rather due to differences in the objective (PMI with negative sampling vs. PPMI), the training procedure (stochastic gradient descent on pairs vs. batch SVD on the full matrix), and the weighting scheme (harmonic weighting of context positions vs. uniform window counts). These are meaningful differences, but they are not the difference between "neural" and "classical": they are differences in how the distributional statistics are collected and how the factorization is performed.

This insight directs attention toward what the actual engineering choices are in building good distributional embeddings, and it clarifies that the progress from LSA to Word2Vec to GloVe was incremental and cumulative, not a revolutionary break. The next chapter covers Word2Vec in detail, which builds directly on the distributional intuitions developed here while introducing the prediction-based training objective that proved empirically superior.

One practical aspect of LSA that practitioners learn quickly is its sensitivity to corpus quality. Unlike neural models, which can tolerate some noise through their implicit regularization mechanisms, SVD is quite sensitive to how the input matrix is constructed. Choices that matter significantly include:

Minimum frequency thresholds: Words that appear fewer than 5-10 times provide unreliable statistics. Including them adds noise to the low singular values and can degrade embedding quality for frequent words through the orthogonality constraint. A common rule of thumb is to exclude words appearing fewer than 5-10 times per million tokens.

Context window size: Narrower windows produce syntactically focused embeddings; wider windows produce topically focused embeddings. The right size depends on the task. Named entity recognition benefits from narrow windows; document similarity benefits from wide ones.

Subsampling: Discarding a fraction of occurrences of very frequent words (analogous to Word2Vec's subsampling) can improve embedding quality by reducing the dominance of the first SVD dimension, which often captures little more than frequency.

PPMI smoothing: Replacing the standard denominator in PPMI with a raised-power version of the context distribution (context probability raised to the power 0.75) reduces the bias toward rare contexts and improves embedding quality on word similarity benchmarks.

These choices interact with $k$ in ways that are hard to predict theoretically, making empirical tuning essential for production systems.

Singular Value Decomposition converts large, sparse co-occurrence matrices into compact, dense word embeddings by finding the most important linear dimensions of the data. The key ideas from this chapter are:

• SVD decomposes any matrix as $\mathbf{M} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T$, where the left singular vectors $\mathbf{U}$ define word space, the right singular vectors $\mathbf{V}$ define context space, and the singular values $\mathbf{\Sigma}$ measure how much variance each direction captures
• Truncated SVD retains only the top $k$ components, giving the optimal rank-$k$ approximation by the Eckart-Young-Mirsky theorem: no other rank-$k$ matrix is closer to the original under the Frobenius norm
• LSA applies truncated SVD to word-context or term-document matrices to discover latent semantic dimensions, enabling words that never co-occur directly to have high similarity if they share distributional neighborhoods
• The singular value spectrum guides the choice of $k$: retain components before the elbow in the scree plot, and validate with downstream task performance
• Exact SVD is $O(V^3)$ but sparse matrix algorithms and randomized SVD bring this to practical levels; scikit-learn's TruncatedSVD handles large sparse matrices efficiently with the randomized algorithm
• Randomized SVD achieves near-exact results by projecting to a random low-dimensional subspace first, then computing exact SVD of the smaller projected matrix; this reduces computation from $O(k \cdot \text{nnz})$ to a much faster constant-factor improvement
• SVD dimensions are not directly interpretable but reflect real semantic structure; examining top-loading words for each dimension reveals the semantic contrasts it captures
• LSA captures global co-occurrence patterns but cannot handle polysemy, negation, or compositional meaning; these limitations motivated the transition to neural approaches
• Word2Vec implicitly performs matrix factorization on a shifted PMI matrix, unifying the neural and algebraic traditions and showing that the progress from LSA to Word2Vec was a matter of objective and training procedure rather than a categorical shift in methodology

Ready to test your understanding? Take this quick quiz to reinforce what you've learned about Singular Value Decomposition and Latent Semantic Analysis.