Skip to main content

MATH 345: Linear Algebra and Optimization

Sebastien Roch with Jacob Denson and Kaitlyn Phillipson

Section 6.6 Applications and computation recap

This section checks whether you can read the computations already used in Unit 6.
🔗
A short SVD computation should be read in three steps.
🔗
  1. Identify the shapes.
    🔗
    🔗
  2. Identify the singular directions or singular values being used.
    🔗
    🔗
  3. Interpret what is kept, weakened, or discarded.
    🔗
    🔗
Table 6.6.1. Reading SVD computations
🔗
Code fragment
🔗
First question to ask
🔗
Typical interpretation
🔗
U, s, Vt = np.linalg.svd(A, full_matrices=False)
What are the shapes of U, s, and Vt?
🔗
reduced SVD
🔗
A.T @ A
Which input directions does this matrix analyze?
🔗
eigenvectors give right singular directions
🔗
s
Are the values sorted?
🔗
singular values, largest first
🔗
s**2
Why squares?
🔗
eigenvalues of \(A^TA\) and squared stretch factors
🔗
np.cumsum(s**2)/np.sum(s**2)
How much energy is kept after \(k\) terms?
🔗
cumulative energy retained
🔗
U[:, :k]
Which output directions are kept?
🔗
first \(k\) left singular vectors
🔗
Vt[:k, :]
Which input directions are kept?
🔗
first \(k\) transposed right singular vectors
🔗
U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]
What rank should this have?
🔗
rank-\(k\) reconstruction
🔗
A @ Vt.T[:, i]
What should this equal?
🔗
\(\sigma_i\mathbf{u}_i\)
🔗
Vt[-1, :] with a small last singular value
🔗
Is this exact or numerical?
🔗
approximate forgotten input direction
🔗
B @ C with \(B\in\mathbb R^{m\times r}\text{,}\) \(C\in\mathbb R^{r\times n}\)
🔗
What is the largest possible rank?
🔗
low-rank update
🔗

Subsection Review activities

Activity 6.6.1. Reading SVD shapes.

The following code computes a reduced SVD.
🔗
import numpy as np

A = np.array([[ 1., -1.],
              [-2.,  2.],
              [ 2., -2.]])

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

A.shape, U.shape, s.shape, Vt.shape
Output:
🔗
((3, 2), (3, 2), (2,), (2, 2))
  1. What is the shape of \(A\text{?}\)
    🔗
    🔗
  2. How many singular values are returned?
    🔗
    🔗
  3. Why is s.shape equal to (2,) rather than (2, 2)?
    🔗
    🔗
  4. What matrix does Vt represent?
    🔗
    🔗
  5. What does full_matrices=False do in this example?
    🔗
    🔗
Solution.
The matrix \(A\) is \(3\times 2\text{.}\) The reduced SVD returns two singular values because
\begin{equation*} \min(3,2)=2. \end{equation*}
The array s stores only the diagonal entries of \(\Sigma\text{,}\) not the full diagonal matrix, so its shape is (2,). The array Vt represents \(V^T\text{.}\) With full_matrices=False, NumPy returns the reduced SVD shapes needed for reconstruction:
\begin{equation*} U\in\mathbb R^{3\times 2}, \qquad s\in\mathbb R^2, \qquad V^T\in\mathbb R^{2\times 2}. \end{equation*}
🔗
🔗
🔗

Activity 6.6.2. Checking a singular-vector identity in code.

For an SVD
\begin{equation*} A=U\Sigma V^T, \end{equation*}
the identity
\begin{equation*} A\mathbf{v}_i=\sigma_i\mathbf{u}_i \end{equation*}
is one of the main ways to read the factors. The following code checks this identity for a diagonal stretch.
🔗
A = np.array([[3., 0.],
              [0., 1.]])

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

i = 0
v = Vt.T[:, i]
lhs = A @ v
rhs = s[i] * U[:, i]

lhs, rhs, np.allclose(lhs, rhs)
Output:
🔗
(array([3., 0.]), array([3., 0.]), True)
  1. Which vector is stored in v?
    🔗
    🔗
  2. What does lhs compute?
    🔗
    🔗
  3. What does rhs compute?
    🔗
    🔗
  4. Why does np.allclose(lhs, rhs) return True?
    🔗
    🔗
  5. Which stretch factor appears in this computation?
    🔗
    🔗
Solution.
The vector v is the first right singular vector \(\mathbf{v}_1\text{.}\) The array lhs computes \(A\mathbf{v}_1\text{.}\) The array rhs computes \(\sigma_1\mathbf{u}_1\text{.}\) The value True means that the numerical computation agrees with
\begin{equation*} A\mathbf{v}_1=\sigma_1\mathbf{u}_1. \end{equation*}
The stretch factor is
\begin{equation*} \sigma_1=3. \end{equation*}
🔗
🔗
🔗

Activity 6.6.3. Reading energy retained.

The following code computes cumulative energy retained from a list of singular values.
🔗
np.set_printoptions(precision=4, suppress=True)

s = np.array([10., 4., 1., 0.2])
energy = np.cumsum(s**2) / np.sum(s**2)

energy
Output:
🔗
array([0.8544, 0.9911, 0.9997, 1.    ])
  1. Why does the code use s**2?
    🔗
    🔗
  2. How much energy is retained by \(k=1\text{?}\)
    🔗
    🔗
  3. How much energy is retained by \(k=2\text{?}\)
    🔗
    🔗
  4. What is the smallest \(k\) that retains at least \(90\%\) of the energy?
    🔗
    🔗
  5. What is discarded in a rank-2 reconstruction?
    🔗
    🔗
