Definition
Truncated SVD computes only the largest singular values and their singular vectors of a data matrix ( rows × features), without subtracting the column means first. It maps every row to numbers, , and gives the best rank- approximation of itself. Run on a document–term matrix, this is Latent Semantic Analysis (LSA).
At a glance
- Task
- Unsupervised linear dimensionality reduction; topic / concept extraction from text (LSA)
- Input → output
- a (usually sparse) matrix → dense coordinates
- Learns
- right singular vectors (the rows of , scikit-learn's
components_) and singular values - Training
- randomized: about ; never forms a dense matrix
- Prediction
- per new row: one sparse vector–matrix product
- Hyperparameters
n_components,algorithm(randomized / arpack),n_iter,n_oversamples; plus the input weighting (counts, tf-idf, normalisation)- Assumes
- the signal is approximately low-rank and linear; distances and angles in the input space are meaningful (so the weighting of features matters)
The problem
Text, ratings and click logs come as enormous, mostly-empty matrices. A corpus of a million documents over a 100,000-word vocabulary with ten non-zero counts per row has non-zeros: about 0.12 GB in sparse CSR format. The obvious way to compress it is PCA, but PCA first subtracts each column's mean. The mean of a word column is not zero, so after centring every one of the entries is non-zero, and the dense matrix needs 800 GB. A full SVD would then cost on top. Neither fits in memory.
Text has a second problem. Search by matching words fails on synonyms: a query for auto has cosine similarity exactly 0 with a document that only says car, because the two share no word. We want a representation in which words that appear in the same contexts end up close together.
The idea
Skip the centring and factorise as it is. Every matrix can be written as a sum of rank-1 pieces , sorted by size (the full theory is in the SVD article). Keep only the largest pieces and drop the rest. Each kept right singular vector is a weighted mix of features, which in text reads as a latent concept (vehicles, fruit). Each document is described by how much of each concept it contains. Words that co-occur, or that share neighbours like car and auto both sharing engine, load on the same concepts, so documents that use different words for the same thing land close together.
Because only products like and are ever needed, the algorithm can work directly on the sparse matrix, touching only its non-zeros. That is why it scales: the cost grows with , not with .
Vocabulary
- Singular value σᵢ
- the length of along direction : . Sorted
- Right singular vector vᵢ
- a unit vector in feature space (one weight per term), the -th component. Stored as row of
components_ - Left singular vector uᵢ
- a unit vector over the rows: . Document coordinates are
- Rank-k approximation
- , the closest rank- matrix to
- Energy
- the fraction of kept by the first components
- Latent space / concept
- the -dimensional space of coordinates ; each axis is a concept (a weighted mix of words)
- Fold-in
- projecting a new row, e.g. a search query, into the latent space with the learned :
- LSA / LSI
- Latent Semantic Analysis / Indexing: truncated SVD of a (tf-idf) document–term matrix, used for retrieval and similarity
- Sketch, oversampling, power iteration
- randomized SVD ideas: multiply by a random matrix to capture its top range ( = extra oversamples), and repeat times with (power iterations) to sharpen it
The math
Start from the thin SVD of the uncentred matrix and cut it after terms:
- data matrix, rows = samples (documents), columns = features (terms); not centred
- rank of , at most
- , orthonormal columns (left singular vectors)
- diagonal matrix of the largest singular values
- , orthonormal columns (right singular vectors = components)
Why truncation is the right thing to do (Eckart–Young). Among all matrices of rank at most , is the closest to , and the leftover error is exactly the energy in the dropped singular values:
- Frobenius norm,
- equals , the total sum of squared entries
This is how acts mathematically: raising by one removes from the squared error. The singular-value spectrum tells you directly how much each extra component buys.
The transform. The reduced coordinates are the projection of each row onto the components. Since is the identity stacked on zeros, the projection collapses to the first columns of :
- document coordinates (what
fit_transformreturns) - a new row in the same feature space, e.g. a query's term counts
- its latent coordinates; compare to rows of by cosine similarity
Where the components come from. Substitute the SVD into the Gram matrix: . So the are the eigenvectors of and are its eigenvalues; maximises over unit vectors. Compare PCA, which diagonalises the covariance . Without centring, is a matrix of second moments about the origin, so for non-negative data points roughly along the mean vector . In the worked example below, . Centre first and truncated SVD returns exactly the PCA components.
The randomized algorithm (Halko, Martinsson & Tropp). Finding the top- eigenvectors does not need the whole spectrum. Draw a Gaussian . Then is a set of random combinations of 's columns, which with high probability spans the top- left singular directions. Power iterations multiply by before orthonormalising:
- random Gaussian test matrix
- oversamples (default 10): extra random directions that absorb error from the tail
- power iterations (
n_iter); each one raises every singular value to a higher odd power - orthonormal basis for the range of
- small matrix; its exact SVD is cheap
The factor is the key to tuning . The tail directions pollute the sketch in proportion to , so each iteration shrinks that ratio geometrically. Text spectra decay slowly (), which is why scikit-learn defaults to rather than 0. Oversampling works alongside it: with random directions instead of , the chance that the sketch misses part of the top- subspace falls very quickly. Every step needs only the products and , which is on a sparse matrix.
Worked example: LSA on seven tiny documents
Six terms, seven documents. Three are about vehicles, three about fruit, and D7, apple car, mixes both. The matrix holds raw counts; 16 of its 42 entries are non-zero. We keep components and then search for the one-word query auto.
| Doc | Text | car | auto | engine | fruit | apple | juice |
|---|---|---|---|---|---|---|---|
| D1 | car car engine | 2 | 0 | 1 | 0 | 0 | 0 |
| D2 | auto auto engine | 0 | 2 | 1 | 0 | 0 | 0 |
| D3 | car auto engine engine | 1 | 1 | 2 | 0 | 0 | 0 |
| D4 | fruit fruit apple | 0 | 0 | 0 | 2 | 1 | 0 |
| D5 | apple apple juice | 0 | 0 | 0 | 0 | 2 | 1 |
| D6 | fruit apple juice juice | 0 | 0 | 0 | 1 | 1 | 2 |
| D7 | apple car | 1 | 0 | 0 | 0 | 1 | 0 |
Rank-2 truncated SVD by hand
- 1Gram matrix. (6 × 6), e.g. and . The full matrix is in the table below. Note that has no centring and is block-structured: vehicle terms only touch fruit terms through D7's car–apple entry .
- 2Top eigenpairs of G. , , so and , with and over (car, auto, engine, fruit, apple, juice). Check one entry of for car: and (using 4-decimal ).
- 3Read the components. is all-positive: it is the "how many words, of any kind" axis, almost parallel to the column-mean vector (). is the topic contrast: positive on car / auto / engine, negative on fruit / apple / juice.
- 4Document coordinates . D1 . D7 , which sits between the topics. All seven are in the next table.
- 5How much is kept. (sum of squared counts). Energy , and . The rank-2 reconstruction gives D1 an auto entry of , even though D1 never contains the word.
- 6Fold in the query “auto” : the auto row of .
- 7Cosine to D1. ; , , so . In raw count space it was .
- 8Rank the documents (table below). Latent space: D2 (1.000), D3 (0.998), D1 (0.993), then D7 (0.542). The fruit documents score about to . The search found D1 through the shared context word engine.
| G | car | auto | engine | fruit | apple | juice |
|---|---|---|---|---|---|---|
| car | 6 | 1 | 4 | 0 | 1 | 0 |
| auto | 1 | 5 | 4 | 0 | 0 | 0 |
| engine | 4 | 4 | 6 | 0 | 0 | 0 |
| fruit | 0 | 0 | 0 | 5 | 3 | 2 |
| apple | 1 | 0 | 0 | 3 | 7 | 4 |
| juice | 0 | 0 | 0 | 2 | 4 | 5 |
| Doc | z₁ | z₂ | raw cosine | latent cosine (k = 2) |
|---|---|---|---|---|
| D1 | 1.265 | 1.253 | 0.000 | 0.993 |
| D2 | 1.037 | 1.277 | 0.894 | 1.000 |
| D3 | 1.595 | 1.793 | 0.408 | 0.998 |
| D4 | 1.192 | −1.096 | 0.000 | −0.074 |
| D5 | 1.468 | −1.284 | 0.000 | −0.049 |
| D6 | 1.633 | −1.523 | 0.000 | −0.081 |
| D7 | 0.953 | −0.093 | 0.000 | 0.542 |
The same mechanism works on terms. Their latent vectors are the rows of , and the cosine between car and auto rises from (raw document columns) to . The rank-2 model has learned that they are used interchangeably.
The algorithm, step by step
Randomized truncated SVD (scikit-learn's default)
- 1Weight the input (optional but standard for text): counts → tf-idf, often with sublinear tf. Keep it sparse.
- 2Sketch. Draw with entries; (, dense but thin).
- 3Power iterations ( times): ; ; . Re-orthonormalising (QR or LU) each time stops all columns from collapsing onto in floating point.
- 4Basis. , with orthonormal columns spanning the approximate top range of .
- 5Project and solve small. (); compute its exact SVD .
- 6Lift and cut. ; keep the first columns of , values of , rows of . Fix signs so the largest-magnitude entry of each is positive (singular vectors are only defined up to sign).
- 7Transform. for training rows and for new ones.
Complexity
- Randomized
- for the sparse products + for QR and the small SVD. Memory: plus
- ARPACK (Lanczos)
- iterative eigen-solver on via repeated , products. More accurate for small , often slower for large , not parallel-friendly
- Full SVD, for contrast
- time and a dense copy, impossible at the 1M × 100k scale above
- Transform
- per row
Variants and tuning
| n_iter q | max relative error | σ₁₀ estimate |
|---|---|---|
| 0 | 0.439 | 12.137 |
| 1 | 0.142 | 14.286 |
| 2 | 0.090 | 15.159 |
| 4 | 0.047 | 15.865 |
| 7 | 0.025 | 16.240 |
A random sketch always underestimates the singular values: it sees the right directions only partially. Each power iteration pulls the estimates up towards the truth. Flat spectra like this one, typical of sparse data, need several iterations.
Knobs that matter
- n_components k
- for LSA, 100–300 is the classic range for retrieval and clustering; for visualisation, 2–3. Pick by the energy curve, or better, by downstream validation score (retrieval precision, classifier accuracy). The energy curve of text has no clear elbow
- algorithm
randomized(default, fast, large fine) vsarpack(Lanczos, exact to tolerancetol, needs )- n_iter q
- default 5. Raise it for slowly decaying spectra or when components look noisy across seeds; each one costs two more passes over
- n_oversamples p
- default 10. Raise it (e.g. 20–50) when k is small relative to a flat spectrum
- Input weighting
- tf-idf instead of counts stops frequent words dominating . L2-normalise rows (or use
Normalizerafter the SVD) so cosine compares topics, not document lengths - Centring
- dense data that fits in memory: just use PCA, which centres. Sparse data: truncated SVD, or scikit-learn's
PCAwithsvd_solver="arpack"/"covariance_eigh", which centre implicitly without densifying (recent versions)
Related methods: NMF factorises the same non-negative matrix but forces non-negative, parts-based components that read more like topics. LDA (latent Dirichlet allocation) is the probabilistic topic-model successor of LSA. Incremental / streaming SVD (e.g. gensim's LsiModel) updates the factorisation in chunks when the corpus doesn't fit on one machine.
In code
1import numpy as np23def truncated_svd(X, k, n_oversamples=10, n_iter=4, seed=0):4 """Randomized truncated SVD (Halko et al., 2011). X may be a NumPy or scipy.sparse matrix."""5 rng = np.random.default_rng(seed)6 n, d = X.shape7 l = min(k + n_oversamples, d)8 Q = X @ rng.standard_normal((d, l)) # n x l sketch of the column space9 for _ in range(n_iter): # power iterations sharpen the spectrum10 Q, _ = np.linalg.qr(Q)11 Q, _ = np.linalg.qr(X.T @ Q)12 Q = X @ Q13 Q, _ = np.linalg.qr(Q) # orthonormal basis for range(X)14 B = (X.T @ Q).T # small l x d matrix B = Q^T X15 Ub, s, Vt = np.linalg.svd(B, full_matrices=False)16 U = Q @ Ub17 U, s, Vt = U[:, :k], s[:k], Vt[:k]18 flip = np.sign(Vt[np.arange(k), np.abs(Vt).argmax(axis=1)]) # largest |entry| of each v positive19 return U * flip, s, Vt * flip[:, None]2021terms = ["car", "auto", "engine", "fruit", "apple", "juice"]22X = np.array([[2, 0, 1, 0, 0, 0], [0, 2, 1, 0, 0, 0], [1, 1, 2, 0, 0, 0],23 [0, 0, 0, 2, 1, 0], [0, 0, 0, 0, 2, 1], [0, 0, 0, 1, 1, 2],24 [1, 0, 0, 0, 1, 0]], dtype=float)2526U, s, Vt = truncated_svd(X, k=2)27Z = U * s # document coordinates = X @ V_k28print("singular values:", s.round(4))29print("V_k^T:\n", Vt.round(4))30print("docs in LSA space:\n", Z.round(4))31print("||X - X_k||_F =", round(np.linalg.norm(X - Z @ Vt), 4))3233q = np.array([0, 1, 0, 0, 0, 0.]) # query: "auto"34zq = q @ Vt.T # fold in: q V_k35cos = lambda a, B: B @ a / np.linalg.norm(B, axis=1) / np.linalg.norm(a)36print("query:", zq.round(4))37print("raw cosine:", cos(q, X).round(3))38print("LSA cosine:", cos(zq, Z).round(3))1from sklearn.decomposition import TruncatedSVD2from sklearn.feature_extraction.text import CountVectorizer3from sklearn.metrics.pairwise import cosine_similarity45docs = ["car car engine", "auto auto engine", "car auto engine engine",6 "fruit fruit apple", "apple apple juice", "fruit apple juice juice",7 "apple car"]8vec = CountVectorizer(vocabulary=["car", "auto", "engine", "fruit", "apple", "juice"])9X = vec.fit_transform(docs) # scipy.sparse CSR, 16 non-zeros of 4210print(type(X).__name__, X.nnz, "non-zeros")1112svd = TruncatedSVD(n_components=2, algorithm="randomized", n_iter=5, random_state=0)13Z = svd.fit_transform(X) # = U_k Sigma_k = X V_k14print("singular values:", svd.singular_values_.round(4))15print("components:\n", svd.components_.round(4))16print("explained variance ratio:", svd.explained_variance_ratio_.round(4))17print("docs:\n", Z.round(4))1819zq = svd.transform(vec.transform(["auto"]))20print("query 'auto':", zq.round(4))21print("raw cosine:", cosine_similarity(vec.transform(["auto"]), X).round(3))22print("LSA cosine:", cosine_similarity(zq, Z).round(3))2324# Real LSA pipeline:25# make_pipeline(TfidfVectorizer(sublinear_tf=True), TruncatedSVD(200), Normalizer(copy=False))Use when
- +The data is large and sparse (tf-idf text, one-hot features, user–item matrices) and must stay sparse.
- +You need dense, low-dimensional features for retrieval, clustering or a linear classifier on text (LSA).
- +You want a fast, deterministic-given-seed, linear reduction whose transform is a single matrix product.
- +You need only the top few singular directions of a huge matrix (spectral methods, low-rank approximation).
Avoid when
- −The data is dense and fits in memory: use PCA, which centres, so components and variance ratios mean what you expect.
- −You need interpretable topics: components mix positive and negative weights; NMF or probabilistic topic models read better.
- −The structure is nonlinear (manifolds, clusters in curved shapes): see kernel PCA, t-SNE or UMAP.
- −Word order or polysemy matters: a bag-of-words SVD gives one vector per word regardless of sense; use contextual embeddings.
Where it's used
Latent semantic indexing
Search engines and document-similarity systems map tf-idf vectors to ~200 latent dimensions, so queries match documents that share no exact words.
Text classification features
TF-IDF → TruncatedSVD → logistic regression / SVM: a compact, fast pipeline for spam, sentiment and topic classification.
Recommender systems
Low-rank factorisation of sparse user–item rating or click matrices (the SVD family behind the Netflix Prize models).
Pre-step for clustering and visualisation
Reduce sparse text to 50–100 dims before k-means, or before t-SNE / UMAP, which struggle on 100k sparse dimensions.
Check yourself
Why does scikit-learn's TruncatedSVD not centre the data, unlike PCA?
Check yourself
A matrix has singular values . You keep . What are the energy kept and ?
Check yourself
In the worked example, the query “auto” has raw cosine 0 with D1 but latent cosine 0.993 at k = 2. What happens to that latent cosine at k = 6 (full rank)?
Check yourself
On non-negative count data, the first truncated-SVD component typically…
Remember
- ✓Truncated SVD keeps the top terms of the uncentred matrix: . On centred data it is exactly PCA.
- ✓Eckart–Young: is the best rank- approximation and , so the spectrum tells you what each extra component buys.
- ✓Randomized SVD needs only products with and , so it costs and keeps sparse data sparse. Power iterations () fix flat spectra.
- ✓On text (LSA), low rank merges words used in the same contexts: “auto” finds the car document (cosine 0 → 0.993). Truncation is what creates the similarity.
- ✓Without centring, component 1 ≈ the mean direction;
explained_variance_ratio_is then unsorted and misleading. Use tf-idf and row normalisation.