3.8.3 Practice set: the singular value decomposition

The singular value decomposition

The singular value decomposition (lesson 3.8.1)

0 of 10 correct

1.
Find $\sigma_1$ for $\begin{pmatrix} 0 & 3 \\ 2 & 0 \end{pmatrix}$
2.
A $2 \times 2$ matrix sends every unit vector to a vector of length 3. What is $\sigma_2$ ?
3.
$\sigma_1 = 5$ and $A\mathbf{v}_1 = (3, 4)$ . What is the first entry of $\mathbf{u}_1$ ?
4.
Find $\sigma_1$ for the $3 \times 2$ matrix of ones (type sqrt for a square root)
5.
A $3 \times 3$ matrix has singular values 4, 2 and 0.5. Find $\lvert\det A\rvert$
6.
The same matrix: find its condition number $\sigma_1 / \sigma_3$
7.
$A$ is $5 \times 3$ with rank 2. How many of the singular values that np.linalg.svd returns are 0?
8.
np.linalg.svd returns Vt whose second row is $(0.8, -0.6)$ . What is the second entry of $\mathbf{v}_2$ ?
9.
Both eigenvalues of the shear $\begin{pmatrix} 1 & 4 \\ 0 & 1 \end{pmatrix}$ are 1. Find $\sigma_1\sigma_2$
10.
For the same shear, $A^\top A$ has trace 18 and determinant 1. Find $\sigma_1$ (type sqrt for a square root)

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Low-rank approximation

Low-rank approximation (lesson 3.8.2)

0 of 10 correct

1.
$A$ has singular values 6, 3 and 2. Find $\lVert A \rVert_F$
2.
The same $A$ : find $\lVert A - A_1 \rVert_2$
3.
The same $A$ : find $\lVert A - A_1 \rVert_F$ (type sqrt for a square root)
4.
The same $A$ : what share of the squared size does $A_2$ keep? Give a fraction
5.
For $A = \begin{pmatrix} 3 & 0 \\ 0 & 1 \end{pmatrix}$ , what is the entry in row 2, column 2 of $A_1$ ?
6.
How many numbers store a rank-3 copy of a $120 \times 20$ matrix?
7.
A copy keeps 96% of the squared size. What is its relative error $\lVert A - A_k \rVert_F / \lVert A \rVert_F$ ?
8.
Singular values 4, 2, 1 and 1. What is the smallest $k$ whose copy keeps at least 95% of the squared size?
9.
Singular values 3 and 1. What share of the squared size does $A_1$ keep? Give a fraction
10.
Singular values 5, 4, 2 and 1. Find $\lVert A - A_2 \rVert_2$

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

Coding exercise

Exercise

The best rank-k copy

Write two functions with NumPy, using np.linalg.svd(A, full_matrices=False) as in lessons 3.8.1 and 3.8.2.

best_rank_k(A, k) returns $A_k = U_kS_kV_k^\top$ as a float array with the shape of A; $k = 0$ gives zeros. Raise ValueError if A is not 2-D, or if k is not a whole number from 0 to $\min(m, n)$ .
rank_for_share(A, share) returns the smallest $k$ whose copy keeps at least share of the squared size, $\sum_{i \le k}\sigma_i^2 / \sum_i \sigma_i^2$ . Raise ValueError unless $0 < \text{share} \le 1$ , and if A is all zeros.

Rounding matters in the second function. $B$ 's first piece keeps exactly 60% of its squared size, yet the computed share can come out a hair below 0.6. Count a share within $10^{-12}$ of the target as reaching it.

The tests use $B$ and $M$ from the lessons, a rank-1 table, a random $6 \times 4$ matrix and a wide one. A version that adds up $\sigma_i$ instead of $\sigma_i^2$ fails them.

See the tests

import numpy as np

B = np.array([[2, 0], [1, 1], [0, 2]])  # lesson 3.8.1's tall matrix
M = np.array([[6, 4, 2, 1], [4, 3, 2, 1], [2, 2, 2, 2], [1, 1, 2, 4], [0, 1, 2, 5]])  # lesson 3.8.2
T = np.outer([1, 2, 3], [1, 2, 3])  # a table of rank 1


def _raises(f, what):
    try:
        f()
    except ValueError:
        return
    raise AssertionError(f"expected ValueError for {what}")


