Draft

Representation learning is matrix factorisation

Word embeddings, recommender systems, topic models, PCA. Four techniques, four corners of machine learning, four different-looking toolboxes. Underneath, they are one operation.

Take a large, sparse table of what-relates-to-what — which words occur near which words, which users rated which films, which terms appear in which documents. Approximate that table as the product of two smaller, dense tables. The rows of those dense tables are the vectors we call embeddings.

That is the whole idea: matrix factorisation as representation learning. This article follows it from raw co-occurrence counts, through the classical SVD route, to word2vec and GloVe — and then makes the jump that makes the concept stick: to the recommender systems that run the identical math on a completely different matrix. Once you see the lens, a dozen methods collapse into one.

Rung 4 of the linear-algebra guided map — the reframe that turns the PCA machinery into a single lens over embeddings, recommenders, and topic models.

It starts with a table

Every method here begins with the same object: a big table of co-occurrences.

For words, the table counts how often each word appears near each other word. Slide a window across a corpus and tally. For the sentence the cat sat on the mat with a ±2 window:

           the   cat   sat   on   mat
   the   [   0,    1,    2,    1,    1 ]
   cat   [   1,    0,    1,    1,    0 ]
   sat   [   2,    1,    0,    1,    0 ]
   on    [   1,    1,    1,    0,    1 ]
   mat   [   1,    0,    0,    1,    0 ]

Each row is one word; each entry M[i, j] is how often word j showed up in word i’s window. That row is already a vector for the word — it just has one slot for every word in the vocabulary. At real scale that is the problem: a vocabulary of a million words gives a million-by-million table, almost entirely zeros, because the overwhelming majority of word pairs never co-occur. Far too wide to use directly — and a sparse row of mostly zeros is a poor representation, since two words with similar meanings can still share very little exact overlap in their raw counts.

What factorisation does

The fix is factorisation: approximate the wide table M as the product of two much narrower ones.

      M             ≈        A          ·        Bᵀ
  (N × V)                 (N × d)              (d × V)
  the wide,               one dense            one dense
  sparse table            row per word         column per
                          — the embeddings     context word

d is small — a few hundred — where V is the whole vocabulary. Each row of A is a d-dimensional dense vector, and A is chosen so that A · Bᵀ reconstructs the original table M as closely as possible.

Why can a V-wide table be squeezed into d columns with so little loss? Because M is deeply redundant. Words do not co-occur in a million independent patterns; they co-occur in a few hundred. Whole groups of words — days of the week, country names, cooking verbs — share almost the same co-occurrence profile. Factorisation discovers those few hundred underlying patterns and writes every word as a short recipe over them. The row of A for cat is no longer “how often cat appeared next to each specific word”; it is “how much cat participates in each of the d dominant co-occurrence patterns.”

The linear-algebra word for that redundancy is rank — the number of truly independent rows in M. Every other row is a linear combination of those few; everything else is a copy. If M had exact rank d, the factorisation M = A · Bᵀ would hold perfectly with A and B only d columns wide: the d rows really would be all the information there is, and every other word would be a recipe over them.

Real co-occurrence matrices are not perfectly low-rank — but their singular values, the numbers measuring how much variance each direction carries, drop off a cliff after a few hundred. Mathematically the matrix is high-rank; practically it is approximately low-rank, which is exactly the condition that lets a modest d reconstruct almost everything. The chain underneath every method in this article is then:

rank                     =  number of independent patterns          (counting)
factorisation            =  expressing M in terms of those patterns (extraction)
low-rank approximation   =  keeping only the strongest ones         (compression)
embedding                =  a row of the low-rank approximation     (representation)

Reading down: each step is the previous one made more useful. Rank is the diagnosis; factorisation is the surgery; low-rank approximation is the practical compression; the embedding is what you walk away with.

In practice, steps 2 and 3 are one operation, not two. Nobody computes a full-rank factorisation and then truncates it — SVD-based methods (LSA, PCA) do a truncated SVD in one call; loss-based methods (GloVe, recommender MF, NMF) bake the chosen rank d into the model and fit it with gradient descent. Word2vec compresses further still, skipping even the matrix and producing the rows of A directly via SGD — with Levy & Goldberg’s result (covered next) certifying you would have got the same answer the long way.

An embedding is a row of a factorised co-occurrence matrix. Everything else in this article is a variation on how you build M and how you compute the factorisation.

