Skip to main content

MATH 345: Linear Algebra and Optimization

Sebastien Roch with Jacob Denson and Kaitlyn Phillipson

Section 6.5 Low-rank approximation and compression

Application question. How can a matrix be approximated by keeping only its strongest directions?
🔗
The SVD writes a matrix map as a sum of directional pieces. If
\begin{equation*} A=U\Sigma V^T \end{equation*}
has rank \(r\text{,}\) then
\begin{equation*} A = \sum_{i=1}^r \sigma_i\mathbf{u}_i\mathbf{v}_i^T. \end{equation*}
The matrix
\begin{equation*} \sigma_i\mathbf{u}_i\mathbf{v}_i^T \end{equation*}
has rank one. It measures the input coordinate in the direction \(\mathbf{v}_i\text{,}\) stretches by \(\sigma_i\text{,}\) and sends the result in the output direction \(\mathbf{u}_i\text{.}\)
🔗

Definition 6.5.1. Rank-\(k\) reconstruction.

Let
\begin{equation*} A=U\Sigma V^T \end{equation*}
be an SVD of a rank-\(r\) matrix \(A\text{.}\) For \(1\leq k\leq r\text{,}\) the rank-\(k\) reconstruction of \(A\) is
\begin{equation*} A_k = U_k\Sigma_kV_k^T = \sum_{i=1}^k \sigma_i\mathbf{u}_i\mathbf{v}_i^T, \end{equation*}
where \(U_k\) contains the first \(k\) columns of \(U\text{,}\) \(\Sigma_k\) contains the first \(k\) singular values, and \(V_k\) contains the first \(k\) columns of \(V\text{.}\)
🔗
The matrix \(A_k\) keeps the \(k\) largest singular directions and discards the rest. Its rank is at most \(k\text{.}\)
🔗
🔗

Activity 6.5.1. Rank-one reconstruction of a diagonal stretch.

Return to the diagonal stretch from Section 6.3:
\begin{equation*} A= \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix}. \end{equation*}
For this matrix, the right and left singular vectors are
\begin{equation*} \mathbf{e}_1= \begin{bmatrix} 1\\ 0 \end{bmatrix}, \qquad \mathbf{e}_2= \begin{bmatrix} 0\\ 1 \end{bmatrix}, \end{equation*}
and the singular values are
\begin{equation*} \sigma_1=3, \qquad \sigma_2=1. \end{equation*}
🔗
  1. Write \(A\) as
    \begin{equation*} 3\mathbf{e}_1\mathbf{e}_1^T+\mathbf{e}_2\mathbf{e}_2^T. \end{equation*}
    🔗
    🔗
  2. Compute the rank-one reconstruction
    \begin{equation*} A_1=3\mathbf{e}_1\mathbf{e}_1^T. \end{equation*}
    🔗
    🔗
  3. For
    \begin{equation*} \mathbf{x}= \begin{bmatrix} a\\ b \end{bmatrix}, \end{equation*}
    compute \(A\mathbf{x}\) and \(A_1\mathbf{x}\text{.}\)
    🔗
    🔗
  4. Which input direction is discarded by \(A_1\text{?}\)
    🔗
    🔗
  5. What is \(\operatorname{rank}(A_1)\text{?}\)
    🔗
    🔗
Solution.
We have
\begin{align*} \mathbf{e}_1\mathbf{e}_1^T\\ \amp = \begin{bmatrix} 1\\ 0 \end{bmatrix} \begin{bmatrix} 1 \amp 0 \end{bmatrix}\\ \amp = \begin{bmatrix} 1 \amp 0\\ 0 \amp 0 \end{bmatrix} \end{align*}
and
\begin{align*} \mathbf{e}_2\mathbf{e}_2^T\\ \amp = \begin{bmatrix} 0\\ 1 \end{bmatrix} \begin{bmatrix} 0 \amp 1 \end{bmatrix}\\ \amp = \begin{bmatrix} 0 \amp 0\\ 0 \amp 1 \end{bmatrix}. \end{align*}
Thus
\begin{align*} 3\mathbf{e}_1\mathbf{e}_1^T+\mathbf{e}_2\mathbf{e}_2^T\\ \amp = 3 \begin{bmatrix} 1 \amp 0\\ 0 \amp 0 \end{bmatrix} + \begin{bmatrix} 0 \amp 0\\ 0 \amp 1 \end{bmatrix}\\ \amp = \begin{bmatrix} 3 \amp 0\\ 0 \amp 1 \end{bmatrix} = A. \end{align*}
🔗
The rank-one reconstruction is
\begin{equation*} A_1 = 3\mathbf{e}_1\mathbf{e}_1^T = \begin{bmatrix} 3 \amp 0\\ 0 \amp 0 \end{bmatrix}. \end{equation*}
Therefore
\begin{align*} A \begin{bmatrix} a\\ b \end{bmatrix}\\ \amp = \begin{bmatrix} 3a\\ b \end{bmatrix},\\ A_1 \begin{bmatrix} a\\ b \end{bmatrix}\\ \amp = \begin{bmatrix} 3a\\ 0 \end{bmatrix}. \end{align*}
The rank-one reconstruction keeps the \(\mathbf{e}_1\) direction and discards the \(\mathbf{e}_2\) direction. The rank of \(A_1\) is \(1\text{.}\)
🔗
🔗
🔗