def test_tall_rank_one():
    """The rank-1 copy of lesson 3.8.1's B is the 3 × 2 table of ones"""
    expect_close(best_rank_k(B, 1), np.ones((3, 2)), what="best_rank_k(B, 1)", abs_tol=1e-9)


def test_full_rank_gives_back_the_matrix():
    """Keeping both pieces of B gives B back"""
    expect_close(best_rank_k(B, 2), B, what="best_rank_k(B, 2)", abs_tol=1e-9)


def test_zero_pieces():
    """k = 0 keeps nothing: a 3 × 2 array of zeros"""
    out = np.asarray(best_rank_k(B, 0))
    expect_equal(out.shape, (3, 2), what="shape of best_rank_k(B, 0)")
    expect_close(out, np.zeros((3, 2)), what="best_rank_k(B, 0)", abs_tol=1e-12)


def test_errors_of_m2():
    """For lesson 3.8.2's M, the rank-2 copy is off by σ₃ = 0.6488 (2-norm) and 0.7232 (Frobenius)"""
    s = np.linalg.svd(M, compute_uv=False)
    err = M - np.asarray(best_rank_k(M, 2))
    expect_close(np.linalg.norm(err, 2), s[2], what="2-norm of M − M₂", rel=1e-9)
    expect_close(np.linalg.norm(err), np.sqrt(s[2] ** 2 + s[3] ** 2), what="Frobenius norm of M − M₂", rel=1e-9)


def test_random_matrix():
    """A random 6 × 4 matrix: the rank-2 copy has rank 2 and the error the rules predict"""
    A = np.random.default_rng(38).standard_normal((6, 4))
    s = np.linalg.svd(A, compute_uv=False)
    A2 = np.asarray(best_rank_k(A, 2))
    expect_equal(int(np.linalg.matrix_rank(A2)), 2, what="rank of best_rank_k(A, 2)")
    expect_close(np.linalg.norm(A - A2), np.sqrt(np.sum(s[2:] ** 2)), what="Frobenius error", rel=1e-9)


def test_wide_matrix_and_lists():
    """A wide 2 × 3 matrix given as a list of lists works: its rank-1 copy is σ₁u₁v₁ᵀ"""
    A = [[3, 0, 4], [0, 1, 0]]
    expect_close(best_rank_k(A, 1), [[3, 0, 4], [0, 0, 0]], what="best_rank_k(wide, 1)", abs_tol=1e-9)


def test_bad_k():
    """k = −1, k = 3 for the 3 × 2 B, and k = 1.5 raise ValueError"""
    _raises(lambda: best_rank_k(B, -1), "k = -1")
    _raises(lambda: best_rank_k(B, 3), "k = 3 for a 3 × 2 matrix")
    _raises(lambda: best_rank_k(B, 1.5), "k = 1.5")


def test_not_a_matrix():
    """A 1-D array is not a matrix: ValueError"""
    _raises(lambda: best_rank_k(np.array([1.0, 2.0, 3.0]), 1), "a 1-D array")


def test_shares_of_m():
    """For M, 90% and 99.5% need k = 2, 99.9% needs k = 3 and 100% needs all 4"""
    expect_equal(rank_for_share(M, 0.9), 2, what="rank_for_share(M, 0.9)")
    expect_equal(rank_for_share(M, 0.995), 2, what="rank_for_share(M, 0.995)")
    expect_equal(rank_for_share(M, 0.999), 3, what="rank_for_share(M, 0.999)")
    expect_equal(rank_for_share(M, 1.0), 4, what="rank_for_share(M, 1.0)")


def test_shares_use_squares():
    """B's first piece keeps exactly 60% of the squared size (6 of 10), so 60% needs k = 1"""
    expect_equal(rank_for_share(B, 0.6), 1, what="rank_for_share(B, 0.6)")


def test_rank_one_table():
    """The rank-1 table keeps 100% with one piece, despite rounding in its other singular values"""
    expect_equal(rank_for_share(T, 1.0), 1, what="rank_for_share(T, 1.0)")


def test_bad_share():
    """A share of 0, 1.5 or −0.1, or a zero matrix, raises ValueError"""
    for share in (0, 1.5, -0.1):
        _raises(lambda: rank_for_share(M, share), f"share = {share}")
    _raises(lambda: rank_for_share(np.zeros((2, 2)), 0.5), "a zero matrix")

The singular value decomposition

Low-rank approximation

Coding exercise

Free further reading