Low-rank approximation

Keep the biggest pieces

Lesson 3.8.1 wrote every matrix as a sum of rank-one pieces, largest first:

Here $\sigma_1 \ge \sigma_2 \ge \cdots$ are the singular values, $\mathbf{u}_i$ and $\mathbf{v}_i$ the left and right singular vectors, and $r$ the rank. Keep only the first $k$ pieces and you get a matrix of rank $k$ that is close to $A$.

Lesson 3.8.1's tall matrix has two pieces:

$B_1 = \sqrt 6\,\mathbf{u}_1\mathbf{v}_1^\top$ is the first piece, and the error $B - B_1$ is the piece left out, $2\mathbf{u}_2\mathbf{v}_2^\top$. To say how good $B_1$ is, we need a way to measure the size of a matrix.

The size of a matrix

The Frobenius norm. Read the entries of $A$ as one long vector and take its length (lesson 3.1.2): the square root of the sum of the squares of all the entries. It is written $\lVert A \rVert_F$.

For $B$ the squares are $4, 0, 1, 1, 0, 4$, which add up to 10, so $\lVert B \rVert_F = \sqrt{10} \approx 3.1623$. That is also $\sqrt{\sigma_1^2 + \sigma_2^2} = \sqrt{6 + 4}$. The turns $U$ and $V^\top$ keep lengths, so only the stretches in $S$ count.

The 2-norm. The largest stretch: the longest $\lVert A\mathbf{x} \rVert$ for a unit vector $\mathbf{x}$, written $\lVert A \rVert_2$. Lesson 3.8.1 found it is the longest semi-axis of the ellipse, $\sigma_1$. For $B$ it is $\sqrt 6 \approx 2.4495$.

The best copy, and its error

No matrix of rank $k$ is closer to $A$ than $A_k$, in either norm. This result is the Eckart–Young theorem, stated here without proof. The error is made of the pieces left out, so its size comes straight from the singular values.

For $B_1$ only $\sigma_2 = 2$ is left out, so both errors are 2. The cell above agrees: the four entries $\pm 1$ of $B - B_1$ give $\sqrt 4 = 2$.

Other rank-1 copies do worse. Keeping only the first column of $B$, $\begin{pmatrix} 2 & 0 \\ 1 & 0 \\ 0 & 0 \end{pmatrix}$, leaves an error of $\sqrt 5 \approx 2.2361$. Even $1.1$ times the table of ones, a small change to $B_1$, leaves 2.0149.

The share kept

The squared Frobenius norm splits exactly between the copy and the error, like the two sides of a right angle: $\lVert A \rVert_F^2 = \lVert A_k \rVert_F^2 + \lVert A - A_k \rVert_F^2$. For $B$, $10 = 6 + 4$. So the copy keeps a share of the squared size.

$B_1$ keeps $6/10 = 60\%$ of the squared size of $B$. Its relative error is $\sqrt{0.4} \approx 0.6325$, which is $2 / \sqrt{10}$.

A larger example: choosing k

Here is a $5 \times 4$ matrix of whole numbers. Its rows run from falling, $(6, 4, 2, 1)$, through flat to rising, $(0, 1, 2, 5)$:

Its singular values are 10.876, 6.016, 0.649 and 0.320, and the squares of its entries add up to 155. The squares of the singular values add up to 155 too: 118.28, 36.19, 0.42 and 0.10.

The rank-2 copy $M_2$ differs from $M$ by at most 0.34 in any entry. Its first row, for example, is $(5.87, 4.07, 2.27, 0.87)$ against $(6, 4, 2, 1)$.

The two pieces it keeps have a meaning: $\mathbf{v}_1 \approx (0.63, 0.50, 0.40, 0.44)$ has every entry positive, a common level. $\mathbf{v}_2 \approx (-0.52, -0.21, 0.18, 0.81)$ runs from negative to positive: a tilt from the first column to the last. Each row of $M$ is close to some amount of the level plus some amount of the tilt.

How to choose k

• A target share. Pick the smallest $k$ whose share reaches a target, such as 90% or 99%. Here 90% needs $k = 2$, and so does 99%.
• A gap. Look for a sharp drop in the singular values. From 6.016 to 0.649 is a fall by a factor of more than 9, so $k = 2$.
• What the small pieces are. If the entries carry measurement or rounding errors, the smallest pieces are often just those errors. Dropping them can make the copy closer to the truth, not further from it.

The choice is a judgement, and the error rules say what it costs. With $k = 2$ the worst direction is off by $\sigma_3 = 0.6488$.

Storage

A rank-$k$ copy of an $m \times n$ matrix is stored as $U_k$, $S_k$ and $V_k^\top$: $k(m + n + 1)$ numbers instead of $mn$.

For $M$ that is no saving: $2 \times (5 + 4 + 1) = 20$, the same as its 20 entries. The saving comes with size. A $1{,}000 \times 500$ matrix holds 500,000 numbers, and a rank-10 copy needs 15,010, about 3%.

Cases to know

• $k = 0$ keeps nothing: $A_0$ is the zero matrix and the error is all of $A$.
• $k$ equal to the rank keeps everything. The table $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 3 & 6 & 9 \end{pmatrix}$ has singular values 14, 0 and 0, so $A_1$ is the table itself, stored as 7 numbers instead of 9.
• Ties. If $\sigma_k = \sigma_{k+1}$, the best copy is not unique. The identity $I_2$ has singular values 1 and 1, and every direction gives an equally good rank-1 copy.
• Scaling. Multiplying $A$ by $c$ multiplies every singular value by $\lvert c \rvert$. The errors scale too, but the shares do not change: $-3M$ keeps 76.31% at $k = 1$, like $M$.

Case study 3.8.4 uses this to compress a table of asset returns into a few factors.

Common mistakes

1. Shares use squares. The share kept is $\sum \sigma_i^2$ over the top $k$ against the total. For $M$, $\sigma_1 / \sum \sigma_i$ is 60.89%, but the true share is 76.31%.
2. The 2-norm error is the first value left out, $\sigma_{k+1}$, not the last one kept, $\sigma_k$.
3. The Frobenius error is a root of a sum of squares, not the sum of the singular values left out.
4. Keep matching parts. Take the first $k$ columns of $U$, the first $k$ singular values and the first $k$ rows of $V^\top$.
5. Low rank is not small entries. Setting the smallest entries of $A$ to 0, or dropping a row or column, does not give the best copy: keeping $B$'s first column leaves 2.2361 against 2.
6. Small matrices save nothing. $k(m + n + 1)$ can equal or pass $mn$.