Dimension reduction

7.5. Dimension reduction#

The SVD has another important property that proves very useful in a variety of applications. Let $A$ be a real $m \times n$ matrix with SVD $A = U S V^{T}$ and (momentarily) $m \geq n$ . Another way of writing the thin form of the SVD is

(7.5.1)#

\begin{array}{r} \begin{aligned} A = \hat{U} \hat{S} V^{T} & = [\begin{array}{c} u_{1} & u_{2} & \dots & u_{n} \end{array}] [\begin{array}{c} σ_{1} \\ ⋱ \\ σ_{n} \end{array}] [\begin{array}{c} v_{1}^{T} \\ ⋮ \\ v_{n}^{T} \end{array}] \\ = [\begin{array}{c} σ_{1} u_{1} & \dots & σ_{n} u_{n} \end{array}] [\begin{array}{c} v_{1}^{T} \\ ⋮ \\ v_{n}^{T} \end{array}] \\ = σ_{1} u_{1} v_{1}^{T} + \dots + σ_{r} u_{r} v_{r}^{T} = \sum_{i = 1}^{r} σ_{i} u_{i} v_{i}^{T}, \end{aligned} \end{array}

where $r$ is the rank of $A$ . The final formula also holds for the case $m < n$ .

Each outer product $u_{i} v_{i}^{T}$ is a rank-1 matrix of unit 2-norm. Thanks to the ordering of singular values, then, Equation (7.5.1) expresses $A$ as a sum of decreasingly important contributions. This motivates the definition, for $1 \leq k \leq r$ ,

(7.5.2)#

A_{k} = \sum_{i = 1}^{k} σ_{i} u_{i} v_{i}^{T} = U_{k} S_{k} V_{k}^{T},

where $U_{k}$ and $V_{k}$ are the first $k$ columns of $U$ and $V$ , respectively, and $S_{k}$ is the upper-left $k \times k$ submatrix of $S$ .

The rank of a sum of matrices is always less than or equal to the sum of the ranks, so $A_{k}$ is a rank- $k$ approximation to $A$ . It turns out that $A_{k}$ is the best rank- $k$ approximation of $A$ , as measured in the matrix 2-norm.

Theorem 7.5.1

Suppose $A$ has rank $r$ and let $A = U S V^{T}$ be an SVD. Let $A_{k}$ be as in (7.5.2) for $1 \leq k < r$ . Then

$‖ A - A_{k} ‖_{2} = σ_{k + 1}, k = 1, \dots, r - 1$ , and
If the rank of $B$ is $k$ or less, then $‖ A - B ‖_{2} \geq σ_{k + 1}$ .

Proof

(part 1 only) Note that (7.5.2) is identical to (7.5.1) with $σ_{k + 1}, \dots, σ_{r}$ all set to zero. This implies that

A - A_{k} = U (S - \hat{S}) V^{T},

where $\hat{S}$ has those same values of $σ_{i}$ replaced by zero. But that makes the above an SVD of $A - A_{k}$ , with singular values $0, \dots, 0, σ_{k + 1}, \dots, σ_{r}$ , the largest of which is $σ_{k + 1}$ . That proves the first claim.

Compression#

If the singular values of $A$ decrease sufficiently rapidly, then $A_{k}$ may capture the most significant behavior of the matrix for a reasonably small value of $k$ .

Demo 7.5.2

We make an image from some text, then reload it as a matrix.

Next we show that the singular values decrease until they reach zero (more precisely, until they are about $ϵ_{mach}$ times the norm of the matrix) at around $k = 45$ .

U,σ,V = svd(A)
scatter(σ,xaxis=(L"i"), yaxis=(:log10,L"\sigma_i"),
    title="Singular values")

The rapid decrease suggests that we can get fairly good low-rank approximations.

plt = plot(layout=(2,2),frame=:none,aspect_ratio=1,titlefontsize=10)
for i in 1:4
    k = 3i
    Ak = U[:,1:k]*diagm(σ[1:k])*V[:,1:k]'
    plot!(Gray.(Ak),subplot=i,title="rank = $k")
