Singular Value Decomposition (SVD)

Source: Unit 4 §10

Every matrix does the same two things to a vector: it scales it and it rotates it. SVD is the statement that those two effects can always be pulled apart and written down separately.

⚠GotchaThe SVD deck was mostly images, so parts of this page are reconstructed

The slides for this section are largely image and equation pictures that do not extract as text. The statements, the matrix table and the applications come straight from them, but the derivations and the worked $AA^{T}$ example are reconstructed from standard material and follow the slide flow rather than being transcribed from it. The same caveat applies to FP-Growth. Treat the results as reliable and the exact wording of the intermediate steps as this page's, not the lecturer's.

Intuition: what a matrix does to a vector

When you multiply a matrix by a vector, the vector scales and/or rotates. Do it to a whole set of vectors forming a circle or a sphere and the same thing happens to the shape. SVD finds the matrices that capture that rotation and that scaling.

A matrix turns a circle into an ellipse. U is the new set of axes, and the singular values are how far each axis got stretched.

≡FactsWhat falls out of a unit sphere in N dimensions

• Multiplying by matrix $A$ gives a new coordinate system U, the principal axes.
• It also gives stretch factors α, the singular values.

The decomposition

Any $m \times n$ matrix $A$ can be written as a product of three matrices:

$$A = U \, \Sigma \, V^{T}$$

The shapes are forced: U is square in m, Vᵀ is square in n, and Σ is the only rectangular factor, so the product comes back out as m × n.

Matrix	What it is
U (m×m)	columns = **orthonormal eigenvectors of AAᵀ (the left** singular vectors uᵢ)
Σ (m×n)	diagonal, holding the singular values (the square roots of the eigenvalues) in descending order
Vᵀ (n×n)	rows = **orthonormal eigenvectors of AᵀA (the right** singular vectors vᵢ)

Why AAᵀ and AᵀA are special

For any $m \times n$ matrix $A$, both AAᵀ and AᵀA are:

• Symmetric
• Square
• have the same positive eigenvalues
• have the same rank r as $A$

Because they are symmetric, their eigenvectors can be chosen to be orthonormal - perpendicular and of unit length. Those are the singular vectors: uᵢ from AAᵀ and vᵢ from AᵀA. The square roots of the shared eigenvalues are the singular values $\sigma_i$.

◎Exam cueOrthogonal vs orthonormal

Two vectors are orthogonal when their inner (dot) product is 0, which means the angle between them is 90°. Orthonormal means orthogonal and unit length.

The recipe

→StepsComputing an SVD by hand

1. Compute AAᵀ, find its eigenvalues and eigenvectors, orthonormalize them (Gram-Schmidt): these are the columns of U.
2. Compute AᵀA, find its eigenvalues and eigenvectors, orthonormalize them: these are the columns of V.
3. Build Σ as the diagonal of singular values $\sigma_i = \sqrt{\text{eigenvalue}_i}$, in descending order.

A compact worked example

Take the $2 \times 3$ matrix $A = \begin{bmatrix} 3 & 1 & 1 \\ -1 & 3 & 1 \end{bmatrix}$.

→StepsFinding Σ

1. Form AAᵀ. The diagonal entries are the squared row norms and the off-diagonal is the dot product of the two rows: $AA^{T} = \begin{bmatrix} 3^2+1^2+1^2 & 3(-1)+1\cdot3+1\cdot1 \\ \cdot & (-1)^2+3^2+1^2 \end{bmatrix} = \begin{bmatrix} 11 & 1 \\ 1 & 11 \end{bmatrix}$.
2. Eigenvalues of AAᵀ are $11 \pm 1$, so $\lambda_1 = 12$ and $\lambda_2 = 10$.
3. Singular values are their square roots: $\sigma_1 = \sqrt{12} = 2\sqrt{3}$ and $\sigma_2 = \sqrt{10}$.
4. Assemble Σ at the size of A: $\Sigma = \begin{bmatrix} 2\sqrt{3} & 0 & 0 \\ 0 & \sqrt{10} & 0 \end{bmatrix}$. U comes from the eigenvectors of AAᵀ, and V from those of AᵀA.

Three views of SVD, and its applications

≡FactsThree ways to see the same factorisation

• Dimensionality reduction - capture the essence of moving from higher to lower dimensions.
• Variance ordering - identify and order the dimensions along which the data varies most.
• Decorrelation - transform correlated variables into uncorrelated ones that expose the relationships.

Applications: Page Ranking, Recommendation Systems, Image Compression, Facial Recognition, Noise reduction.

Truncating to the top k singular values keeps a thin slice of U and Vᵀ. The reconstruction is still recognisable because the dropped values were small.

◎Exam cueThe "Tiger" intuition from the slides

A high-dimensional image of you is still recognisably you using just the top ~20% of dimensions - the ones with the largest singular values. The rest is redundancy and noise. That is low-rank approximation via SVD: keep the largest singular values, drop the small ones, and get massive compression with little information loss.

$$A \approx U_k \, \Sigma_k \, V_k^{T} \qquad \text{(keep only the top } k \text{ singular values)}$$