Solution.
Squared singular values measure squared stretch and are used for the energy calculation. For \(k=1\text{,}\) the retained energy is approximately
\begin{equation*} 0.8544. \end{equation*}
For \(k=2\text{,}\) the retained energy is approximately
\begin{equation*} 0.9911. \end{equation*}
The smallest \(k\) retaining at least \(90\%\) of the energy is
\begin{equation*} k=2. \end{equation*}
A rank-2 reconstruction keeps the directions corresponding to singular values \(10\) and \(4\text{,}\) and discards the smaller directions corresponding to singular values \(1\) and \(0.2\text{.}\)
🔗
🔗
🔗

Activity 6.6.4. Debugging an SVD slice.

A student tries to compute a rank-one reconstruction using this code.
🔗
A = np.array([[3., 0.],
              [0., 1.]])

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

k = 1
Ak_wrong = U[:, :k] @ np.diag(s[:k]) @ Vt[:, :k]
  1. Which slice is wrong?
    🔗
    🔗
  2. What should the last slice be?
    🔗
    🔗
  3. What shape problem appears when \(A\) is \(2\times 2\) and \(k=1\text{?}\)
    🔗
    🔗
  4. What is the mathematical mistake?
    🔗
    🔗
Solution.
The wrong slice is Vt[:, :k]. The reconstruction should use Vt[:k, :]. When \(A\) is \(2\times 2\) and \(k=1\text{,}\) the shapes are
\begin{equation*} U[:, :1]\in\mathbb R^{2\times 1}, \qquad \operatorname{diag}(s[:1])\in\mathbb R^{1\times 1}, \qquad Vt[:, :1]\in\mathbb R^{2\times 1}. \end{equation*}
After the first two factors are multiplied, the result has shape \(2\times 1\text{,}\) which cannot be multiplied by a \(2\times 1\) matrix on the right.
🔗
The mathematical mistake is that columns of \(V^T\) are not the transposed right singular vectors used in the reconstruction. The rows of \(V^T\) are the transposed right singular vectors, so the correct slice is Vt[:k, :].
🔗
🔗
🔗

Activity 6.6.5. Reading a low-rank update shape.

The following code counts storage for a low-rank update.
🔗
m, n, r = 1000, 800, 4

W_shape = (m, n)
B_shape = (m, r)
C_shape = (r, n)
update_shape = (m, n)

storage_update = m*r + r*n
storage_full = m*n

W_shape, B_shape, C_shape, update_shape, storage_update, storage_full
Output:
🔗
((1000, 800), (1000, 4), (4, 800), (1000, 800), 7200, 800000)
  1. What is the shape of \(W\text{?}\)
    🔗
    🔗
  2. What is the shape of \(BC\text{?}\)
    🔗
    🔗
  3. What is the largest possible rank of \(BC\text{?}\)
    🔗
    🔗
  4. How many numbers are needed to store \(B\) and \(C\text{?}\)
    🔗
    🔗
  5. How many numbers are needed to store a full \(1000\times 800\) matrix?
    🔗
    🔗
Solution.
The matrix \(W\) has shape
\begin{equation*} 1000\times 800. \end{equation*}
Since
\begin{equation*} B\in\mathbb R^{1000\times 4}, \qquad C\in\mathbb R^{4\times 800}, \end{equation*}
the product \(BC\) has shape
\begin{equation*} 1000\times 800. \end{equation*}
Its rank is at most \(4\text{.}\) The matrices \(B\) and \(C\) require
\begin{equation*} 1000\cdot 4+4\cdot 800=7200 \end{equation*}
numbers. A full \(1000\times 800\) matrix requires
\begin{equation*} 1000\cdot 800=800000 \end{equation*}
numbers.
🔗
🔗
🔗
🔗

Note 6.6.2. Linked notebook.

Run Lab U6: SVD and Compression
 1 
sebroc.github.io/MATH345-Course-Materials/labs/#lab-u6
. The core path practices SVD shapes, singular values, singular-vector identities, rank and null directions, redundant features, energy retained, rank-\(k\) reconstruction, compression on a small matrix, low-rank update shapes, and review code-reading checks. The activities above prepare you to read the notebook outputs as mathematical statements.
🔗
For a quick reference on SVD commands, diagonal matrices, slices, matrix multiplication, and numerical checks such as np.allclose, see the programming appendix sections B.10, B.8, B.3, B.4, and B.9.
🔗
🔗
Interpretation check. Given singular values, choose \(k\) to retain a specified percentage of energy. Explain what information is discarded when small singular values are removed. Tags. [U6-LO6, U6-LO7 | C+M+T | Core]
🔗
Exam-style check. The singular values are
\begin{equation*} 10,\ 4,\ 1,\ 0.2. \end{equation*}
Which directions are most important, and what is discarded in a rank-2 approximation? Tags. [U6-LO6, U6-LO7 | C+M | Core]
🔗
Exam skill. Read a short SVD computation and explain singular values, rank, retained energy, forgotten directions, and rank-\(k\) reconstruction without coding the SVD from scratch. Tags. [U6-LO4, U6-LO5, U6-LO6, U6-LO7 | C+M+T | Core]
🔗
🔗
PrevTopNext