The classical route: SVD

The oldest way to compute that factorisation is singular value decomposition (SVD), a piece of linear algebra far older than machine learning. SVD factors any matrix exactly, and the Eckart–Young theorem guarantees that truncating it to d dimensions gives the best possible rank-d approximation of M. Keep the d directions of greatest variance, drop the rest, and you have your (N, d) table.

This is not a recent idea dressed up. Latent semantic analysis (LSA, 1990) is exactly truncated SVD of a term-by-document matrix; it was doing information retrieval long before anyone said “embedding.” HAL (1996) did the same on a word-by-word matrix to model human semantic memory. Both produced dense word vectors — as a byproduct of other goals. PCA is the same operation once more: run SVD on a mean-centred data matrix and the top components are the principal axes. PCA, LSA, HAL — one algorithm, three names, three research communities.

The catch is cost. Classical SVD of a V × V matrix, with V in the millions, is enormous to store and heavier still to factor. By the early 2010s this count-then-factor recipe was the standard, and nobody loved it.

How is it actually computed?

If you have taken a linear algebra course, the natural thought is: to find the rank and pull out the independent rows, just row-reduce the matrix — Gaussian elimination, the algorithm you applied by hand to drive a small matrix down to row echelon form. And there is a beautiful payoff to that intuition: Gaussian elimination, written down formally, is a factorisation. It is called LU decomposition — M = L · U, with U upper triangular (the reduced matrix) and L lower triangular (a record of the elimination multipliers). Row reduction and matrix factorisation are the same operation in that one specific case.

To make that concrete, take a small 3 × 3 matrix and run the algorithm by hand:

M = | 2  1  1 |
    | 4  3  3 |
    | 8  7  9 |

Step 1 — clear column 1 below the pivot. The pivot is the 2 in row 1, column 1. We want zeros below it. Row 2 has a 4 there, so subtracting 4 / 2 = 2 copies of row 1 from row 2 cancels the 4. Row 3 has an 8, so subtracting 4 copies of row 1 from row 3 cancels the 8:

R2 ← R2 − 2 · R1      [4, 3, 3] − 2·[2, 1, 1]  =  [0, 1, 1]
R3 ← R3 − 4 · R1      [8, 7, 9] − 4·[2, 1, 1]  =  [0, 3, 5]

The matrix after step 1:

| 2  1  1 |
| 0  1  1 |
| 0  3  5 |

Step 2 — clear column 2 below the new pivot. The pivot is now the 1 in row 2, column 2. Row 3 has a 3 there, so subtracting 3 copies of row 2 from row 3 cancels the 3:

R3 ← R3 − 3 · R2      [0, 3, 5] − 3·[0, 1, 1]  =  [0, 0, 2]

The matrix after step 2 — the row echelon form your linear algebra lesson is producing:

| 2  1  1 |
| 0  1  1 |   ←  this is U
| 0  0  2 |

Three nonzero rows: rank is 3, so this particular M has no redundancy at all.

Now the trick. The three multipliers we used — 2, 4, and 3 — were each chosen so that a specific cell of M would become zero. Each multiplier therefore captures exactly how much of one earlier row was “inside” a later row of M. Drop each into the lower-triangular cell of L that points to the same row-op, and put 1s on the diagonal:

L = | 1  0  0 |     row 1 wasn't modified — it stays as itself
    | 2  1  0 |     the 2 we used to clear (row 2, col 1)
    | 4  3  1 |     the 4 cleared (row 3, col 1); the 3 cleared (row 3, col 2)

The diagonal is 1 because each row contains “one copy of itself”; the cells above the diagonal are 0 because the algorithm never used a later row to clean an earlier one.

And the product checks out exactly:

L · U  =  | 1  0  0 |     | 2  1  1 |     | 2  1  1 |
          | 2  1  0 |  ·  | 0  1  1 |  =  | 4  3  3 |  =  M
          | 4  3  1 |     | 0  0  2 |     | 8  7  9 |

To see why, it helps to read matrix multiplication a particular way. Each row of L · U is a weighted sum of U’s rows, with the weights given by the corresponding row of L. So row 2 of the product is built like this:

row 2 of L · U  =  2 · row1(U)   +  1 · row2(U)   +  0 · row3(U)
                =  2 · [2, 1, 1] +  1 · [0, 1, 1] +  0 · [0, 0, 2]
                =  [4, 2, 2]     +  [0, 1, 1]
                =  [4, 3, 3]                                  ← matches row 2 of M