end
plt

Consider how little data is needed to reconstruct these images. For rank-9, for instance, we have 9 left and right singular vectors plus 9 singular values, for a compression ratio of better than 12:1.

m,n = size(A)
compression = m*n / (9*(m+n+1))

12.099213551119178

Capturing major trends#

The use of dimension reduction offered by low-rank SVD approximation goes well beyond simply reducing computation time. By isolating the most important contributions to the matrix, dimension reduction can uncover deep connections and trends that are otherwise obscured by weaker effects and noise.

One useful way to quantify the decay in the singular values is to compute

(7.5.3)#

s_{k} = \sum_{i = 1}^{k} σ_{i}^{2}, τ_{k} = \frac{s_{k}}{s_{r}}, k = 1, \dots, r .

Clearly $0 \leq τ_{k} \leq 1$ and $τ_{k}$ is non-decreasing as a function of $k$ . We can think of $τ_{k}$ as the fraction of energy (or in statistical terms, variance) contained in the singular values up to and including the $k$ th.1

Demo 7.5.3

This matrix describes the votes on bills in the 111th session of the United States Senate. (The data set was obtained from [https://voteview.com].) Each row is one senator, and each column is a vote item.

@load "voting.jld2" A;

If we visualize the votes (yellow is “yea,” blue is “nay”), we can see great similarity between many rows, reflecting party unity.

heatmap(A,color=:viridis,
    title="Votes in 111th U.S. Senate",xlabel="bill",ylabel="senator")

We use (7.5.3) to quantify the decay rate of the values.

U,σ,V = svd(A)
τ = cumsum(σ.^2) / sum(σ.^2)
scatter(τ[1:16], xaxis=("k"), yaxis=(L"\tau_k"), 
    title="Fraction of singular value energy")

The first and second singular triples contain about 58% and 17%, respectively, of the energy of the matrix. All others have far less effect, suggesting that the information is primarily two-dimensional. The first left and right singular vectors also contain interesting structure.

Both vectors have values greatly clustered near $\pm C$ for a constant $C$ . These can be roughly interpreted as how partisan a particular senator or bill was, and for which political party. Projecting the senators’ vectors into the first two $V$ -coordinates gives a particularly nice way to reduce them to two dimensions. Political scientists label these dimensions partisanship and bipartisanship. Here we color them by actual party affiliation (also given in the data file): red for Republican, blue for Democrat, and yellow for independent.

Not all data sets can be reduced effectively to a small number of dimensions, but as Demo 7.5.3 illustrates, in some cases reduction reveals information that corresponds to real-world understanding.

Exercises#

✍ Suppose that $A$ is an $n \times n$ matrix. Explain why $σ_{n}$ is the distance (in 2-norm) from $A$ to the set of all singular matrices.
✍ Suppose $A$ is a $7 \times 4$ matrix and the eigenvalues of $A^{*} A$ are 3, 4, 7, and 10. How close is $A$ in the 2-norm to (a) a rank-3 matrix? (b) a rank-2 matrix?
(a) ⌨ Find the rank-1 matrix closest to

$\begin{array}{r} A = [\begin{array}{c} 1 & 5 \\ 5 & 1 \end{array}], \end{array}$

as measured in the 2-norm.

(b) ⌨ Repeat part (a) for

$\begin{array}{r} A = [\begin{array}{c} 1 & 5 \\ 0 & 1 \end{array}] . \end{array}$
✍ Find the rank-1 matrix closest to

$\begin{array}{r} A = [\begin{array}{c} 1 & b \\ b & 1 \end{array}], \end{array}$

as measured in the 2-norm, where $b > 0$ .
⌨ Following Demo 7.5.2 as a guide, load the “mandrill” test image and convert it to a matrix of floating-point pixel grayscale intensities. Using the SVD, display as images the best approximations of rank 5, 10, 15, and 20.

1: In statistics this quantity may be interpreted as the fraction of explained variance.

Dimension reduction

Contents

7.5. Dimension reduction#

Compression#

Capturing major trends#

Exercises#