Note 6.5.2. Energy retained.

A common way to summarize how much of a matrix has been kept is to use squared singular values. The energy retained by the first \(k\) singular values is
\begin{equation*} \frac{\sigma_1^2+\cdots+\sigma_k^2} {\sigma_1^2+\cdots+\sigma_r^2}. \end{equation*}
This number is between \(0\) and \(1\text{.}\) Larger values mean that the rank-\(k\) reconstruction keeps more of the matrix’s dominant directions.
🔗
🔗

Activity 6.5.2. Choosing \(k\) from singular values.

Suppose the nonzero singular values of a matrix are
\begin{equation*} 10,\ 4,\ 1,\ 0.5,\ 0.1. \end{equation*}
🔗
  1. Compute the total squared singular-value energy.
    🔗
    🔗
  2. Compute the energy retained by \(k=1\text{.}\)
    🔗
    🔗
  3. Compute the energy retained by \(k=2\text{.}\)
    🔗
    🔗
  4. What is the smallest \(k\) that retains at least \(90\%\) of the energy?
    🔗
    🔗
Solution.
The squared singular values are
\begin{equation*} 100,\ 16,\ 1,\ 0.25,\ 0.01. \end{equation*}
The total squared energy is
\begin{equation*} 100+16+1+0.25+0.01=117.26. \end{equation*}
🔗
For \(k=1\text{,}\) the retained energy is
\begin{equation*} \frac{100}{117.26}\approx 0.853. \end{equation*}
For \(k=2\text{,}\) the retained energy is
\begin{equation*} \frac{100+16}{117.26} = \frac{116}{117.26} \approx 0.989. \end{equation*}
Thus \(k=2\) is the smallest value that retains at least \(90\%\) of the energy.
🔗
🔗
🔗

Note 6.5.3. Rank-\(k\) reconstruction in NumPy.

In NumPy, the singular values are returned as a one-dimensional array s. The diagonal matrix \(\Sigma_k\) is built from s[:k].
🔗
U, s, Vt = np.linalg.svd(A, full_matrices=False)
Ak = U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]
The matrix U[:, :k] keeps the first \(k\) left singular vectors. The matrix Vt[:k, :] keeps the first \(k\) rows of \(V^T\text{,}\) which correspond to the first \(k\) right singular vectors. The product Ak is the rank-\(k\) reconstruction.
🔗
For a quick reference on SVD commands, diagonal matrices, slices, and matrix multiplication, see the programming appendix sections B.10, B.8, B.3, and B.4.
🔗
🔗

Activity 6.5.3. Reading rank-\(k\) reconstruction code.

The following code computes a rank-one reconstruction of the diagonal stretch.
🔗
import numpy as np

A = np.array([[3., 0.],
              [0., 1.]])

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

k = 1
Ak = U[:, :k] @ np.diag(s[:k]) @ Vt[:k, :]

s, Ak
Output:
🔗
(array([3., 1.]),
 array([[3., 0.],
        [0., 0.]]))
  1. What are the singular values of \(A\text{?}\)
    🔗
    🔗
  2. Which singular value is kept when \(k=1\text{?}\)
    🔗
    🔗
  3. What is the matrix \(A_1\text{?}\)
    🔗
    🔗
  4. Which input direction does \(A_1\) discard?
    🔗
    🔗
  5. Why is Vt[:k, :] used instead of Vt[:, :k]?
    🔗
    🔗
Solution.
The singular values are \(3\) and \(1\text{.}\) When \(k=1\text{,}\) the reconstruction keeps only the singular value \(3\text{.}\) The reconstructed matrix is
\begin{equation*} A_1= \begin{bmatrix} 3 \amp 0\\ 0 \amp 0 \end{bmatrix}. \end{equation*}
It discards the second input direction. The slice Vt[:k, :] keeps the first \(k\) rows of \(V^T\text{,}\) which are the transposed right singular vectors used in the reconstruction. The slice Vt[:, :k] would keep columns of \(V^T\text{,}\) which is the wrong shape and the wrong mathematical object for this product.
🔗
🔗
🔗

Activity 6.5.4. Redundant features revisited by singular values.

Return to the redundant-feature matrix from Unit 2:
\begin{equation*} X= \begin{bmatrix} 1 \amp 2 \amp 3\\ 2 \amp 4 \amp 6\\ 0 \amp 1 \amp 1\\ 1 \amp -1 \amp 0 \end{bmatrix}. \end{equation*}
The third column is the sum of the first two columns.
🔗
The following code computes the singular values and the last row of \(V^T\text{.}\)
🔗
import numpy as np

