10 · Truncated SVD
The original Netflix-Prize idea: mean-center the matrix, take its SVD, keep only the top-k singular triplets, and reconstruct to fill in the blanks. Small k denoises.
If R ≈ P Qᵀ is low-rank, the Singular Value Decomposition R = U Σ Vᵀ finds the BEST rank-k approximation for free: keep the top-k singular triplets and the reconstruction predicts the missing entries. Small k discards noise; large k overfits.
Without this:
SVD is the bridge from 'factors exist' to 'here's a concrete way to get them'. It also reveals the central tension of every MF model: k is a knob trading fidelity to the data against generalization.
Lesson 9 said good P and Q exist. Truncated SVD is the classic recipe to find them — the move that kicked off the Netflix-Prize era of recommenders.
The Singular Value Decomposition factors any matrix as R = U Σ Vᵀ, where U and V are orthonormal and Σ is a diagonal of non-negative singular values sorted largest-first. Each singular value is the strength of one latent dimension. The Eckart–Young theorem guarantees that keeping only the top-k triplets gives the best possible rank-k approximation of R (in squared error). So:
- Keep
U[:, :k],Σ[:k],V[:, :k]. - Reconstruct
R_hat = U_k Σ_k V_kᵀ. - The reconstructed values at the empty cells are your predictions.
Two practical wrinkles. First, plain SVD needs a fully filled matrix, but R is mostly missing — the classic fix is to mean-impute: fill blanks with each item's (or user's, or global) mean before decomposing. Second, mean-center first (subtract row/column/global means), so the factors model deviations from the average, then add the mean back at the end.
The magic knob is k:
- Too large → you reconstruct the imputed matrix almost perfectly, including its noise → overfit.
- Too small → you keep only the strongest patterns → you denoise, and predictions for held-out cells often improve.
Below we hide a few cells, mean-impute, run np.linalg.svd, truncate to k, and compare predicted vs actual on the held-out cells — and watch a smaller k denoise.
Python (in browser)
Mean-impute → SVD → truncate to k → reconstruct. The held-out RMSE is best at the true rank; too-large k refits noise (overfits the imputation).
Python runs entirely in your browser via Pyodide (~6 MB on first Run, cached after).
How it looks with scikit-learn's TruncatedSVD on a sparse matrix (read-along; not executed here).
After running SVD on a mean-imputed rating matrix, why does keeping a SMALL number of factors k often improve predictions on held-out cells?
- SVD R = U Σ Vᵀ + Eckart–Young gives the best rank-k approximation; the reconstruction at empty cells is your prediction.
- Plain SVD needs a full matrix → mean-impute and mean-center first, then add the mean back after reconstructing.
- k trades fit vs noise: small k denoises and generalizes; large k refits the imputed values and overfits.
Truncated SVD is the historical core of the Netflix Prize, and the same low-rank trick powers LSA in NLP and dimensionality reduction across ML.
If you remove it: Without the low-rank/SVD view, you'd have no principled way to compress a sparse rating matrix into reusable user/item factors.