Singular Value Decomposition and Low-Rank Approximation

Hello. In the previous lesson, eigendecomposition gave a clean description of a symmetric square matrix: rotate into its eigenvector coordinates, scale each coordinate by an eigenvalue, then rotate back.

Singular value decomposition (SVD) extends that idea to any real matrix, including rectangular matrices such as a data matrix with many examples and relatively few features. It will become a key mathematical tool behind compression, denoising, dimensionality reduction, and several low-rank techniques used in modern ML systems.

By the end of this lesson, you should be able to compute the SVD of a small matrix using eigendecomposition of $A^{\top }A$, form a rank-$k$ approximation, and explain precisely why retaining the largest singular values is the best low-rank approximation under common error measures.

---

SVD: independent input and output directions

For any real matrix

$$A\in {\mathbb{R}}^{m\times n}$$

the singular value decomposition is

$$A=U\Sigma V^{\top }$$

where:

• $U\in {\mathbb{R}}^{m\times m}$ is orthogonal. Its columns are the left singular vectors.
• $V\in {\mathbb{R}}^{n\times n}$ is orthogonal. Its columns are the right singular vectors.
• $\Sigma \in {\mathbb{R}}^{m\times n}$ is diagonal in the rectangular sense: entries may be nonzero only along its leading diagonal.
• The diagonal entries of $\Sigma$ are the singular values:

$${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$$

where $r=\mathrm{rank}(A)$.

Unlike eigenvalues, singular values are always nonnegative.

To interpret the transformation, read the product from right to left:

$$A\mathbf{x}=U\Sigma V^{\top }\mathbf{x}$$

1. $V^{\top }$ expresses an input vector in the right-singular-vector basis.
2. $\Sigma$ scales each resulting coordinate by a nonnegative singular value.
3. $U$ expresses the result in the output space using left singular vectors.

This distinction between input directions and output directions is why SVD applies to rectangular matrices. A matrix may map an $n$-dimensional input into an $m$-dimensional output, so it needs two potentially different orthonormal bases.

The central relation is:

$$A^{\top }A=V{\Sigma }^{\top }\Sigma V^{\top }$$

Since $A^{\top }A$ is symmetric and positive semidefinite, it has orthonormal eigenvectors and nonnegative eigenvalues. Comparing this equation with the symmetric eigendecomposition form shows that:

$$A^{\top }A{\mathbf{v}}_i={\sigma }_i^2{\mathbf{v}}_i$$

So:

• ${\mathbf{v}}_i$ is an eigenvector of $A^{\top }A$, hence a right singular vector of $A$;
• the corresponding eigenvalue is ${\sigma }_i^2$;
• therefore,

$${\sigma }_i=\sqrt{{\lambda }_i}$$

For each nonzero singular value, the matching left singular vector is

$${\mathbf{u}}_i=\frac{A{\mathbf{v}}_i}{{\sigma }_i}$$

Equivalently,

$$A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$$

This equation is worth remembering: the matrix sends a right singular direction to its corresponding left singular direction, scaling it by ${\sigma }_i$.

---

Computing an SVD for a small matrix

Consider the rectangular matrix

$$A=\left[\begin{array}{cc}1& 1\\ 0& 1\\ 1& 0\end{array}\right]$$

It has three rows and two columns, so ordinary eigendecomposition of $A$ itself is not available. But $A^{\top }A$ is square:

$$A^{\top }A=\left[\begin{array}{ccc}1& 0& 1\\ 1& 1& 0\end{array}\right]\left[\begin{array}{cc}1& 1\\ 0& 1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}2& 1\\ 1& 2\end{array}\right]$$

This is the same kind of symmetric matrix handled in the prior lesson.

Step 1: Find the right singular vectors

The eigenvalues satisfy

$$\det \left(\left[\begin{array}{cc}2& 1\\ 1& 2\end{array}\right]-\lambda I\right)=0$$ $$(2-\lambda {)}^2-1=0$$

Thus,

$${\lambda }_1=3,{\lambda }_2=1$$

The associated normalized eigenvectors are

$${\mathbf{v}}_1=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right],{\mathbf{v}}_2=\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right]$$

Place them in the columns of $V$:

$$V=\left[\begin{array}{cc}{\mathbf{v}}_1& {\mathbf{v}}_2\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$$

Step 2: Convert eigenvalues into singular values

Because ${\lambda }_i={\sigma }_i^2$,

$${\sigma }_1=\sqrt{3},{\sigma }_2=1$$

The singular values are already in descending order, as required.

Step 3: Find the left singular vectors

Use

$${\mathbf{u}}_i=\frac{A{\mathbf{v}}_i}{{\sigma }_i}$$

For the first vector:

$$A{\mathbf{v}}_1=\left[\begin{array}{cc}1& 1\\ 0& 1\\ 1& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ 1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}2\\ 1\\ 1\end{array}\right]$$

Therefore,

