Definition
Non-negative matrix factorization (NMF) approximates a data matrix with no negative entries, , by the product of two smaller non-negative matrices, with and . Each row of is a part (a topic, a face feature, a spectral template), and each row of says how much of each part a sample contains. Because nothing can be subtracted, every sample is rebuilt purely by adding parts.
At a glance
- Task
- Unsupervised dimensionality reduction / matrix factorization; soft clustering and topic extraction
- Input → output
- non-negative ( samples × features) → ( weights) and ( parts)
- Learns
- non-negative basis vectors (rows of ) and a non-negative code per sample (rows of )
- Objective
- (default), or KL / Itakura–Saito divergence; non-convex, solved by alternating updates
- Training
- per iteration (sparse : ); tens to hundreds of iterations
- Prediction
- new row : a small non-negative least squares problem with fixed, per inner step
- Hyperparameters
- rank k, loss (Frobenius / KL / IS), initialization (random, NNDSVD), solver (mu, cd), L1/L2 penalties, iterations
- Assumes
- all entries ≥ 0 and meaningful as amounts (counts, intensities, power); data is a sum of a few non-negative sources
The problem
Many data sets are amounts: word counts in documents, pixel brightness in images, power in an audio spectrogram, gene expression levels, ratings. Such data is naturally a sum of parts — a document about a football club's charity bake-off is some sports vocabulary plus some cooking vocabulary.
PCA and the SVD find the best low-rank approximation, but their components mix signs. On the six-document example below, PCA's first component is over goal, team, match, oven, flour, recipe: a contrast "sports minus cooking". A document is then rebuilt by adding some components and subtracting others, so a component on its own means little — and a reconstruction can even contain negative word counts. We want components that look like the things in the data, combined only by adding.
The idea
Forbid negative numbers in both factors. Then is a sum of non-negative terms: no cancellation is possible, so a part can only be used where its words (pixels, frequencies) actually occur. To explain a count of zero, every part used by that sample must be (near) zero on that feature. The cheapest way to satisfy this is to make parts that cover disjoint groups of features and samples that use only a few parts — so NMF tends to produce sparse, localized, interpretable components without being asked to. Lee and Seung (1999) showed it on faces: PCA gives ghostly whole "eigenfaces", NMF gives noses, eyes and mouths.
Vocabulary
- Rank k
- number of parts (topics, components); the inner dimension of
- Basis / dictionary H
- ; row is part expressed over the original features (a topic's word weights)
- Coefficients / activations W
- ; row says how much of each part sample uses (a document's topic mix)
- Reconstruction
- ; the residual is
- Parts-based
- each sample is an additive combination of parts; parts are not cancelled by other parts
- Multiplicative update
- an update that multiplies each entry by a positive ratio, so a positive entry stays positive
- Fold-in
- computing for new samples with held fixed (scikit-learn's
transform) - NNDSVD
- non-negative double SVD — a deterministic initialization built from the positive parts of the leading singular vectors
The math
- data matrix, all entries
- coefficient matrix,
- basis matrix,
- rank — number of parts, usually
- Frobenius norm: square root of the sum of squared entries
The problem is non-convex in jointly (and NP-hard in general), but it is convex in for fixed and in for fixed — each half is a non-negative least squares problem. So every practical solver alternates: improve with fixed, then with fixed.
Step 1 — the gradient. Differentiating the loss with respect to (and symmetrically ):
- positive part of the gradient's negative: how strongly the data "pulls" each up
- how much of feature the current reconstruction already supplies through part
Step 2 — a gradient step with a clever step size. Ordinary gradient descent can push entries below zero. Lee and Seung chose a different step size for every entry, :
- entry-wise step size; it shrinks to 0 as the entry approaches 0, so the step can never overshoot below zero
The terms cancel and the subtraction disappears, leaving a multiplicative rule. In matrix form, with and for element-wise product and division:
- element-wise multiplication and division
- the data wants more of this entry → it grows
- the reconstruction overshoots → it shrinks
- gradient is zero for that entry (a KKT point when )
Every quantity in the ratio is non-negative, so non-negativity is preserved for free — no projection needed. Lee and Seung proved, with an auxiliary-function (majorize–minimize) argument, that each update never increases the loss. It does not guarantee the global minimum: different initializations can land in different local minima.
Other losses. For count data the Poisson-motivated (generalized) Kullback–Leibler divergence is often a better fit, and gives an equally simple update:
- generalized KL divergence; equals the negative Poisson log-likelihood up to constants
- matrix of ones
Both are members of the β-divergence family: is Frobenius, is KL, is Itakura–Saito (scale-invariant, used for audio spectrograms). Smaller pays more attention to small entries.
- overall regularization strength
- L1 ratio (scikit-learn's l1_ratio): 1 = pure L1 (sparsity), 0 = pure L2 (small, smooth entries)
With penalties the denominators simply gain the penalty's gradient: L1 adds , L2 adds . A larger denominator shrinks every entry each step, and entries with weak support are pushed to zero — the L1 term is the main knob for sparser parts.
Worked example: topics in six documents
Six short documents, counted over six words. d1–d2 are about football, d3–d4 about baking, d5–d6 mix both. We ask for parts and run the multiplicative updates from a fixed positive start.
| Doc | goal | team | match | oven | flour | recipe |
|---|---|---|---|---|---|---|
| d1 | 3 | 2 | 2 | 0 | 0 | 0 |
| d2 | 2 | 3 | 1 | 0 | 0 | 1 |
| d3 | 0 | 0 | 0 | 3 | 2 | 2 |
| d4 | 0 | 1 | 0 | 2 | 3 | 3 |
| d5 | 2 | 2 | 1 | 1 | 2 | 1 |
| d6 | 1 | 0 | 2 | 2 | 1 | 2 |
| Doc | W₀ topic 1 | W₀ topic 2 | · | H₀ row | goal | team | match | oven | flour | recipe |
|---|---|---|---|---|---|---|---|---|---|---|
| d1 | 0.6 | 0.4 | topic 1 | 0.9 | 0.7 | 0.8 | 0.4 | 0.3 | 0.5 | |
| d2 | 0.8 | 0.3 | topic 2 | 0.3 | 0.4 | 0.2 | 0.8 | 0.9 | 0.6 | |
| d3 | 0.3 | 0.7 | ||||||||
| d4 | 0.4 | 0.9 | ||||||||
| d5 | 0.5 | 0.5 | ||||||||
| d6 | 0.7 | 0.6 |
Iteration 1 by hand (W first, then H — the order scikit-learn uses)
- 1Numerator for W. , row d1: goal·0.9 + team·0.7 + match·0.8 for topic 1, and for topic 2.
- 2Denominator for W. , row d1: — what the current reconstruction already "explains" through each topic.
- 3Update row d1. (the data wants much more topic 1) and (ratio , a small increase). All six rows: d1 , d2 , d3 , d4 , d5 , d6 — the sports and baking documents already separate.
- 4Update H with the new W. Column goal: , . So and : goal moves into topic 1 and fades from topic 2.
- 5Loss after one iteration: . Repeating: (iteration 2), (3), (5), (10), (20) and from iteration 50 on — relative error .
| Doc | W topic 1 | W topic 2 | share (sports / baking) |
|---|---|---|---|
| d1 | 2.19 | 0 | 100% / 0% |
| d2 | 1.96 | 0.23 | 90% / 10% |
| d3 | 0 | 2.28 | 0% / 100% |
| d4 | 0.25 | 2.60 | 9% / 91% |
| d5 | 1.56 | 1.22 | 56% / 44% |
| d6 | 0.75 | 1.62 | 32% / 68% |
| Topic | goal | team | match | oven | flour | recipe |
|---|---|---|---|---|---|---|
| topic 1 (sports) | 1.23 | 1.14 | 0.77 | 0 | 0.03 | 0.12 |
| topic 2 (baking) | 0 | 0.06 | 0.09 | 1.02 | 1.01 | 1.02 |
Fold in a new document: goal ×2, oven ×1, recipe ×1
- 1Keep fixed and solve for — a 2-variable non-negative least squares problem.
- 2Normal equations: , .
- 3Solve: . Both entries are positive, so the constraint is inactive and this is the NNLS solution.
- 4Interpretation: 54% sports, 46% baking. The reconstruction spreads each topic's mass over all its words, with residual norm — NMF summarizes, it does not memorize.
- 1W, H ← small positive values
- 2repeat:
- 3 W ← W ⊙ (X Hᵀ) ⊘ (W H Hᵀ)
- 4 H ← H ⊙ (Wᵀ X) ⊘ (Wᵀ W H)
- 5until ½‖X − WH‖² stops falling
- 6new x: h = argmin_{h ≥ 0} ‖x − h H‖
Start from strictly positive W (6×2) and H (2×6). Their product is a blurry guess: loss ½‖X − WH‖² = 25.71.
Watch the colours: after a few iterations the WH cells for d1–d2 are almost pure topic-1 blue and d3–d4 almost pure topic-2 orange, while d5–d6 are visibly blended — that blend is the additive combination NMF is built on. With the sports topic splits in two (one led by goal and match, one by team), which is the first sign of choosing too large for six documents.
The algorithm, step by step
NMF(X, k) with multiplicative updates
- 1Check the input. Every entry of must be . Optionally scale features (e.g. TF-IDF for text), but never centre — centring creates negatives.
- 2Initialize () and () with strictly positive values: random uniform scaled to , or NNDSVD (
init="nndsvda"fills its zeros with the data mean, which multiplicative updates need). - 3Update W with fixed: , where a tiny guards against division by zero.
- 4Update H with fixed: .
- 5Check convergence. Stop when the relative drop in loss over the last few iterations is below a tolerance (scikit-learn default
tol=1e-4) or atmax_iter. - 6Normalize (optional): scale each row of to unit sum or norm and absorb the scale into .
- 7Transform new data: with fixed, solve per row (repeat the -update alone, or use NNLS).
Cost
- Per iteration
- Compute and in ; the small Gram matrices , in . Multiply rather than to avoid forming the dense product.
- Sparse X
- per iteration — NMF scales to millions of documents with sparse TF-IDF matrices.
- Memory
- for the factors plus itself.
- Iterations
- multiplicative updates: often hundreds; coordinate descent (HALS): typically tens (14 on the worked example, to the same loss 3.9821).
Variants and tuning
| Knob | Options | Effect |
|---|---|---|
| Rank k | 2 … a few hundred | More parts → lower error but finer, less distinct parts. On the example: loss 18.69 (k=1), 3.98 (k=2), 1.78 (k=3). |
| Loss (beta_loss) | frobenius · kullback-leibler · itakura-saito | Frobenius for intensities / general data; KL for counts (Poisson); IS for audio power spectra. KL and IS need the mu solver. |
| Solver | cd (HALS, coordinate descent) · mu | cd converges much faster for Frobenius; mu is the only option for other β-divergences. |
| Initialization | nndsvd · nndsvda · nndsvdar · random | NNDSVD is deterministic and starts near a good solution; random needs several restarts. Use nndsvda/nndsvdar with mu (no exact zeros). |
| L1 penalty (alpha_W, alpha_H) | 0 … large | Sparser parts and codes. Error ‖X−WH‖ 2.82 → 2.92 → 7.56 and zeros in H 2 → 3 → 9 of 12 for α = 0, 0.1, 0.5. |
| L2 penalty | l1_ratio < 1 | Smaller, smoother entries; stabilizes ill-conditioned problems. |
l1_ratio=1.Choosing k
- Elbow
- plot reconstruction error against k and look for where the gains flatten.
- Stability
- run several seeds per k and measure how consistent the parts are (consensus clustering, as used in genomics); stable k values are trustworthy.
- Held-out entries
- mask a random 5–10% of entries, fit on the rest (weighted NMF), and pick the k with the lowest error on the masked ones.
- Downstream
- if the parts feed a classifier or a recommender, choose k by that task's validation score; for topics, by topic coherence.
Related models
- Sparse NMF
- explicit L1 (or Hoyer sparseness) constraints on W or H.
- Semi-NMF / convex NMF
- allow (and ) to have mixed signs while keeping , or restrict parts to convex combinations of data points.
- Probabilistic view
- KL-NMF is maximum likelihood for Poisson counts; with normalized factors it is equivalent to PLSA, the precursor of LDA topic models.
- Online / mini-batch NMF
- scikit-learn's MiniBatchNMF updates H from batches, for data that does not fit in memory.
- Tensor / convolutive NMF
- non-negative CP decomposition for 3-way data; convolutive NMF for patterns that extend over time.
In code
1import numpy as np23def nmf(X, k, iters=500, W=None, H=None, seed=0, eps=1e-12):4 """Lee–Seung multiplicative updates for min ½‖X − WH‖², W, H ≥ 0."""5 rng = np.random.default_rng(seed)6 n, d = X.shape7 W = rng.uniform(0.1, 1, (n, k)) if W is None else W.astype(float).copy()8 H = rng.uniform(0.1, 1, (k, d)) if H is None else H.astype(float).copy()9 losses = [0.5 * np.sum((X - W @ H) ** 2)]10 for _ in range(iters):11 W *= (X @ H.T) / (W @ H @ H.T + eps) # gradient step with step size W / (W H Hᵀ)12 H *= (W.T @ X) / (W.T @ W @ H + eps) # same for H13 losses.append(0.5 * np.sum((X - W @ H) ** 2))14 return W, H, losses1516def fold_in(x, H, iters=2000, eps=1e-12):17 """Topic weights of a new row with H fixed: the same update applied to h alone."""18 h = np.ones(H.shape[0])19 for _ in range(iters):20 h *= (H @ x) / (H @ H.T @ h + eps)21 return h2223words = ["goal", "team", "match", "oven", "flour", "recipe"]24X = np.array([[3, 2, 2, 0, 0, 0],25 [2, 3, 1, 0, 0, 1],26 [0, 0, 0, 3, 2, 2],27 [0, 1, 0, 2, 3, 3],28 [2, 2, 1, 1, 2, 1],29 [1, 0, 2, 2, 1, 2]], dtype=float)30W0 = np.array([[.6, .4], [.8, .3], [.3, .7], [.4, .9], [.5, .5], [.7, .6]])31H0 = np.array([[.9, .7, .8, .4, .3, .5], [.3, .4, .2, .8, .9, .6]])3233W, H, losses = nmf(X, 2, W=W0, H=H0)34print("loss:", [round(float(losses[i]), 2) for i in (0, 1, 2, 3, 500)]) # 25.71 9.83 6.09 4.71 3.9835print("H =\n", H.round(2))36for t in range(2):37 print(f"topic {t + 1}:", [words[j] for j in np.argsort(-H[t])[:3]])38print("d5 topic share:", (W[4] / W[4].sum()).round(2)) # [0.56 0.44]39print("new doc h =", fold_in(np.array([2, 0, 0, 1, 0, 1.]), H).round(4)) # [0.7024 0.5891]1import numpy as np2from sklearn.decomposition import NMF34X = np.array([[3, 2, 2, 0, 0, 0],5 [2, 3, 1, 0, 0, 1],6 [0, 0, 0, 3, 2, 2],7 [0, 1, 0, 2, 3, 3],8 [2, 2, 1, 1, 2, 1],9 [1, 0, 2, 2, 1, 2]], dtype=float)10W0 = np.array([[.6, .4], [.8, .3], [.3, .7], [.4, .9], [.5, .5], [.7, .6]])11H0 = np.array([[.9, .7, .8, .4, .3, .5], [.3, .4, .2, .8, .9, .6]])1213# 1) Exactly the article's run: multiplicative updates from the same start.14mu = NMF(n_components=2, init="custom", solver="mu", max_iter=500, tol=0)15W = mu.fit_transform(X, W=W0.copy(), H=H0.copy())16print("loss =", round(0.5 * mu.reconstruction_err_ ** 2, 4)) # 3.982117print("H =\n", mu.components_.round(2))18print("new doc h =", mu.transform([[2, 0, 0, 1, 0, 1]]).round(4)) # [[0.7024 0.5891]]1920# 2) What you would use in practice: NNDSVD start + coordinate descent.21cd = NMF(n_components=2, init="nndsvda", solver="cd", max_iter=1000, random_state=0).fit(X)22print("cd: loss =", round(0.5 * cd.reconstruction_err_ ** 2, 4), "in", cd.n_iter_, "iterations")Use when
- +Your data are non-negative amounts — counts, intensities, spectra, expression levels — and you want components a person can read.
- +You need soft, overlapping memberships: a document can be 56% one topic and 44% another.
- +The matrix is large and sparse (TF-IDF, user–item); NMF works directly on sparse input.
- +You want a compact, non-negative feature set for a downstream model or for source separation.
Avoid when
- −The data have meaningful negative values or must be centred — use PCA, ICA or Factor Analysis.
- −You need a unique, reproducible answer: results depend on initialization and k, up to scaling and permutation.
- −You need the optimal low-rank reconstruction — truncated SVD is always at least as accurate.
- −The goal is a 2-D picture of neighbourhoods — use t-SNE or UMAP.
Where it's used
Topic modelling
Factor a TF-IDF document–term matrix: rows of H are topics (ranked word lists), rows of W are document–topic mixtures. A fast, deterministic alternative to LDA.
Audio source separation
Factor a magnitude spectrogram (frequency × time): H holds spectral templates of notes or instruments, W their activations over time; mask and invert to separate sources.
Genomics
Gene-expression and mutation-count matrices factor into metagenes and mutational signatures (COSMIC signatures were extracted with NMF).
Recommenders and images
Non-negative user–item factors give interpretable taste profiles; image patches and faces decompose into localized parts; hyperspectral pixels unmix into material spectra.
Check yourself
In a multiplicative update, an entry has , and . What is its new value?
Check yourself
You initialize one entry of H to exactly 0. After 1,000 multiplicative updates it is…
Check yourself
minimizes the NMF loss. Which pair has exactly the same loss?
Check yourself
On the worked example, rank-2 NMF reaches loss 3.98 while the truncated SVD reaches 3.91. Why can NMF never beat the SVD at the same rank?
Remember
- ✓NMF factors a non-negative matrix as with : rows of are parts, rows of are how much of each part a sample contains.
- ✓No subtraction means no cancellation, so parts come out additive, localized and often sparse — readable topics, face parts, spectral templates.
- ✓Lee–Seung updates (and the mirror for ) are gradient steps with entry-wise step sizes; they keep entries non-negative and never increase the loss.
- ✓The problem is non-convex and the factors are unique only up to scaling and permutation: initialize with NNDSVD or several seeds, and normalize before comparing.
- ✓Choose the loss to match the data (Frobenius, KL for counts, Itakura–Saito for audio), choose k by error elbow, stability or a downstream task, and never centre the data.