Matrix Factorization

Why Factor a Matrix?

Consider a matrix V of size m×n — perhaps ratings that m users gave to n movies, or word counts in m documents across a vocabulary of n words. Most entries may be missing or zero. The raw matrix is hard to interpret: it has mn numbers with no obvious structure.

Matrix factorization decomposes V into a product of two (or more) smaller matrices whose columns and rows correspond to latent factors — hidden concepts that explain the observed data. The idea appears across machine learning under many names: NMF for parts-based representations, SVD for recommender systems, LSA for text, and implicit factorization in word embeddings. All share the same core linear algebra.

Non-Negative Matrix Factorization (NMF)

Given a non-negative matrix V ∈ ℝ₊^{m×n}, NMF seeks non-negative factor matrices W ∈ ℝ₊^{m×k} and H ∈ ℝ₊^{k×n} such that V ≈ WH, where k ≪ min(m,n) is the number of latent components:

NMF Objective

\min_{W \geq 0,\, H \geq 0} \|V - WH\|_F^2

The Frobenius norm ‖·‖_F measures elementwise reconstruction error. The non-negativity constraints (W ≥ 0, H ≥ 0) force an additive, parts-based decomposition — each column of W is a "part" and each row of H tells how strongly each part appears in each data point. The columns of W form an over-complete dictionary; each data point is a non-negative combination of dictionary atoms.

Because of non-negativity, NMF automatically produces interpretable factors. For an image dataset, columns of W resemble facial features — eyes, noses, mouths — and H encodes how strongly each feature appears in each image. For text, columns of W are topic word distributions and rows of H are document-topic weights.

NMF is solved by alternating multiplicative updates derived from the gradient of the Frobenius objective. Starting from random non-negative W and H:

Multiplicative Update Rules

H \leftarrow H \odot \frac{W^T V}{W^T W H}, \quad W \leftarrow W \odot \frac{V H^T}{W H H^T}

Each update is elementwise: multiply by the ratio of the positive gradient to the negative gradient. This guarantees W and H remain non-negative throughout. The updates converge to a local minimum — NMF is non-convex in (W,H) jointly, though convex in each factor separately.

Parts vs. Holistic Representations

PCA (via SVD) allows negative coefficients, so its components can cancel each other — a holistic representation. NMF's non-negativity means components only add, never subtract, producing parts-based representations that match how humans describe objects. This makes NMF factors far more interpretable in domains like images, text, and audio spectrograms.

Collaborative Filtering via SVD

A recommender system must predict whether user i will like item j, given only a sparse matrix of observed ratings R ∈ ℝ^{m×n}. The key insight from collaborative filtering is that ratings are low-rank: a small number of latent factors (genres, styles, themes) explain most of the variance across millions of ratings.

SVD factorizes R = UΣVᵀ where U ∈ ℝ^{m×r} contains user latent vectors, Σ is a diagonal matrix of singular values, and V ∈ ℝ^{n×r} contains item latent vectors. In practice R has many missing entries so we cannot compute the exact SVD. Instead we minimize a regularized reconstruction loss only over observed ratings:

Matrix Factorization for Recommenders

\min_{\{p_i\},\{q_j\}} \sum_{(i,j)\in\Omega} (r_{ij} - p_i^T q_j)^2 + \lambda(\|p_i\|^2 + \|q_j\|^2)

Here Ω is the set of observed (i,j) pairs, pᵢ ∈ ℝᵏ is the latent vector for user i, qⱼ ∈ ℝᵏ is the latent vector for item j, and λ controls regularization strength. The predicted rating is r̂ᵢⱼ = pᵢᵀqⱼ. Learned via stochastic gradient descent: for each observed rating update pᵢ and qⱼ to reduce the residual (rᵢⱼ − pᵢᵀqⱼ).

After training, the k-dimensional vectors pᵢ and qⱼ encode user preferences and item characteristics in a shared latent space. Items with similar qⱼ vectors are similar (even if they share no explicit features), and users with similar pᵢ vectors have similar taste. The dot product pᵢᵀqⱼ measures alignment between user preference and item character — a large value predicts a high rating.

Low-Rank Approximation and the Eckart–Young Theorem

The Eckart–Young theorem establishes that the best rank-k approximation to a matrix A (in both spectral and Frobenius norms) is obtained by truncating its SVD: keep only the k largest singular values and their corresponding singular vectors. If A = UΣVᵀ, then:

Truncated SVD (Best Rank-k Approximation)

A_k = U_k \Sigma_k V_k^T = \sum_{i=1}^{k} \sigma_i \mathbf{u}_i \mathbf{v}_i^T