np.set_printoptions(precision=3, suppress=True)

X = np.array([[1.,  2., 3.],
              [2.,  4., 6.],
              [0.,  1., 1.],
              [1., -1., 0.]])

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

s, Vt[-1, :]
Output:
🔗
(array([8.478, 1.459, 0.   ]),
 array([-0.577, -0.577,  0.577]))
  1. What does the zero singular value say about the rank of \(X\text{?}\)
    🔗
    🔗
  2. What null-space direction does the last row of \(V^T\) point along?
    🔗
    🔗
  3. How does this match the Unit 2 relation among the columns?
    🔗
    🔗
  4. If \(X\mathbf{c}=\mathbf{y}\text{,}\) what happens to \(X(\mathbf{c}+t\mathbf{z})\text{,}\) where
    \begin{equation*} \mathbf{z}= \begin{bmatrix} 1\\ 1\\ -1 \end{bmatrix}? \end{equation*}
    🔗
    🔗
Solution.
The zero singular value says that the three columns of \(X\) contain only two independent directions, so
\begin{equation*} \operatorname{rank}(X)=2. \end{equation*}
The last row of \(V^T\) is approximately
\begin{equation*} \begin{bmatrix} -0.577 \amp -0.577 \amp 0.577 \end{bmatrix}, \end{equation*}
which points in the same direction as
\begin{equation*} -\frac{1}{\sqrt3} \begin{bmatrix} 1\\ 1\\ -1 \end{bmatrix}. \end{equation*}
🔗
This matches the Unit 2 relation
\begin{equation*} \text{column }1+\text{column }2-\text{column }3=\mathbf{0}, \end{equation*}
or
\begin{equation*} X \begin{bmatrix} 1\\ 1\\ -1 \end{bmatrix} = \mathbf{0}. \end{equation*}
Therefore, if \(X\mathbf{c}=\mathbf{y}\text{,}\) then
\begin{align*} X(\mathbf{c}+t\mathbf{z})\\ \amp = X\mathbf{c}+tX\mathbf{z}\\ \amp = \mathbf{y}. \end{align*}
The null direction gives different coefficient vectors with the same output.
🔗
🔗
🔗

Note 6.5.4. Low-rank updates.

A low-rank update changes a large matrix by adding a product
\begin{equation*} BC, \end{equation*}
where
\begin{equation*} B\in\mathbb R^{m\times r}, \qquad C\in\mathbb R^{r\times n}, \end{equation*}
and \(r\) is small. Since
\begin{equation*} \operatorname{rank}(BC)\leq r, \end{equation*}
the update \(BC\) changes the matrix through at most \(r\) independent directions.
🔗
This is useful when a full \(m\times n\) matrix would be expensive to store or change. The matrix \(BC\) can be stored using
\begin{equation*} mr+rn \end{equation*}
numbers instead of \(mn\) numbers.
🔗
In model-adaptation settings, \(W\) may be a large existing weight matrix and \(BC\) may represent a small trainable update. The linear-algebra point is independent of that application: the update \(BC\) has rank at most \(r\) and can be stored using many fewer numbers than a full \(m\times n\) matrix.
🔗
🔗

Activity 6.5.5. Rank of an update.

Let
\begin{equation*} W\in\mathbb R^{1000\times 800}, \qquad B\in\mathbb R^{1000\times 4}, \qquad C\in\mathbb R^{4\times 800}. \end{equation*}
Define
\begin{equation*} W_{\text{new}}=W+BC. \end{equation*}
🔗
  1. What is the shape of \(BC\text{?}\)
    🔗
    🔗
  2. What is the largest possible rank of \(BC\text{?}\)
    🔗
    🔗
  3. How many numbers are needed to store \(W\text{?}\)
    🔗
    🔗
  4. How many numbers are needed to store \(B\) and \(C\text{?}\)
    🔗
    🔗
  5. Why is \(BC\) called a low-rank update?
    🔗
    🔗
Solution.
The product \(BC\) has shape
\begin{equation*} 1000\times 800, \end{equation*}
so it can be added to \(W\text{.}\)
🔗
The rank of a product is at most the inner dimension, so
\begin{equation*} \operatorname{rank}(BC)\leq 4. \end{equation*}
The full matrix \(W\) stores
\begin{equation*} 1000\cdot 800=800000 \end{equation*}
numbers. The two update matrices store
\begin{equation*} 1000\cdot 4+4\cdot 800=4000+3200=7200 \end{equation*}
numbers.
🔗
The update is called low-rank because the change \(BC\) has rank at most \(4\text{,}\) even though it has the same shape as \(W\text{.}\)
🔗
🔗
🔗

Warning 6.5.5. Low-rank update versus low-rank matrix.

A low-rank update does not mean that the whole matrix
\begin{equation*} W_{\text{new}}=W+BC \end{equation*}
has low rank. The update \(BC\) has rank at most \(r\text{.}\) The matrix \(W+BC\) may still have large rank.
🔗
🔗
🔗
PrevTopNext