Read backwards: row 2 of M is two copies of row 1 of U, plus one copy of row 2 of U — which is exactly the inverse of what we did during elimination (“subtract two copies of row 1 from row 2”). The numbers in L are the recipe for reconstructing the original rows of M from the reduced rows of U.

So the multipliers you subtracted during row reduction were not being thrown away — they were the other factor. Gaussian elimination is bookkeeping: as you transform M into U, the multipliers used to do it quietly assemble into L, and the algorithm’s full output is the pair (L, U).

But for the embedding case, row reduction has two fatal problems: it is O(N³) — hopeless on a million-word vocabulary — and it produces a square full-rank decomposition (L and U are both N × N, as the example above made visible), not the tall-skinny (N, d) table you want. So the algorithms that produce embeddings use one of two fundamentally different approaches.

Iterative SVD: query the matrix, never transform it. Real SVD on a huge sparse matrix is not done by the textbook eigenvalue formula. Algorithms like power iteration, Lanczos, and randomised SVD work by repeatedly multiplying M by a vector and watching what comes out — after a few rounds, the dominant singular directions emerge from the cumulative product. The matrix is never modified; it is only ever asked questions of the form “what does multiplying by you do to this vector?” That is how LSA, HAL, and PCA scale to real corpora.

Loss-based fitting: ignore M’s rows entirely. GloVe, recommender MF, NMF, and topic models go further still — they never operate on M as a matrix at all:

1. start with random A (N × d) and random B (V × d)
2. compute the loss: how badly does A · Bᵀ reconstruct M?
3. compute gradients of that loss with respect to A and B
4. nudge A and B downhill
5. repeat until convergence

M is only evaluated cell by cell as part of the loss. The factorisation emerges from optimisation, not algebra — and the rank constraint is the model itself: A and B are forced to be d columns wide by construction. There is no separate “factor first, truncate later”; the low-rank-ness is baked in from the start.

So three flavours of “how to factorise,” each with a different relationship to M:

LU / Gaussian elimination  →  transforms M directly, exact, O(N³)
                              best for solving A x = b and small exact rank
iterative SVD              →  queries M via repeated multiplication, never modifies it
                              best for dominant singular directions of huge sparse M
loss-based factorisation   →  doesn't touch M's rows; fits A · Bᵀ by gradient descent
                              best for custom losses, missing entries, streaming data

What stays the same across all three is the goal: find the small number of independent patterns that explain M. What changes is how you get there — transform, query, or fit. Row reduction is one exact way that works on small matrices; for the giant sparse matrices behind embeddings, the algorithms had to be reinvented because exact transformation is not tractable.

word2vec and GloVe factorise the same matrix

The 2013 wave — word2vec, then GloVe — did not abandon factorisation. It changed how the factorisation is computed, trading exact linear algebra for gradient descent.

GloVe is the honest case: it still builds the co-occurrence matrix explicitly. What it changes is the factor step. Instead of SVD, it learns vectors u, v and biases by minimising a weighted least-squares loss — fitting u_i · v_j + b_i + b_j to log X_ij — with gradient descent over the nonzero cells. Same matrix, same goal of a (V, d) factor table, a different solver.

word2vec looks like it has nothing to do with matrices at all. It never builds one. It streams (center, context) word pairs out of the corpus and nudges two embedding tables with SGD, one pair at a time. And yet — this is the keystone result — Levy & Goldberg (2014) proved that word2vec’s skip-gram-with-negative-sampling objective is implicitly factorising a matrix: a shifted pointwise-mutual-information matrix of exactly the co-occurrence statistics it streams past. The matrix is never materialised in memory, but the vectors word2vec lands on are the vectors you would get by factorising it.

So the method that looks least like matrix factorisation is matrix factorisation too. That is the moment the lens locks into place: it is not that several embedding methods happen to resemble factorisation — it is that producing an embedding is factorising an interaction matrix, whether or not the matrix is ever written down.

One cousin sits outside this story. fastText is word2vec with each word’s vector replaced by the sum of its character-n-gram vectors. That is a change to the representation — what a word vector is built from — not to which matrix gets factorised or how. It is a genuinely useful trick (morphology and out-of-vocabulary words come for free), but it is orthogonal to the factorisation lens. The factorisation story is about the table; fastText is about the row.

