# SVD

> Factor the data matrix as UΣVᵀ; keeping the top k singular vectors gives the best rank-k approximation of the data.

Source: https://www.mlfoundry.in/learn/svd  
Section: ML Algorithms › Unsupervised · Dimensionality Reduction  
Level: core · 17 min read · updated 2026-10-07

**The singular value decomposition (SVD):** writes **any** real $m\times n$ matrix as $A=U\Sigma V^\top$: an orthonormal set of input directions $V$, a list of non-negative stretch factors $\sigma_1\ge\sigma_2\ge\dots\ge 0$ on the diagonal of $\Sigma$, and an orthonormal set of output directions $U$. Equivalently, $A$ is a sum of rank-1 layers $\sigma_i u_i v_i^\top$ sorted from most to least important — and cutting the sum after $k$ terms gives the best possible rank-$k$ approximation of $A$.

- **Task:** Matrix factorization: dimensionality reduction, compression, denoising, latent factors, solving least squares
- **Input → output:** a matrix $A\in\mathbb{R}^{m\times n}$ → $U\in\mathbb{R}^{m\times r}$, $\sigma_1..\sigma_r$, $V\in\mathbb{R}^{n\times r}$ with $r=\min(m,n)$ (thin SVD)
- **Learns:** row-space directions $v_i$ (e.g. "taste profiles" over movies), column-space directions $u_i$ (each user's coordinates), and their strengths $\sigma_i$
- **Training cost:** exact: $O(mn\min(m,n))$; top-$k$ only (randomized / Lanczos): about $O(mnk)$
- **Prediction cost:** projecting a new row $x$: $O(nk)$ for $z=V_k^\top x$; reconstructing it: another $O(nk)$
- **Hyperparameters:** the rank $k$ kept; the solver (full LAPACK, randomized, ARPACK); whether to centre / scale columns first; the cutoff below which a $\sigma_i$ is treated as 0
- **Assumes:** nothing statistical — it is exact linear algebra. Using a truncated SVD as a *model* assumes the signal is low-rank and the noise is spread over all directions

## The problem

Real data matrices are big and redundant. A users × movies ratings table, a documents × words count table, a grayscale image, a sensor array over time — each has thousands of columns, but the columns are strongly correlated: people who love *Alien* tend to love *Star Wars*. We want a factorization that (1) works for **any** rectangular matrix, (2) finds the few directions that carry most of the structure, (3) tells us exactly how much we lose by keeping only those, and (4) is numerically stable.

The eigendecomposition $A=Q\Lambda Q^{-1}$ fails all four: it only exists for square matrices, may need complex numbers, its eigenvectors need not be orthogonal (so "keeping the top ones" has no clean error guarantee), and it can fail to exist at all (defective matrices). Gaussian elimination or QR tells you nothing about which directions *matter*. The SVD fixes all of this: it exists for every matrix, it is real, both bases are orthonormal, and its truncation is provably optimal.

## The idea

**Geometry.** Any linear map, however messy its matrix looks, does only three things: it **rotates** the input (by $V^\top$), **stretches** along the coordinate axes (by $\Sigma$, possibly squashing some axes to zero), and **rotates** again into the output space (by $U$). Feed in the unit circle and you get an ellipse; the ellipse's semi-axes are $\sigma_1u_1$ and $\sigma_2u_2$, and the input directions that land on them are $v_1$ and $v_2$.

**Layers.** Read the same factorization as a sum: $A=\sigma_1u_1v_1^\top+\sigma_2u_2v_2^\top+\dots$. Each term is a rank-1 matrix — a single pattern $v_i$ across the columns, multiplied by a single loading $u_i$ down the rows. For ratings, $v_1$ might be "overall movie popularity" and $v_2$ "romance minus sci-fi"; $u_i$ says how strongly each user expresses that pattern. The layers are sorted by $\sigma_i$, so the first few carry the bulk of the matrix and the tail is mostly noise.

**Vocabulary**

- **Singular value σᵢ:** the $i$-th stretch factor, $\sigma_i\ge 0$, sorted descending. $\sigma_1$ is the largest gain $\|Av\|$ over unit vectors $v$
- **Right singular vector vᵢ:** a unit vector in the **input** space $\mathbb{R}^n$ (a pattern over the columns); the $v_i$ are orthonormal and are the eigenvectors of $A^\top A$
- **Left singular vector uᵢ:** a unit vector in the **output** space $\mathbb{R}^m$ (a loading over the rows); $u_i=Av_i/\sigma_i$, the eigenvectors of $AA^\top$
- **Rank r:** the number of non-zero singular values — the true number of independent directions in $A$
- **Full / thin / truncated SVD:** full: $U$ is $m\times m$, $V$ is $n\times n$; thin: only the $\min(m,n)$ columns that meet $\Sigma$; truncated: only the top $k$ (see **Truncated SVD**)
- **Frobenius norm:** $\|A\|_F=\sqrt{\sum_{ij}a_{ij}^2}=\sqrt{\sum_i\sigma_i^2}$ — total "energy" of the matrix
- **Spectral norm:** $\|A\|_2=\sigma_1$ — the most any unit vector can be stretched
- **Energy kept:** $\sum_{i\le k}\sigma_i^2\,/\sum_i\sigma_i^2$ — the fraction of $\|A\|_F^2$ that a rank-$k$ approximation retains
- **Condition number:** $\kappa=\sigma_1/\sigma_r$ — how much relative error in $b$ can be amplified when solving $Ax=b$
- **Pseudo-inverse A⁺:** $V\Sigma^+U^\top$, where $\Sigma^+$ inverts the non-zero $\sigma_i$ — the least-squares, minimum-norm "inverse" of any matrix

## The math

$$
A=U\Sigma V^\top=\sum_{i=1}^{r}\sigma_i\,u_i v_i^\top,\qquad U^\top U=I,\; V^\top V=I
$$

- $A$: the data matrix, $m$ rows (samples) × $n$ columns (features)
- $U=[u_1\dots u_r]$: $m\times r$, orthonormal columns: left singular vectors
- $\Sigma$: $r\times r$ diagonal, entries $\sigma_1\ge\dots\ge\sigma_r>0$
- $V=[v_1\dots v_r]$: $n\times r$, orthonormal columns: right singular vectors
- $r$: rank of $A$ (at most $\min(m,n)$)

**Where $V$ and $\Sigma$ come from.** Suppose the factorization exists. Then $A^\top A=V\Sigma U^\top U\Sigma V^\top=V\Sigma^2V^\top$. That is an eigendecomposition of the symmetric, positive-semidefinite matrix $A^\top A$: its eigenvectors are the $v_i$ and its eigenvalues are $\sigma_i^2$. Run the argument backwards to *construct* the SVD: the spectral theorem gives $A^\top A$ orthonormal eigenvectors $v_i$ with eigenvalues $\lambda_i\ge 0$ (because $v^\top A^\top Av=\|Av\|^2\ge0$). Set $\sigma_i=\sqrt{\lambda_i}$.

$$
u_i=\frac{Av_i}{\sigma_i}\quad\Rightarrow\quad u_i^\top u_j=\frac{v_i^\top A^\top A\,v_j}{\sigma_i\sigma_j}=\frac{\sigma_j^2\,v_i^\top v_j}{\sigma_i\sigma_j}=\delta_{ij}
$$

- $\delta_{ij}$: 1 if $i=j$, else 0 — so the $u_i$ come out orthonormal automatically
- $Av_i=\sigma_iu_i$: the defining pair of equations; also $A^\top u_i=\sigma_iv_i$

Stacking $Av_i=\sigma_iu_i$ for all $i$ gives $AV=U\Sigma$, and multiplying by $V^\top$ on the right gives $A=U\Sigma V^\top$. **Every** matrix therefore has an SVD. The singular values are unique; each pair $(u_i,v_i)$ is unique up to a joint sign flip (or rotation within a block if two $\sigma$ tie).

$$
\sigma_1=\max_{\|v\|=1}\|Av\|,\qquad \sigma_k=\max_{\|v\|=1,\;v\perp v_1..v_{k-1}}\|Av\|
$$

- $\|Av\|$: how long the unit vector $v$ becomes after applying $A$
- $v_1$: the maximizer: the input direction $A$ stretches most

This **variational** view is what power iteration exploits: maximizing $\|Av\|^2=v^\top A^\top Av$ is a Rayleigh quotient, so repeatedly applying $A^\top A$ to a vector and normalizing converges to $v_1$, at a rate set by $(\sigma_2/\sigma_1)^2$.

**A 2×2 by hand.** $A=\begin{bmatrix}3&0\\4&5\end{bmatrix}$ gives $A^\top A=\begin{bmatrix}25&20\\20&25\end{bmatrix}$, with eigenvalues $45$ and $5$ and eigenvectors $v_1=(1,1)/\sqrt2$, $v_2=(-1,1)/\sqrt2$. So $\sigma_1=\sqrt{45}=6.708$, $\sigma_2=\sqrt5=2.236$, $u_1=Av_1/\sigma_1=(1,3)/\sqrt{10}=(0.316,0.949)$ and $u_2=Av_2/\sigma_2=(-3,1)/\sqrt{10}$. Checks: $\sigma_1\sigma_2=15=|\det A|$, and $\kappa=\sigma_1/\sigma_2=3$. This is the default matrix in the figure below.

## Why truncation is optimal (Eckart–Young)

$$
A_k=\sum_{i=1}^{k}\sigma_iu_iv_i^\top=U_k\Sigma_kV_k^\top,\qquad \min_{\operatorname{rank}B\le k}\|A-B\|_F^2=\|A-A_k\|_F^2=\sum_{i>k}\sigma_i^2
$$

- $A_k$: the truncated SVD: keep the top $k$ layers
- $U_k,\Sigma_k,V_k$: the first $k$ columns of $U$, $V$ and the top-left $k\times k$ block of $\Sigma$
- $B$: any matrix of rank at most $k$ — no other one does better

**Why the error is the tail sum.** Orthogonal matrices preserve the Frobenius norm, so $\|A-A_k\|_F=\|U^\top(A-A_k)V\|_F=\|\operatorname{diag}(0,..,0,\sigma_{k+1},..,\sigma_r)\|_F$. The optimality (no rank-$k$ $B$ beats it) follows from Weyl's inequality $\sigma_{i+k}(A)\le\sigma_i(A-B)+\sigma_{k+1}(B)$ with $\sigma_{k+1}(B)=0$: the residual $A-B$ must have singular values at least $\sigma_{k+1},\sigma_{k+2},\dots$ of $A$. The same theorem holds in the spectral norm: $\min_{\operatorname{rank}B\le k}\|A-B\|_2=\sigma_{k+1}$.

**The hyperparameter $k$, mathematically.** Raising $k$ by one adds one layer, lowers the squared error by exactly $\sigma_{k+1}^2$, and costs $m+n+1$ more stored numbers. Since the $\sigma_i$ are sorted, the returns diminish monotonically — which is why you look for the point where the spectrum flattens into a noise floor.

## Least squares and the pseudo-inverse

$$
x^\star=A^+b=V\Sigma^+U^\top b=\sum_{i=1}^{r}\frac{u_i^\top b}{\sigma_i}\,v_i
$$

- $x^\star$: the minimum-norm minimizer of $\|Ax-b\|^2$
- $u_i^\top b$: the component of the target along output direction $u_i$
- $1/\sigma_i$: the gain applied to it — huge when σᵢ is tiny

This explains ill-conditioning: noise in $b$ along a direction with small $\sigma_i$ gets divided by $\sigma_i$ and blows up. Two cures fall straight out of the formula: **truncate** (drop terms with $\sigma_i$ below a cutoff — "truncated SVD regression"), or **damp** them — ridge regression multiplies each term by the *filter factor* $\sigma_i^2/(\sigma_i^2+\lambda)$, which is about 1 for big $\sigma_i$ and about 0 for small ones. Least-squares solvers such as NumPy's lstsq use exactly this SVD route.

> **PCA is the SVD of centred data:** If $X_c$ is the data with column means subtracted, its covariance is $X_c^\top X_c/(n-1)=V\frac{\Sigma^2}{n-1}V^\top$. So the principal directions are the right singular vectors, the explained variances are $\sigma_i^2/(n-1)$, and the scores are $U\Sigma$. Production PCA never forms the covariance — it runs an SVD on $X_c$. The statistics side (variance maximization, scree plots, whitening) is covered in **PCA**; this article is about the factorization itself, which works on *uncentred* matrices too.

## Worked example: a tiny ratings matrix

Six users rate four movies from 1 to 5: two sci-fi films (*Alien*, *Star Wars*) and two romances (*Notting Hill*, *Titanic*). Users 1–3 prefer sci-fi, users 4–5 romance, user 6 rates everything 3. We factor the raw (uncentred) matrix, as a recommender would.

The 6×4 ratings matrix A. Highlighted: user 6, who has no preference between genres.

| User | Alien | Star Wars | Notting Hill | Titanic |
| --- | --- | --- | --- | --- |
| u1 | 5 | 5 | 1 | 1 |
| u2 | 4 | 5 | 1 | 2 |
| u3 | 5 | 4 | 2 | 1 |
| u4 | 1 | 1 | 5 | 4 |
| u5 | 2 | 1 | 4 | 5 |
| u6 | 3 | 3 | 3 | 3 |

**Factoring A by hand**

1. **Gram matrix.** $A^\top A$ holds the dot products between movie columns: $\begin{bmatrix}80&77&41&41\\77&77&36&37\\41&36&56&54\\41&37&54&56\end{bmatrix}$. Its trace $80+77+56+56=269$ equals $\|A\|_F^2$, the sum of all squared ratings.
2. **Eigenvalues of $A^\top A$** (the characteristic polynomial of a 4×4 is solved numerically): $213.59,\;52.13,\;2.25,\;1.03$ — they sum to 269. Square roots give the **singular values** $\sigma=(14.615,\;7.220,\;1.499,\;1.017)$.
3. **Right singular vectors** (eigenvectors of $A^\top A$): $v_1=(0.579,0.553,0.423,0.425)$ — all positive, "how much you like movies at all". $v_2=(-0.386,-0.462,0.569,0.560)$ — negative on sci-fi, positive on romance: the **genre axis**.
4. **Left singular vectors** $u_i=Av_i/\sigma_i$. For $i=1$: $Av_1=(6.506,6.352,6.376,4.945,5.527,5.938)$, divided by 14.615 gives $u_1=(0.445,0.435,0.436,0.338,0.378,0.406)$. Likewise $u_2=(-0.431,-0.300,-0.288,0.587,0.532,0.117)$: sci-fi fans negative, romance fans positive, user 6 near 0.
5. **Rank-2 reconstruction of one entry.** $\hat a_{11}=\sigma_1u_{11}v_{11}+\sigma_2u_{12}v_{12}=14.615(0.445)(0.579)+7.220(-0.431)(-0.386)=3.766+1.201=4.967$, against the true 5.
6. **Error by Eckart–Young.** $\|A-A_2\|_F^2=\sigma_3^2+\sigma_4^2=2.247+1.034=3.281$ (RMS error per cell $\sqrt{3.281/24}=0.37$). The two kept layers hold $(213.59+52.13)/269=98.8\%$ of the energy.

Every rank k for the ratings matrix. The error column is exactly the sum of the dropped σᵢ²; the spectral error is the first dropped σ.

| k | σₖ | σₖ² | Energy kept | ‖A − Aₖ‖²_F | ‖A − Aₖ‖₂ | Numbers stored k(m+n+1) |
| --- | --- | --- | --- | --- | --- | --- |
| 1 | 14.615 | 213.59 | 79.4% | 55.408 | 7.220 | 11 |
| **2** | **7.220** | **52.13** | **98.8%** | **3.281** | **1.499** | **22** |
| 3 | 1.499 | 2.25 | 99.6% | 1.034 | 1.017 | 33 |
| 4 | 1.017 | 1.03 | 100% | 0 | 0 | 44 (vs 24 raw) |

**Predicting for a new user.** A newcomer rates only *Alien* = 5 and *Notting Hill* = 1. Find the coordinates $z$ in the rank-2 taste space that fit those two ratings: solve $\begin{bmatrix}0.579&-0.386\\0.423&0.569\end{bmatrix}z=\begin{bmatrix}5\\1\end{bmatrix}$, giving $z=(6.561,-3.113)$. The full predicted row is $z^\top V_2^\top=(5.00,\;\mathbf{5.06},\;1.00,\;\mathbf{1.05})$: recommend *Star Wars* (5.06), skip *Titanic* (1.05). With only $k=1$ the same fit predicts $(3.74,3.57,2.73,2.75)$ — popularity alone cannot see the genre, which is exactly what layer 2 adds.

> Figure: Two tabs. Rotate · stretch · rotate: A = [3 0; 4 5] maps the unit circle to an ellipse; press play to watch Vᵀ turn v₁ = (0.707, 0.707) onto the x-axis, Σ stretch by σ₁ = 6.708 and σ₂ = 2.236, then U turn the axes onto u₁ = (0.316, 0.949). Drag the □ handles (the columns of A) to change the matrix; the coloured dots show where individual inputs travel. Best rank-k: the ratings matrix from the table, its rank-k reconstruction and the residual; at k = 2 the kept layers hold 98.8% of the energy and ‖A − A₂‖²_F = 3.281 = σ₃² + σ₄².

> **Missing ratings are not zeros:** A plain SVD needs every entry. Filling unknown ratings with 0 tells the factorization "this user hated this movie" and drags every prediction down. Real recommenders either fit only the observed entries (alternating least squares, "Funk SVD" via SGD on $\sum_{\text{observed}}(a_{ij}-p_i^\top q_j)^2+\lambda(\|p_i\|^2+\|q_j\|^2)$) or impute and iterate (soft-impute). The fold-in above did the right thing: it fitted only the two ratings the newcomer gave.

## The algorithm, step by step

The textbook construction (eigen-decompose $A^\top A$) is how to *understand* the SVD, not how to *compute* it. Libraries use the Golub–Kahan–Reinsch family; for a few top components on big matrices they use iterative or randomized methods.

**Exact SVD (LAPACK gesdd / gesvd)**

1. **Bidiagonalize.** Apply Householder reflections alternately from the left and right, $A=Q_L\,B\,Q_R^\top$, with $B$ upper-bidiagonal. Orthogonal transforms leave the singular values unchanged. Cost $O(mn^2)$ for $m\ge n$.
2. **Diagonalize $B$.** Run implicit-shift QR sweeps (gesvd) or divide-and-conquer (gesdd, NumPy's default) on the bidiagonal matrix until off-diagonals vanish: $B=W\Sigma Z^\top$.
3. **Assemble.** $U=Q_LW$, $V=Q_RZ$. Sort by $\sigma$ and fix signs if you want a canonical form.
4. **Truncate** to the top $k$ if you only need $A_k$.

**Top-k SVD by power iteration with deflation (what the from-scratch code does)**

1. Start with a random unit vector $v\in\mathbb{R}^n$.
2. Repeat $v\leftarrow A^\top(Av)$, $v\leftarrow v/\|v\|$ until it stops changing — never form $A^\top A$ explicitly.
3. Set $\sigma=\|Av\|$ and $u=Av/\sigma$.
4. **Deflate**: $A\leftarrow A-\sigma uv^\top$ removes this layer, so the next run converges to the next singular triple.
5. Repeat $k$ times. Each run costs $O(mn)$ per iteration; convergence slows when $\sigma_{i+1}/\sigma_i$ is close to 1.

**Randomized SVD (Halko–Martinsson–Tropp; used by scikit-learn)**

1. Draw a Gaussian test matrix $\Omega$ of size $n\times(k+p)$, with a small oversampling $p$ (scikit-learn's default is 10).
2. Sample the range: $Y=(AA^\top)^qA\Omega$, using $q$ power iterations (re-orthonormalized each time) to sharpen a slowly decaying spectrum.
3. Orthonormalize: $Q=\operatorname{qr}(Y)$, an $m\times(k+p)$ basis that captures the top of $A$'s range.
4. Project to a small matrix $B=Q^\top A$, $(k+p)\times n$, and take its exact SVD $B=\tilde U\Sigma V^\top$.
5. Lift back: $U=Q\tilde U$; keep the first $k$ columns. Cost about $O(mnk)$ plus a few passes over $A$.

**Complexity**

- **Exact thin SVD:** $O(mn\min(m,n))$ time, $O(mn)$ memory — fine to about $10^4\times10^4$ dense
- **Top-k (Lanczos / ARPACK, randomized):** about $O(mnk)$ dense, or $O(\text{nnz}\cdot k)$ for a sparse matrix with nnz non-zeros
- **Projecting a new row:** $O(nk)$: $z=V_k^\top x$ (or $\Sigma_k^{-1}V_k^\top x$ for $u$-coordinates)
- **Storage of Aₖ:** $k(m+n+1)$ numbers instead of $mn$

> **Don't compute the SVD through AᵀA:** Forming $A^\top A$ squares the condition number: for the ratings matrix $\kappa(A)=14.37$ but $\kappa(A^\top A)=206.5$. In floating point, any singular value below about $\sqrt{\varepsilon}\,\sigma_1$ ($\sqrt{\varepsilon}=1.5\times10^{-8}$ in double precision) is wiped out by rounding. The eigen route is fine for intuition and tiny examples like the 2×2 above; real code calls a proper SVD routine.

## Variants and practical tuning

Which SVD to call. The decomposition is the same; what differs is how much of it you compute and on what matrix. Truncated and iterative solvers are covered in depth in Truncated SVD.

| Variant | Computes | Use when | Call |
| --- | --- | --- | --- |
| Full SVD | U (m×m), Σ, V (n×n) | you need null-space bases | np.linalg.svd(A) |
| Thin (economy) SVD | U (m×r), Σ, V (n×r) | the default for data | svd(A, full_matrices=False) |
| Truncated, iterative | top k only | big / sparse, k ≪ min(m,n) | scipy.sparse.linalg.svds |
| Randomized | top k, approximately | big dense matrices | sklearn randomized_svd |
| Centred SVD | SVD of centred A | variance directions (**PCA**) | sklearn PCA |
| Incremental / streaming | running top k | data larger than memory | sklearn IncrementalPCA |

**Choosing k and preparing A**

- **Energy threshold:** smallest $k$ whose cumulative $\sum_{i\le k}\sigma_i^2/\sum\sigma_i^2$ passes a target (90%, 95%…). For the ratings, $k=2$ already keeps 98.8%
- **Spectrum gap / elbow:** plot $\sigma_i$ on a log scale and cut where it drops into a flat noise floor (here 7.22 → 1.50)
- **Optimal hard threshold:** for a matrix of signal plus i.i.d. noise, Gavish and Donoho derive a cutoff proportional to the median singular value — a principled default when no labels exist
- **Downstream validation:** if the factors feed a model (recommender, classifier), choose $k$ by held-out error, not by energy
- **Centring and scaling:** a column with large units dominates $\sigma_1$. Uncentred, $v_1$ often just captures the mean (here: "likes movies"); centre if you want contrasts, standardize if units differ
- **Rank cutoff:** for pseudo-inverses treat $\sigma_i<\text{rcond}\cdot\sigma_1$ as 0 (NumPy's pinv default is a few multiples of machine precision); raise it to regularize

> **Signs are arbitrary:** $(u_i,v_i)$ and $(-u_i,-v_i)$ give the same layer $\sigma_iu_iv_i^\top$, so two libraries — or two runs of a randomized solver — can return opposite signs. Fix a convention (e.g. make the largest-magnitude entry of each $v_i$ positive, as this article does) before comparing or plotting factors.

## In code

```python
import numpy as np

def svd_power(A, k, iters=500, seed=0):
    """Top-k SVD by power iteration on A^T A, with deflation."""
    A = A.astype(float).copy()
    rng = np.random.default_rng(seed)
    U, S, V = [], [], []
    for _ in range(k):
        v = rng.normal(size=A.shape[1])
        for _ in range(iters):
            v = A.T @ (A @ v)              # one step of power iteration on A^T A
            v /= np.linalg.norm(v)
        Av = A @ v
        sigma = np.linalg.norm(Av)         # sigma = ||A v||
        u = Av / sigma                     # u = A v / sigma
        if v[np.argmax(abs(v))] < 0:       # fix the sign ambiguity
            u, v = -u, -v
        U.append(u); S.append(sigma); V.append(v)
        A -= sigma * np.outer(u, v)        # deflate: remove this rank-1 layer
    return np.array(U).T, np.array(S), np.array(V)

# users x movies: Alien, Star Wars, Notting Hill, Titanic
A = np.array([[5, 5, 1, 1],
              [4, 5, 1, 2],
              [5, 4, 2, 1],
              [1, 1, 5, 4],
              [2, 1, 4, 5],
              [3, 3, 3, 3]], float)

U, S, Vt = svd_power(A, k=4)
print("singular values:", S.round(3))
print("v1:", Vt[0].round(3), " v2:", Vt[1].round(3))

A2 = U[:, :2] * S[:2] @ Vt[:2]                 # best rank-2 approximation
print("rank-2 error ||A-A2||_F^2 =", round(((A - A2) ** 2).sum(), 3),
      " = s3^2 + s4^2 =", round((S[2:] ** 2).sum(), 3))
print("energy kept:", round((S[:2] ** 2).sum() / (S ** 2).sum(), 4))

# new user: Alien = 5, Notting Hill = 1, the rest unknown
known, x = [0, 2], np.array([5.0, 1.0])
z = np.linalg.lstsq(Vt[:2, known].T, x, rcond=None)[0]
print("predicted ratings:", (z @ Vt[:2]).round(2))

# singular values: [14.615  7.22   1.499  1.017]
# v1: [0.579 0.553 0.423 0.425]  v2: [-0.386 -0.462  0.569  0.56 ]
# rank-2 error ||A-A2||_F^2 = 3.281  = s3^2 + s4^2 = 3.281
# energy kept: 0.9878
# predicted ratings: [5.   5.06 1.   1.05]
```

From scratch with NumPy: power iteration + deflation, applied to the worked example.

```python
import numpy as np
from sklearn.utils.extmath import randomized_svd

A = np.array([[5, 5, 1, 1], [4, 5, 1, 2], [5, 4, 2, 1],
              [1, 1, 5, 4], [2, 1, 4, 5], [3, 3, 3, 3]], float)

U, s, Vt = np.linalg.svd(A, full_matrices=False)   # exact, LAPACK
print("sigma:", s.round(3))
print("energy:", (np.cumsum(s**2) / (s**2).sum()).round(4))

k = 2
A2 = U[:, :k] @ np.diag(s[:k]) @ Vt[:k]
print("Frobenius error:", round(np.linalg.norm(A - A2), 3),
      " spectral error:", round(np.linalg.norm(A - A2, 2), 3))

# Randomized SVD: only the top k, cost O(m n k) -- what you use on big matrices
Ur, sr, Vtr = randomized_svd(A, n_components=k, random_state=0)
print("randomized sigma:", sr.round(3))

# Pseudo-inverse from the SVD solves least squares
print("pinv(A) @ A ~ I:", np.allclose(np.linalg.pinv(A) @ A, np.eye(4)))
print("condition number:", round(s[0] / s[-1], 2))

# sigma: [14.615  7.22   1.499  1.017]
# energy: [0.794  0.9878 0.9962 1.    ]
# Frobenius error: 1.811  spectral error: 1.499
# randomized sigma: [14.615  7.22 ]
# pinv(A) @ A ~ I: True
# condition number: 14.37
```

Library version: exact LAPACK SVD, randomized top-k SVD from scikit-learn, and the pseudo-inverse.

Note the two error norms: the Frobenius error $1.811=\sqrt{3.281}$ is the root of the dropped energy, while the spectral error $1.499$ is exactly $\sigma_3$ — Eckart–Young in both norms.

**Strengths**

- You need the best low-rank approximation of a matrix with a guaranteed, computable error.
- You want latent factors of a matrix (users × items, documents × terms, time × sensors) or to compress / denoise it.
- You are solving least squares that may be rank-deficient or ill-conditioned — the SVD shows and controls the small σ's.
- You need numerically stable rank, null space, condition number or pseudo-inverse.

**Limitations**

- The structure is nonlinear (curved manifolds, clusters) — linear layers miss it; consider **Kernel PCA**, **t-SNE** or **UMAP**.
- You need parts-based, non-negative factors that are easy to interpret — singular vectors mix signs; use **NMF**.
- The matrix is huge and sparse — a dense exact SVD is infeasible; use a truncated / randomized solver (**Truncated SVD**).
- Many entries are missing — a plain SVD needs a complete matrix; use matrix-completion methods.
- Outliers are present — squared error lets a few large entries dominate σ₁ (robust PCA addresses this).

- **Recommender systems:** Latent-factor models factor the users × items matrix; the Netflix Prize era popularized SVD-style factorizations fitted on observed ratings only.
- **Image and signal compression:** An $m\times n$ image stored as $A_k$ needs $k(m+n+1)$ numbers; natural images have fast-decaying spectra, so modest $k$ looks close to the original.
- **Text: latent semantic analysis:** The SVD of a documents × terms matrix groups co-occurring words into topics — the main use of **Truncated SVD**.
- **Numerical solvers and statistics:** Least squares (lstsq), pseudo-inverses, rank and condition-number checks, PCA, canonical correlation and many regularized regression methods are computed through the SVD.

**Question:** A matrix has singular values 10, 3 and 1. What is the Frobenius error of its best rank-1 approximation?

- A. 1
- B. 3
- C. √10 ≈ 3.162
- D. 10

**Answer:** C. √10 ≈ 3.162 — By Eckart–Young, $\|A-A_1\|_F^2=\sigma_2^2+\sigma_3^2=9+1=10$, so the error is $\sqrt{10}=3.162$. The spectral-norm error would be $\sigma_2=3$.

**Question:** How are the singular values of A related to the eigenvalues of AᵀA?

- A. They are equal
- B. σᵢ = √λᵢ
- C. σᵢ = λᵢ²
- D. σᵢ = 1/λᵢ

**Answer:** B. σᵢ = √λᵢ — $A^\top A=V\Sigma^2V^\top$, so its eigenvalues are $\sigma_i^2$. In the worked example the eigenvalue 213.59 gives $\sigma_1=14.615$.

**Question:** For A = [3 0; 4 5] (σ₁ = 6.708, σ₂ = 2.236), what is the condition number, and what is |det A|?

- A. 3 and 15
- B. 9 and 15
- C. 3 and 8.944
- D. 6.708 and 2.236

**Answer:** A. 3 and 15 — $\kappa=\sigma_1/\sigma_2=6.708/2.236=3$, and $|\det A|$ is the product of the singular values, $6.708\times2.236=15=3\cdot5-0\cdot4$.

**Question:** A 1000×800 grayscale image is stored as its rank-50 truncated SVD. How many numbers are stored, as a share of the raw pixels?

- A. 40,000 (5%)
- B. 90,050 (11.3%)
- C. 400,000 (50%)
- D. 50 (0.006%)

**Answer:** B. 90,050 (11.3%) — $U_{50}$ has $50\cdot1000$, $V_{50}$ has $50\cdot800$, plus 50 singular values: $50(1000+800+1)=90{,}050$, versus $800{,}000$ pixels — 11.3%.

**Key points**

- Every matrix factors as $A=U\Sigma V^\top$: rotate ($V^\top$), stretch ($\sigma_i\ge0$), rotate ($U$) — or a sum of rank-1 layers $\sigma_iu_iv_i^\top$ sorted by importance.
- $v_i$ are eigenvectors of $A^\top A$, $\sigma_i^2$ its eigenvalues, and $u_i=Av_i/\sigma_i$ — but compute with a real SVD routine, never via $A^\top A$.
- Eckart–Young: keeping the top $k$ layers is the best rank-$k$ approximation; the squared Frobenius error is exactly $\sum_{i>k}\sigma_i^2$ and the spectral error is $\sigma_{k+1}$.
- The pseudo-inverse $V\Sigma^+U^\top$ solves least squares; small $\sigma_i$ amplify noise, which truncation or ridge filter factors $\sigma_i^2/(\sigma_i^2+\lambda)$ control.
- PCA is the SVD of centred data; for big or sparse matrices compute only the top $k$ with randomized or Lanczos solvers.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