$${\mathbf{u}}_1=\frac{1}{\sqrt{3}}\left(\frac{1}{\sqrt{2}}\left[\begin{array}{c}2\\ 1\\ 1\end{array}\right]\right)=\frac{1}{\sqrt{6}}\left[\begin{array}{c}2\\ 1\\ 1\end{array}\right]$$

For the second vector:

$$A{\mathbf{v}}_2=\left[\begin{array}{cc}1& 1\\ 0& 1\\ 1& 0\end{array}\right]\frac{1}{\sqrt{2}}\left[\begin{array}{c}1\\ -1\end{array}\right]=\frac{1}{\sqrt{2}}\left[\begin{array}{c}0\\ -1\\ 1\end{array}\right]$$

Since ${\sigma }_2=1$,

$${\mathbf{u}}_2=\frac{1}{\sqrt{2}}\left[\begin{array}{c}0\\ -1\\ 1\end{array}\right]$$

For the compact, or thin, SVD, collect only the columns associated with nonzero singular values:

$$U_{\text{thin}}=\left[\begin{array}{cc}{\mathbf{u}}_1& {\mathbf{u}}_2\end{array}\right]=\left[\begin{array}{cc}\frac{2}{\sqrt{6}}& 0\\ \frac{1}{\sqrt{6}}& -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{6}}& \frac{1}{\sqrt{2}}\end{array}\right]$$ $${\Sigma }_{\text{thin}}=\left[\begin{array}{cc}\sqrt{3}& 0\\ 0& 1\end{array}\right]$$

The thin SVD is therefore

$$A=U_{\text{thin}}{\Sigma }_{\text{thin}}{V}^{\top }$$

The thin form is usually what you want in ML code: it omits orthonormal basis directions multiplied by zero singular values.

A careful shape check:

$$(3\times 2)(2\times 2)(2\times 2)=3\times 2$$

Also note the important truncated-matrix identity:

$$U_k^{\top }{U}_k=I_k$$

but generally

$$U_k{U}_k^{\top }\ne I_m$$

because $U_k$ is tall and has only $k$ columns. The product $U_k{U}_k^{\top }$ is instead a rank-$k$ projection matrix.

---

SVD as a sum of rank-one patterns

The most useful way to read an SVD is as a sum:

$$A=\sum _{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\top }$$

Each term

$${\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\top }$$

is a rank-one matrix.

The product ${\mathbf{u}}_i{\mathbf{v}}_i^{\top }$ is an outer product: it combines one output-direction vector with one input-direction vector to produce an entire matrix. The singular value determines the strength of that pattern.

For our example,