The same trick runs your recommendations

Here is the jump that makes the concept worth carrying around. Leave language behind entirely and look at a recommender system.

A streaming service has a table R of which user gave which film which rating:

            Inception   Toy Story   Heat   Amélie   ...
   Alice  [     5           ·         4       ·     ... ]
   Bob    [     ·           2         ·       5     ... ]
   Carol  [     4           ·         5       ·     ... ]
    ...

It is a big, overwhelmingly empty table — every user has rated a tiny fraction of the catalogue. The · cells are exactly the ones you want to predict.

The method that won the Netflix Prize and still underpins recommendation at scale: factorise R ≈ U · Vᵀ. The rows of U are user embeddings, the rows of V are film embeddings, both in the same d-dimensional space. A missing rating is predicted as the dot product of a user row and a film row. Fit only the cells you actually observed — exactly as GloVe fits only the nonzero co-occurrence cells — and the rest of the table fills itself in.

Look at what falls out of that factorisation. Films cluster: heist thrillers near heist thrillers, Pixar near Pixar. Users cluster by taste. “People who liked this also liked that” is just dot-product proximity in the film embedding space — the same geometric relationship as king − man + woman ≈ queen in the word embedding space.

Same operation. The only thing that changed is the matrix: words × contexts became users × films. Swap in documents × terms and you have topic modelling; customers × products, papers × citations, nodes × neighbours — each one is the same factorisation with a different table on the left.

So what is an embedding?

Pulling it together, the lens gives a one-sentence definition: an embedding is a row of a factorised interaction matrix.

That reframes a long list of methods as a single recipe with two slots — which interaction matrix, and how you factor it:

method           interaction matrix          factorisation
──────────────────────────────────────────────────────────────────
LSA / HAL        word × context counts        truncated SVD
PCA              (centred) data matrix        SVD / eigendecomposition
GloVe            word × context counts        weighted least squares (GD)
word2vec         word × context (implicit)    SGD on streamed pairs
recommender MF   user × item ratings          least squares (SGD / ALS)
topic models     document × term counts       non-negative factorisation
node embeddings  graph adjacency / walks      SGD on sampled walks

Reading down the right-hand column, the differences are engineering choices — exact versus iterative, explicit matrix versus streamed, which loss, which weighting. Reading across, the thing being produced is always the same: an (N, d) table of dense rows whose geometry encodes similarity.

So when you meet a new “embedding” method, the lens hands you the two questions that actually matter: what is the interaction matrix, and how is it being factored? Answer those and you understand the method.

Does this still matter in the age of transformers?

In 2026 you would not train a word2vec or GloVe model for any task that cares about meaning — a transformer embedding does it better. So is the factorisation lens a historical curiosity?

No, for three reasons.

It is still running in production — under recommendations and retrieval. Matrix factorisation never left recommender systems; it is cheap, fast, and interpretable. And the two-tower / dual-encoder retrieval models behind modern search and RAG are factorisation in spirit — encode queries and documents into a shared space, score by dot product, which is exactly A · Bᵀ with learned encoders standing in for lookup tables.

It explains what a transformer is doing. The input embedding table at the bottom of every transformer is still a (V, d) factor table — the same object this article has been describing. Attention then learns context-dependent interactions on top of it, which you can read as factorising a far richer, input-specific interaction matrix instead of one fixed global one. The transformer did not discard the idea; it made the matrix dynamic.

It powers modern ML far beyond embeddings. Three quick examples to make the point:

LoRA (Low-Rank Adaptation) — the dominant way to fine-tune large language models cheaply. Instead of updating a huge weight matrix W directly, you learn a low-rank update ΔW = A · B with tiny A and B. Pure matrix factorisation, applied to weight deltas instead of data — same math, completely different setting.
Knowledge-graph embeddings (RESCAL, DistMult, ComplEx) — factor an (entity × relation × entity) tensor for link prediction. The same operation generalised one dimension up.
Spectral graph methods — eigendecomposition of an adjacency or Laplacian matrix for community detection, graph clustering, and spectral embeddings. The classical SVD / eigendecomposition route, applied to graphs.

The methods age. The lens does not. “Where do these vectors come from?” almost always has the same answer: some interaction matrix got factorised — and knowing which one, and how, is most of what you need to understand any representation-learning system you will meet.