Aₖ = UₖΣₖVₖᵀ, where Uₖ and Vₖ contain only the first k columns. The approximation error is ‖A − Aₖ‖_F² = σₖ₊₁² + σₖ₊₂² + … + σᵣ². The fraction of variance explained by the top k components is (σ₁² + … + σₖ²) / (σ₁² + … + σᵣ²). Choosing k is the model-selection problem: a scree plot of σᵢ² helps identify the "elbow" where additional components add diminishing variance.

Latent Semantic Analysis (LSA)

LSA applies truncated SVD to a term-document matrix. Build a matrix A ∈ ℝ^{t×d} where Aᵢⱼ is the (TF-IDF-weighted) count of term i in document j. SVD decomposes A = UΣVᵀ; truncating to rank k gives a compressed representation Aₖ = UₖΣₖVₖᵀ.

The rows of UₖΣₖ are "concept vectors" for each term, and the columns of ΣₖVₖᵀ are concept vectors for each document — both living in the same k-dimensional latent semantic space. Document similarity is measured by cosine similarity between their concept vectors, which captures synonymy (words that mean the same thing cluster together) and polysemy (words with multiple meanings are positioned near their most common sense).

Why SVD Denoises Text

The raw term-document matrix is noisy: synonyms appear as different dimensions, irrelevant co-occurrences inflate similarity. Truncating to rank k removes the noise dimensions (those with small singular values) and retains the dominant semantic directions. Documents that share topics but not exact vocabulary end up close in the low-rank space.

Word Embeddings and Matrix Factorization

Word2Vec (skip-gram with negative sampling) and GloVe — the dominant word embedding methods — have deep connections to matrix factorization. GloVe explicitly factorizes the log co-occurrence matrix: given a co-occurrence count matrix X where Xᵢⱼ counts how often word i appears near word j in a large corpus, GloVe seeks word vectors wᵢ and context vectors w̃ⱼ such that:

GloVe Objective

\min_{w_i, \tilde{w}_j, b_i, \tilde{b}_j} \sum_{i,j} f(X_{ij})\,(w_i^T \tilde{w}_j + b_i + \tilde{b}_j - \log X_{ij})^2

f(Xᵢⱼ) is a weighting function that downweights very frequent co-occurrences (so common pairs like "the cat" don't dominate). The biases bᵢ and b̃ⱼ absorb word-specific frequency effects. The result: wᵢᵀw̃ⱼ ≈ log Xᵢⱼ. This is exactly weighted low-rank approximation of the log co-occurrence matrix. The learned vectors capture semantic analogies: king − man + woman ≈ queen in embedding space.

Levy and Goldberg (2014) proved that Word2Vec skip-gram with negative sampling implicitly factorizes the shifted pointwise mutual information (PMI) matrix — a weighted version of the log co-occurrence matrix. The connection shows that neural word embeddings are not fundamentally different from classical matrix factorization; they differ mainly in optimization and weighting strategies.

Geometric Properties of Embeddings

The geometric structure of word embedding spaces follows directly from the matrix factorization objective. If wᵢᵀw̃ⱼ ≈ log P(j|i) (pointwise mutual information), then:

Synonymy: words that appear in similar contexts have similar vectors — their dot products with all context words are similar
Analogy: the difference vector wking − wman captures the "royalty" direction; adding it to wwoman moves toward wqueen because this direction shifts PMI with royalty-related words
Compositionality: phrase meaning is roughly the sum of word vectors — an additive approximation to the product of PMIs

Choosing the Rank: Model Selection

All matrix factorization methods require choosing k, the number of latent factors. Too small: the model underfits — the low-rank approximation misses important structure. Too large: the model overfits — it memorizes noise, and the factors lose interpretability.

Practical strategies:

Scree plot (SVD/PCA): plot σᵢ² vs. i; look for an "elbow" where the curve flattens — factors below the elbow explain mainly noise
Explained variance: choose k such that the top k singular values account for 90–95% of the total variance Σᵢ σᵢ²
Cross-validation (recommenders): hold out a random subset of observed ratings; choose k minimizing validation RMSE
Reconstruction error vs. interpretability (NMF): smaller k gives more interpretable but less accurate factors; k is often chosen by domain knowledge

Key Takeaways

Matrix factorization decomposes a data matrix V ≈ WH into latent factor matrices, revealing hidden structure in high-dimensional data. NMF enforces non-negativity to produce interpretable parts-based decompositions — each column of W is a part, each row of H is a mixture weight. Collaborative filtering via SVD represents users and items as latent vectors in a shared space; predicted ratings are dot products pᵢᵀqⱼ, learned by minimizing reconstruction error on observed ratings. The Eckart–Young theorem guarantees truncated SVD is the optimal low-rank approximation in both spectral and Frobenius norms. LSA applies this to text, compressing a term-document matrix to discover latent semantic topics. Word embeddings (GloVe, Word2Vec) implicitly factorize log co-occurrence matrices, producing vector spaces where semantic relationships correspond to geometric directions.