$$A={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^{\top }+{\sigma }_2{\mathbf{u}}_2{\mathbf{v}}_2^{\top }$$

The first rank-one component is

$${\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^{\top }=\left[\begin{array}{cc}1& 1\\ \frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right]$$

The second component is

$${\sigma }_2{\mathbf{u}}_2{\mathbf{v}}_2^{\top }=\left[\begin{array}{cc}0& 0\\ -\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& -\frac{1}{2}\end{array}\right]$$

Adding them recovers $A$:

$$\left[\begin{array}{cc}1& 1\\ \frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right]+\left[\begin{array}{cc}0& 0\\ -\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& -\frac{1}{2}\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 0& 1\\ 1& 0\end{array}\right]$$

The first term captures the larger shared structure across the two columns. The second, smaller term captures the contrast between them. This “dominant pattern plus correction patterns” interpretation is the foundation of low-rank approximation.

---

Truncated SVD and low-rank approximation

Suppose the singular values are ordered from largest to smallest. The rank-$k$ truncated SVD keeps only the first $k$ rank-one terms:

$$A_k=\sum _{i=1}^k{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\top }$$

In matrix form,

$$A_k=U_k{\Sigma }_k{V}_k^{\top }$$

where:

• $U_k\in {\mathbb{R}}^{m\times k}$ contains the first $k$ left singular vectors;
• ${\Sigma }_k\in {\mathbb{R}}^{k\times k}$ contains the largest $k$ singular values;
• $V_k^{\top }\in {\mathbb{R}}^{k\times n}$ contains the first $k$ right singular vectors as rows.

Because the product passes through a $k$-dimensional middle space,

$$\mathrm{rank}(A_k)\le k$$

For our example, the rank-one approximation is simply the first component:

$$A_1={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^{\top }=\left[\begin{array}{cc}1& 1\\ \frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right]$$

It does not reproduce $A$ exactly. Its residual is

$$A-A_1=\left[\begin{array}{cc}0& 0\\ -\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& -\frac{1}{2}\end{array}\right]$$

The approximation has deliberately discarded the second, weaker singular pattern.

Why keep the largest singular values?

The Eckart-Young theorem states that $A_k$ is the closest matrix to $A$ among all matrices with rank at most $k$, under both the Frobenius norm and the spectral norm.

For the Frobenius norm,

$$\Vert A-B{\Vert }_F=\sqrt{\sum _{i,j}(A_{ij}-B_{ij}{)}^2}$$

the theorem says:

$$A_k=\underset{\mathrm{rank}(B)\le k}{\mathrm{argmin}}\Vert A-B{\Vert }_F$$

The squared error has a particularly useful form:

$$\Vert A-A_k{\Vert }_F^2=\sum _{i=k+1}^r{\sigma }_i^2$$

For the rank-one approximation in the example,

$$\Vert A-A_1{\Vert }_F^2={\sigma }_2^2=1$$

No other rank-one matrix can achieve a smaller squared Frobenius reconstruction error.

This is stronger than saying that SVD gives a convenient approximation. It gives the provably best approximation for the chosen rank and error measure.

---

What low rank means for ML data

A low-rank approximation is useful when a large matrix is governed by a relatively small number of shared patterns.

If $A$ is $m\times n$, storing every entry requires $mn$ numbers. A rank-$k$ representation stores approximately

$$mk+k+kn$$

numbers instead. When

$$k\ll \min (m,n)$$

this can be much smaller than $mn$.

Common interpretations depend on what rows and columns mean:

Matrix interpretation	Left singular vectors $U_k$	Right singular vectors $V_k$
Image matrix	Image-side spatial patterns	Pixel-direction patterns
User-item interaction matrix	User patterns	Item patterns
Document-term matrix	Document patterns	Term or topic-like patterns
Centered tabular data matrix	Example scores along dominant directions	Feature directions

The orientation is not cosmetic. If rows are examples and columns are features, $V_k$ lives in feature space, while $U_k$ describes how individual examples express the retained patterns.

A common diagnostic before choosing $k$ is the fraction of squared singular-value mass retained:

$$\frac{{\sum }_{i=1}^k{\sigma }_i^2}{{\sum }_{i=1}^r{\sigma }_i^2}$$

A rapid drop in singular values suggests that a small rank may approximate the matrix well. A slow decline means a low-rank approximation will discard substantial structure.

Two practical cautions matter:

• Small does not automatically mean noise. Tail singular components can contain rare classes, minority-group behavior, important edge cases, or real but subtle signals.
• Data preprocessing affects the decomposition. For feature data, centering and often scaling decisions can substantially change which directions dominate. The connection to PCA will make this precise later.

---

PyTorch verification

In PyTorch, use torch.linalg.svd. It returns $U$, a vector of singular values, and Vh, which is $V^{\top }$ for real-valued matrices.

import torch

A = torch.tensor(
    [
        [1.0, 1.0],
        [0.0, 1.0],
        [1.0, 0.0],
    ]
)

# Thin SVD: U is 3 by 2, s has length 2, Vh is 2 by 2
U, s, Vh = torch.linalg.svd(A, full_matrices=False)

# Exact reconstruction
A_reconstructed = (U * s) @ Vh
assert torch.allclose(A, A_reconstructed)

# Rank-1 approximation
k = 1
A1 = (U[:, :k] * s[:k]) @ Vh[:k, :]

# Eckart-Young reconstruction error
squared_error = torch.linalg.matrix_norm(A - A1, ord="fro") ** 2
assert torch.allclose(squared_error, s[1] ** 2)

print(s)
print(A1)

torch.linalg.svd returns singular values in descending order, so slicing the first $k$ components gives the truncated SVD directly.

Do not expect the signs of U and Vh to match a handwritten solution. For any singular-vector pair, simultaneously replacing

$${\mathbf{u}}_i\to -{\mathbf{u}}_i$$

and

$${\mathbf{v}}_i\to -{\mathbf{v}}_i$$

leaves the rank-one term unchanged:

$${\sigma }_i(-{\mathbf{u}}_i)(-{\mathbf{v}}_i{)}^{\top }={\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\top }$$

Verify the reconstruction and approximation error rather than comparing singular-vector signs.

---

Key takeaways

SVD decomposes any real matrix as

$$A=U\Sigma V^{\top }$$

with orthonormal left and right singular vectors and nonnegative singular values. You can compute the right singular vectors from the eigendecomposition of $A^{\top }A$, obtain singular values by square-rooting its eigenvalues, and calculate left singular vectors using

$${\mathbf{u}}_i=\frac{A{\mathbf{v}}_i}{{\sigma }_i}$$

Most importantly, SVD writes a matrix as a sum of ordered rank-one patterns:

$$A=\sum _{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^{\top }$$

Keeping only the first $k$ terms produces

$$A_k=U_k{\Sigma }_k{V}_k^{\top }$$

the best rank-$k$ approximation under common matrix norms. This is the mathematical reason low-rank methods can compress or simplify structured data while retaining its dominant patterns.

Next, you will shift from linear algebra to multivariable calculus: partial derivatives and gradients, the machinery that lets ML models determine how to change their parameters.