Velamuvi AIAcademy

Lesson 14 of 16 · Decompositions

Singular Value Decomposition

Understand the SVD as rotate, stretch, rotate; what singular values measure; how low-rank approximations compress data; and how SVD finds hidden patterns in ratings, images and text.

  • 8 min read
  • Intermediate
  • Reviewed
In this lesson you will learn
  • What the singular value decomposition is
  • The picture behind it: rotate, stretch, rotate
  • What singular values tell you about a matrix
  • How to keep only the important part of a matrix (low-rank approximation)
  • Where SVD is used: compression, recommendations and more

Every matrix, broken into simple steps

Eigenvectors are wonderful, but they only exist for square matrices, and not every square matrix has enough of them. The singular value decomposition works for every matrix, of any shape. It is often called the most useful idea in all of linear algebra.

Rotate, stretch, rotate

Read A = U Σ Vᵀ from right to left, the order in which it acts on a vector:

  1. Vᵀ rotates the input, lining it up with A's most important directions.
  2. Σ stretches along each axis, by a different amount on each.
  3. U rotates the result into its final position.

So every linear transformation, however complicated it looks, is just a rotation, then a stretch along perpendicular axes, then another rotation.

Try it yourselfPython
import numpy as np

A = np.array([[3.0, 1.0],
              [1.0, 3.0],
              [1.0, 1.0]])            # a 3 x 2 matrix: no eigenvectors, but an SVD

U, S, Vt = np.linalg.svd(A, full_matrices=False)

print("shapes:", U.shape, S.shape, Vt.shape)
print("singular values:", np.round(S, 3))
print("rebuilt A:")
print(np.round(U @ np.diag(S) @ Vt, 6) + 0.0)

Multiplying the three pieces back together gives the original matrix exactly.

Singular values reveal hidden structure

Here is a small table of film ratings: 5 users (rows) and 4 films (columns). The first two films are action, the last two are romance.

Try it yourselfPython
import numpy as np

ratings = np.array([
    [5, 4, 1, 1],
    [4, 5, 1, 2],
    [1, 1, 5, 4],
    [2, 1, 4, 5],
    [5, 5, 2, 1],
], dtype=float)

S = np.linalg.svd(ratings, compute_uv=False)     # just the singular values
print(np.round(S, 2))

Two singular values are large, and the other two are small. That tells you the table is mostly explained by two hidden factors, here a taste for action and a taste for romance, even though nobody labelled them. The small values are mostly noise.

Keeping only what matters

Try it yourselfPython
import numpy as np

ratings = np.array([
    [5, 4, 1, 1],
    [4, 5, 1, 2],
    [1, 1, 5, 4],
    [2, 1, 4, 5],
    [5, 5, 2, 1],
], dtype=float)

U, S, Vt = np.linalg.svd(ratings, full_matrices=False)

k = 2
approx = U[:, :k] @ np.diag(S[:k]) @ Vt[:k, :]

print(np.round(approx, 1) + 0.0)
error = np.linalg.norm(ratings - approx) / np.linalg.norm(ratings)
print(f"relative error with rank {k}: {error:.1%}")

With only 2 of the 4 "ingredients", the rebuilt table keeps the clear pattern of the original: action fans still rate action films highly, and romance fans romance films. The overall error is only about 12%. Recommendation systems use exactly this idea: a missing rating can be predicted from the hidden factors.

How much does each part explain?

The "energy" of a matrix is the sum of its squared singular values. The share of energy in the top k values tells you how much of the matrix they capture:

Try it yourselfPython
import numpy as np

S = np.array([13.38, 7.12, 1.41, 1.14])     # the singular values of the ratings table
energy = S ** 2
share = energy / energy.sum()

total = 0.0
for k in range(len(S)):
    total += share[k]
    print(f"top {k + 1}: {total:.1%}")

The top two singular values hold about 98% of the energy, which is why the rank-2 approximation was so good.

Common mistakes

Practice exercise

Decide how many singular values you need to keep 95% of a matrix's energy.

Your solutionPython
import numpy as np

# The singular values of a large data matrix
S = np.array([20.0, 10.0, 5.0, 2.0, 1.0])

# 1. Work out each singular value's share of the energy (squared values / total of squares).
# 2. Print the cumulative share for the top 1, 2 and 3 values, as percentages with 1 decimal place.
# 3. Print the smallest k whose cumulative share is at least 95%.

# Output must be exactly:
# top 1: 75.5%
# top 2: 94.3%
# top 3: 99.1%
# smallest k for 95%: 3
Knowledge check

What does the SVD do to a vector, read as A = U Σ Vᵀ?

Summary

  • The SVD writes any matrix as A = U Σ Vᵀ: rotate, stretch, rotate.
  • Singular values are the stretch amounts, never negative and sorted from largest to smallest.
  • A few large singular values mean the data has a few strong hidden patterns.
  • A low-rank approximation keeps the top k values: the best compression of that size.
  • The share of squared singular values tells you how much each part explains.

Next: PCA, which uses these ideas to shrink data to its most important directions.

Finished reading? Tick it off to track your progress.