Using Singular Value Decompositions

Section 7.5 Using Singular Value Decompositions

We’ve now seen what singular value decompositions are, how to construct them, and how they provide important information about a matrix such as orthonormal bases for the four fundamental subspaces. This puts us in a good position to begin using singular value decompositions to solve a wide variety of problems.

🔗

Given the fact that singular value decompositions so immediately convey fundamental data about a matrix, it seems natural that some of our previous work can be reinterpreted in terms of singular value decompositions. Therefore, we’ll take some time in this section to revisit some familiar issues, such as least-squares problems and principal component analysis, while also looking at some new applications.

🔗

Preview Activity 7.5.1.

Suppose that

A = U Σ V^{T}

where

Σ = [\begin{matrix} 13 & 0 & 0 & 0 \\ 0 & 8 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{matrix}],

vectors

u_{j}

form the columns of

U,

and vectors

v_{j}

form the columns of

V .

What are the shapes of the matrices $A,$ $U,$ and $V ?$
🔗

🔗
What is the rank of $A ?$
🔗

🔗
Describe how to find an orthonormal basis for $Col (A) .$
🔗

🔗
Describe how to find an orthonormal basis for $Nul (A) .$
🔗

🔗
If the columns of $Q$ form an orthonormal basis for $Col (A),$ what is $Q^{T} Q ?$
🔗

🔗
How would you form a matrix that projects vectors orthogonally onto $Col (A) ?$
🔗

🔗

🔗

Subsection 7.5.1 Least-squares problems

Least-squares problems, which we explored in Section 6.5, arise when we are confronted with an inconsistent linear system

A x = b .

Since there is no solution to the system, we instead find the vector

x

minimizing the distance between

b

and

A x .

That is, we find the vector

\hat{x},

the least-squares approximate solution, by solving

A \hat{x} = \hat{b}

where

\hat{b}

is the orthogonal projection of

b

onto the column space of

A .

🔗

If we have a singular value decomposition

A = U Σ V^{T},

then the number of nonzero singular values

r

tells us the rank of

A,

and the first

r

columns of

U

form an orthonormal basis for

Col (A) .

This basis may be used to project vectors onto

Col (A)

and hence to solve least-squares problems.

🔗

Before exploring this connection further, we will introduce Sage as a tool for automating the construction of singular value decompositions. One new feature is that we need to declare our matrix to consist of floating point entries. We do this by including RDF inside the matrix definition, as illustrated in the following cell.

xxxxxxxxxx
 
A = matrix(RDF, 3, 2, [1,0,-1,1,1,1])
U, Sigma, V = A.SVD()     
print(U)
print('---------')
print(Sigma)
print('---------')
print(V)

🔗

Activity 7.5.2.

Consider the equation

A x = b

where

[\begin{matrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{matrix}] x = [\begin{array}{r} - 1 \\ 3 \\ 6 \end{array}]

Find a singular value decomposition for $A$ using the Sage cell below. What are singular values of $A ?$
xxxxxxxxxx
Language:
Messages
🔗
🔗
What is $r,$ the rank of $A ?$ How can we identify an orthonormal basis for $Col (A) ?$
🔗

🔗
Form the reduced singular value decomposition $U_{r} Σ_{r} V_{r}^{T}$ by constructing: the matrix $U_{r},$ consisting of the first $r$ columns of $U;$ the matrix $V_{r},$ consisting of the first $r$ columns of $V;$ and $Σ_{r},$ a square $r \times r$ diagonal matrix. Verify that $A = U_{r} Σ_{r} V_{r}^{T} .$
🔗
You may find it convenient to remember that if B is a matrix defined in Sage, then B.matrix_from_columns( list ) and B.matrix_from_rows( list ) can be used to extract columns or rows from B. For instance, B.matrix_from_rows([0,1,2]) provides a matrix formed from the first three rows of B.
xxxxxxxxxx
Language:
Messages
🔗
🔗
How does the reduced singular value decomposition provide a matrix whose columns are an orthonormal basis for $Col (A) ?$
🔗

🔗
Explain why a least-squares approximate solution $\hat{x}$ satisfies

$A \hat{x} = U_{r} U_{r}^{T} b .$

🔗

🔗
What is the product $V_{r} V_{r}^{T}$ and why does it have this form?
🔗

🔗
Explain why

$\hat{x} = V_{r} Σ_{r}^{- 1} U_{r}^{T} b$
is the least-squares approximate solution, and use this expression to find $\hat{x} .$
xxxxxxxxxx

Language:
Messages
🔗
🔗

🔗

This activity demonstrates the power of a singular value decomposition to find a least-squares approximate solution for an equation

A x = b .

Because it immediately provides an orthonormal basis for

Col (A),

something that we’ve had to construct using the Gram-Schmidt process in the past, we can easily project

b

onto

Col (A),

which results in a simple expression for

\hat{x} .

🔗

Proposition 7.5.1.

A = U_{r} Σ_{r} V_{r}^{T}

is a reduced singular value decomposition of

A,

then a least-squares approximate solution to

A x = b

is given by

\hat{x} = V_{r} Σ_{r}^{- 1} U_{r}^{T} b .

🔗

If the columns of

A

are linearly independent, then the equation

A \hat{x} = \hat{b}

has only one solution so there is a unique least-squares approximate solution

\hat{x} .

Otherwise, the expression in Proposition 7.5.1 produces the solution to

A \hat{x} = \hat{b}

having the shortest length.

🔗

The matrix

A^{+} = V_{r} Σ_{r}^{- 1} U_{r}^{T}

is known as the Moore-Penrose psuedoinverse of

A .

When

A

is invertible,

A^{- 1} = A^{+} .

🔗

Subsection 7.5.2 Rank $k$ approximations

If we have a singular value decomposition for a matrix

A,

we can form a sequence of matrices

A_{k}

that approximate

A

with increasing accuracy. This may feel familiar to calculus students who have seen the way in which a function

f (x)

can be approximated by a linear function, a quadratic function, and so forth with increasing accuracy.

🔗

We’ll begin with a singular value decomposition of a rank

r

matrix

A

so that

A = U Σ V^{T} .

To create the approximating matrix

A_{k},

we keep the first

k

singular values and set the others to zero. For instance, if

Σ = [\begin{matrix} 22 & 0 & 0 & 0 & 0 \\ 0 & 14 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}],

we can form matrices

Σ^{(1)} = [\begin{matrix} 22 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}], Σ^{(2)} = [\begin{matrix} 22 & 0 & 0 & 0 & 0 \\ 0 & 14 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix}]

and define

A_{1} = U Σ^{(1)} V^{T}

and

A_{2} = U Σ^{(2)} V^{T} .

Because

A_{k}

has

k

nonzero singular values, we know that

rank (A_{k}) = k .

In fact, there is a sense in which

A_{k}

is the closest matrix to

A

among all rank

k

matrices.

🔗

Activity 7.5.3.

Let’s consider a matrix

A = U Σ V^{T}

where

\begin{aligned} U = [\begin{array}{c} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & - \frac{1}{2} & - \frac{1}{2} \\ \frac{1}{2} & - \frac{1}{2} & \frac{1}{2} & - \frac{1}{2} \\ \frac{1}{2} & - \frac{1}{2} & - \frac{1}{2} & \frac{1}{2} \end{array}], Σ = [\begin{array}{c} 500 & 0 & 0 & 0 \\ 0 & 100 & 0 & 0 \\ 0 & 0 & 20 & 0 \\ 0 & 0 & 0 & 4 \end{array}] \\ V = [\begin{array}{c} \frac{1}{2} & \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & - \frac{1}{2} & - \frac{1}{2} & \frac{1}{2} \\ - \frac{1}{2} & - \frac{1}{2} & \frac{1}{2} & \frac{1}{2} \\ - \frac{1}{2} & \frac{1}{2} & - \frac{1}{2} & \frac{1}{2} \end{array}] \end{aligned}

Evaluating the following cell will create the matrices U, V, and Sigma. Notice how the diagonal_matrix command provides a convenient way to form the diagonal matrix

Σ .

xxxxxxxxxx
 
h = 1/2
U = matrix(4,4,[h,h,h,h,  h,h,-h,-h,  h,-h,h,-h,  h,-h,-h,h])       
V = matrix(4,4,[h,h,h,h,  h,-h,-h,h,  -h,-h,h,h,  -h,h,-h,h])
Sigma = diagonal_matrix([500, 100, 20, 4])

Form the matrix $A = U Σ V^{T} .$ What is $rank (A) ?$
xxxxxxxxxx
Language:
Messages
🔗
🔗
Now form the approximating matrix $A_{1} = U Σ^{(1)} V^{T} .$ What is $rank (A_{1}) ?$
xxxxxxxxxx
Language:
Messages
🔗
🔗
Find the error in the approximation $A \approx A_{1}$ by finding $A - A_{1} .$
🔗

🔗
Now find $A_{2} = U Σ^{(2)} V^{T}$ and the error $A - A_{2} .$ What is $rank (A_{2}) ?$
xxxxxxxxxx
Language:
Messages
🔗
🔗
Find $A_{3} = U Σ^{(3)} V^{T}$ and the error $A - A_{3} .$ What is $rank (A_{3}) ?$
🔗

🔗
What would happen if we were to compute $A_{4} ?$
🔗

🔗
What do you notice about the error $A - A_{k}$ as $k$ increases?
🔗

🔗

🔗

In this activity, the approximating matrix

A_{k}

has rank

k

because its singular value decomposition has

k

nonzero singular values. We then saw how the difference between

A

and the approximations

A_{k}

decreases as

k

increases, which means that the sequence

A_{k}

forms better approximations as

k

increases.

🔗

Another way to represent

A_{k}

is with a reduced singular value decomposition so that

A_{k} = U_{k} Σ_{k} V_{k}^{T}

where

U_{k} = [\begin{matrix} u_{1} & \dots & u_{k} \end{matrix}], Σ_{k} = [\begin{matrix} σ_{1} & 0 & \dots & 0 \\ 0 & σ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & σ_{k} \end{matrix}], V_{k} = [\begin{matrix} v_{1} & \dots & v_{k} \end{matrix}] .

Notice that the rank

1

matrix

A_{1}

then has the form

A_{1} = u_{1} [\begin{matrix} σ_{1} \end{matrix}] v_{1}^{T} = σ_{1} u_{1} v_{1}^{T}

and that we can similarly write:

\begin{aligned} A \approx A_{1} & = σ_{1} u_{1} v_{1}^{T} \\ A \approx A_{2} & = σ_{1} u_{1} v_{1}^{T} + σ_{2} u_{2} v_{2}^{T} \\ A \approx A_{3} & = σ_{1} u_{1} v_{1}^{T} + σ_{2} u_{2} v_{2}^{T} + σ_{3} u_{3} v_{3}^{T} \\ ⋮ \\ A = A_{r} & = σ_{1} u_{1} v_{1}^{T} + σ_{2} u_{2} v_{2}^{T} + σ_{3} u_{3} v_{3}^{T} + \dots + σ_{r} u_{r} v_{r}^{T} . \end{aligned}

🔗

Given two vectors

u

and

v,

the matrix

u v^{T}

is called the outer product of

u

and

v .

(The dot product

u \cdot v = u^{T} v

is sometimes called the inner product.) An outer product will always be a rank

1

matrix so we see above how

A_{k}

is obtained by adding together

k

rank

1

matrices, each of which gets us one step closer to the original matrix

A .

🔗

Subsection 7.5.3 Principal component analysis

In Section 7.3, we explored principal component analysis as a technique to reduce the dimension of a dataset. In particular, we constructed the covariance matrix

C

from a demeaned data matrix and saw that the eigenvalues and eigenvectors of

C

tell us about the variance of the dataset in different directions. We referred to the eigenvectors of

C

as principal components and found that projecting the data onto a subspace defined by the first few principal components frequently gave us a way to visualize the dataset. As we added more principal components, we retained more information about the original dataset. This feels similar to the rank

k

approximations we have just seen so let’s explore the connection.

🔗

Suppose that we have a dataset with

N

points, that

A

represents the demeaned data matrix, that

A = U Σ V^{T}

is a singular value decomposition, and that the singular values are

A

are denoted as

σ_{i} .

It follows that the covariance matrix

C = \frac{1}{N} A A^{T} = \frac{1}{N} (U Σ V^{T}) (U Σ V^{T})^{T} = U (\frac{1}{N} Σ Σ^{T}) U^{T} .

Notice that

\frac{1}{N} Σ Σ^{T}

is a diagonal matrix whose diagonal entries are

\frac{1}{N} σ_{i}^{2} .

Therefore, it follows that

C = U (\frac{1}{N} Σ Σ^{T}) U^{T}

is an orthogonal diagonalization of

C

showing that

the principal components of the dataset, which are the eigenvectors of $C,$ are given by the columns of $U .$ In other words, the left singular vectors of $A$ are the principal components of the dataset.
🔗

🔗
the variance in the direction of a principal component is the associated eigenvalue of $C$ and therefore

$V_{u_{i}} = \frac{1}{N} σ_{i}^{2} .$

🔗

🔗

🔗

Activity 7.5.4.

Let’s revisit the iris dataset that we studied in Section 7.3. Remember that there are four measurements given for each of 150 irises and that each iris belongs to one of three species.

🔗

Evaluating the following cell will load the dataset and define the demeaned data matrix

A

whose shape is

4 \times 150 .

xxxxxxxxxx
 
sage.repl.load.load('https://raw.githubusercontent.com/davidaustinm/ula_modules/master/pca_iris.py', globals())
df.T

Find the singular values of $A$ using the command A.singular_values() and use them to determine the variance $V_{u_{j}}$ in the direction of each of the four principal components. What is the fraction of variance retained by the first two principal components?
xxxxxxxxxx
Language:
Messages
🔗
🔗
We will now write the matrix $Γ = Σ V^{T}$ so that $A = U Γ .$ Suppose that a demeaned data point, say, the 100th column of $A,$ is written as a linear combination of principal components:

$x = c_{1} u_{1} + c_{2} u_{2} + c_{3} u_{3} + c_{4} u_{4} .$

Explain why $[\begin{array}{r} c_{1} \\ c_{2} \\ c_{3} \\ c_{4} \end{array}],$ the vector of coordinates of $x$ in the basis of principal components, appears as 100th column of $Γ .$

🔗

🔗
Suppose that we now project this demeaned data point $x$ orthogonally onto the subspace spanned by the first two principal components $u_{1}$ and $u_{2} .$ What are the coordinates of the projected point in this basis and how can we find them in the matrix $Γ ?$
🔗

🔗
Alternatively, consider the approximation $A_{2} = U_{2} Σ_{2} V_{2}^{T}$ of the demeaned data matrix $A .$ Explain why the 100th column of $A_{2}$ represents the projection of $x$ onto the two-dimensional subspace spanned by the first two principal components, $u_{1}$ and $u_{2} .$ Then explain why the coefficients in that projection, $c_{1} u_{1} + c_{2} u_{2},$ form the two-dimensional vector $[\begin{array}{r} c_{1} \\ c_{2} \end{array}]$ that is the 100th column of $Γ_{2} = Σ_{2} V_{2}^{T} .$
🔗

🔗
Now we’ve seen that the columns of $Γ_{2} = Σ_{2} V_{2}^{T}$ form the coordinates of the demeaned data points projected on to the two-dimensional subspace spanned by $u_{1}$ and $u_{2} .$ In the cell below, find a singular value decomposition of $A$ and use it to form the matrix Gamma2. When you evaluate this cell, you will see a plot of the projected demeaned data plots, similar to the one we created in Section 7.3.
xxxxxxxxxx

# Form the SVD of A and use it to form Gamma2

Gamma2 =

# The following will plot the projected demeaned data points
data = Gamma2.columns()
(list_plot(data[:50], color='blue', aspect_ratio=1) +
list_plot(data[50:100], color='orange') +
list_plot(data[100:], color='green'))
Language:
Messages
🔗
🔗

🔗

In our first encounter with principal component analysis, we began with a demeaned data matrix

A,

formed the covariance matrix

C,

and used the eigenvalues and eigenvectors of

C

to project the demeaned data onto a smaller dimensional subspace. In this section, we have seen that a singular value decomposition of

A

provides a more direct route: the left singular vectors of

A

form the principal components and the approximating matrix

A_{k}

represents the data points projected onto the subspace spanned by the first

k

principal components. The coordinates of a projected demeaned data point are given by the columns of

Γ_{k} = Σ_{k} V_{k}^{T} .

🔗

Subsection 7.5.4 Image compressing and denoising

In addition to principal component analysis, the approximations

A_{k}

of a matrix

A

obtained from a singular value decomposition can be used in image processing. Remember that we studied the JPEG compression algorithm, whose foundation is the change of basis defined by the Discrete Cosine Transform, in Section 3.3. We will now see how a singular value decomposition provides another tool for both compressing images and removing noise in them.

🔗

Activity 7.5.5.

Evaluating the following cell loads some data that we’ll use in this activity. To begin, it defines and displays a

25 \times 15

matrix

A .

xxxxxxxxxx
 
sage.repl.load.load('https://raw.githubusercontent.com/davidaustinm/ula_modules/master/svd_compress.py', globals())
print(A)

If we interpret 0 as black and 1 as white, this matrix represents an image as shown below.
xxxxxxxxxx

display_matrix(A)

Language:
Messages
We will explore how the singular value decomposition helps us to compress this image.
1. By inspecting the image represented by $A,$ identify a basis for $Col (A)$ and determine $rank (A) .$
  🔗
  
  🔗
2. The following cell plots the singular values of $A .$ Explain how this plot verifies that the rank is what you found in the previous part.
  xxxxxxxxxx
  
  plot_sv(A)
  
  Language:
  
  Messages
  🔗
  🔗
3. There is a command approximate(A, k) that creates the approximation $A_{k} .$ Use the cell below to define $k$ and look at the images represented by the first few approximations. What is the smallest value of $k$ for which $A = A_{k} ?$
  xxxxxxxxxx
  
  k =
  display_matrix(approximate(A, k))
  
  Language:
  
  Messages
  🔗
  🔗
4. Now we can see how the singular value decomposition allows us to compress images. Since this is a $25 \times 15$ matrix, we need $25 \cdot 15 = 375$ numbers to represent the image. However, we can also reconstruct the image using a small number of singular values and vectors:
  
  $A = A_{k} = σ_{1} u_{1} v_{1}^{T} + σ_{2} u_{2} v_{2}^{T} + \dots + σ_{k} u_{k} v_{k}^{T} .$
  
  What are the dimensions of the singular vectors $u_{i}$ and $v_{i} ?$ Between the singular vectors and singular values, how many numbers do we need to reconstruct $A_{k}$ for the smallest $k$ for which $A = A_{k} ?$ This is the compressed size of the image.
  
  🔗
  
  🔗
5. The compression ratio is the ratio of the uncompressed size to the compressed size. What compression ratio does this represent?
  🔗
  
  🔗
🔗
🔗
Next we’ll explore an example based on a photograph.
1. Consider the following image consisting of an array of $316 \times 310$ pixels stored in the matrix $A .$
  xxxxxxxxxx
  
  A = matrix(RDF, image)
  display_image(A)
  
  Language:
  
  Messages
  🔗
  Plot the singular values of $A .$
  xxxxxxxxxx
  
  plot_sv(A)
  
  Language:
  
  Messages
  🔗
  🔗
2. Use the cell below to study the approximations $A_{k}$ for $k = 1, 10, 20, 50, 100 .$
  xxxxxxxxxx
  
  k = 1
  display_image(approximate(A, k))
  
  Language:
  
  Messages
  Notice how the approximating image $A_{k}$ more closely approximates the original image $A$ as $k$ increases.
  🔗
  What is the compression ratio when $k = 50 ?$ What is the compression ratio when $k = 100 ?$ Notice how a higher compression ratio leads to a lower quality reconstruction of the image.
  🔗
  
  🔗
🔗
🔗
A second, related application of the singular value decomposition to image processing is called denoising. For example, consider the image represented by the matrix $A$ below.
xxxxxxxxxx

A = matrix(RDF, noise.values)
display_matrix(A)

Language:
Messages
This image is similar to the image of the letter "O" we first studied in this activity, but there are splotchy regions in the background that result, perhaps, from scanning the image. We think of the splotchy regions as noise, and our goal is to improve the quality of the image by reducing the noise.
1. Plot the singular values below. How are the singular values of this matrix similar to those represented by the clean image that we considered earlier and how are they different?
  xxxxxxxxxx
  
  plot_sv(A)
  
  Language:
  
  Messages
  🔗
  🔗
2. There is a natural point where the singular values dramatically decrease so it makes sense to think of the noise as being formed by the small singular values. To denoise the image, we will therefore replace $A$ by its approximation $A_{k},$ where $k$ is the point at which the singular values drop off. This has the effect of setting the small singular values to zero and hence eliminating the noise. Choose an appropriate value of $k$ below and notice that the new image appears to be somewhat cleaned up as a result of removing the noise.
  xxxxxxxxxx
  
  k =
  display_matrix(approximate(A, k))
  
  Language:
  
  Messages
  🔗
  🔗
🔗
🔗

🔗

Several examples illustrating how the singular value decomposition compresses images are available at this page from Tim Baumann.

timbaumann.info/projects.html

🔗

Subsection 7.5.5 Analyzing Supreme Court cases

As we’ve seen, a singular value decomposition concentrates the most important features of a matrix into the first singular values and singular vectors. We will now use this observation to extract meaning from a large dataset giving the voting records of Supreme Court justices. A similar analysis appears in the paper A pattern analysis of the second Rehnquist U.S. Supreme Court

gvsu.edu/s/21F

by Lawrence Sirovich.

🔗

The makeup of the Supreme Court was unusually stable during a period from 1994-2005 when it was led by Chief Justice William Rehnquist. This is sometimes called the second Rehnquist court. The justices during this period were:

William Rehnquist
🔗

🔗
Antonin Scalia
🔗

🔗
Clarence Thomas
🔗

🔗
Anthony Kennedy
🔗

🔗
Sandra Day O’Connor
🔗

🔗
John Paul Stevens
🔗

🔗
David Souter
🔗

🔗
Ruth Bader Ginsburg
🔗

🔗
Stephen Breyer
🔗

🔗

🔗

During this time, there were 911 cases in which all nine judges voted. We would like to understand patterns in their voting.

🔗

Activity 7.5.6.

Evaluating the following cell loads and displays a dataset describing the votes of each justice in these 911 cases. More specifically, an entry of +1 means that the justice represented by the row voted with the majority in the case represented by the column. An entry of -1 means that justice was in the minority. This information is also stored in the

9 \times 911

matrix

A .

xxxxxxxxxx
 
sage.repl.load.load('https://raw.githubusercontent.com/davidaustinm/ula_modules/master/svd_supreme.py', globals())
A = matrix(RDF, cases.values)
cases

The justices are listed, very roughly, in order from more conservative to more progressive.

🔗

In this activity, it will be helpful to visualize the entries in various matrices and vectors. The next cell displays the first 50 columns of the matrix

A

with white representing an entry of +1, red representing -1, and black representing 0.

xxxxxxxxxx
 
display_matrix(A.matrix_from_columns(range(50)))

Plot the singular values of $A$ below. Describe the significance of this plot, including the relative contributions from the singular values $σ_{k}$ as $k$ increases.
xxxxxxxxxx

plot_sv(A)
Language:
Messages
🔗
🔗
Form the singular value decomposition $A = U Σ V^{T}$ and the matrix of coefficients $Γ$ so that $A = U Γ .$
xxxxxxxxxx
Language:
Messages
🔗
🔗
We will now study a particular case, the second case which appears as the column of $A$ indexed by 1. There is a command display_column(A, k) that provides a visual display of the $k^{t h}$ column of a matrix $A .$ Describe the justices’ votes in the second case.
xxxxxxxxxx
Language:
Messages
🔗
🔗
Also, display the first left singular vector $u_{1},$ the column of $U$ indexed by $0,$ and the column of $Γ$ holding the coefficients that express the second case as a linear combination of left singular vectors.
xxxxxxxxxx
Language:
Messages
What does this tell us about how the second case is constructed as a linear combination of left singular vectors? What is the significance of the first left singular vector $u_{1} ?$
🔗
🔗
Let’s now study the $48^{t h}$ case, which is represented by the column of $A$ indexed by 47. Describe the voting pattern in this case.
xxxxxxxxxx
Language:
Messages
🔗
🔗
Display the second left singular vector $u_{2}$ and the vector of coefficients that express the $48^{t h}$ case as a linear combination of left singular vectors.
xxxxxxxxxx
Language:
Messages
Describe how this case is constructed as a linear combination of singular vectors. What is the significance of the second left singular vector $u_{2} ?$
🔗
🔗
The data in Table 7.5.2 describes the number of cases decided by each possible vote count.
Table 7.5.2. Number of cases by vote count
🔗

Vote count # of cases

9-0 405

8-1 89

7-2 111

6-3 118

5-4 188

How do the singular vectors $u_{1}$ and $u_{2}$ reflect this data? Would you characterize the court as leaning toward the conservatives or progressives? Use these singular vectors to explain your response.
🔗

🔗
Cases decided by a 5-4 vote are often the most impactful as they represent a sharp divide among the justices and, often, society at large. For that reason, we will now focus on the 5-4 decisions. Evaluating the next cell forms the $9 \times 188$ matrix $B$ consisting of 5-4 decisions.
xxxxxxxxxx

B = matrix(RDF, fivefour.values)
display_matrix(B.matrix_from_columns(range(50)))
Language:
Messages
Form the singular value decomposition of $B = U Σ V^{T}$ along with the matrix $Γ$ of coefficients so that $B = U Γ$ and display the first left singular vector $u_{1} .$ Study how the $7^{t h}$ case, indexed by 6, is constructed as a linear combination of left singular vectors.
xxxxxxxxxx
Language:
Messages
What does this singular vector tell us about the make up of the court and whether it leans towards the conservatives or progressives?
🔗
🔗
Display the second left singular vector $u_{2}$ and study how the $6^{t h}$ case, indexed by 5, is constructed as a linear combination of left singular vectors.
xxxxxxxxxx
Language:
Messages
What does $u_{2}$ tell us about the relative importance of the justices’ voting records?
🔗
🔗
By a swing vote, we mean a justice who is less inclined to vote with a particular bloc of justices but instead swings from one bloc to another with the potential to sway close decisions. What do the singular vectors $u_{1}$ and $u_{2}$ tell us about the presence of voting blocs on the court and the presence of a swing vote? Which justice represents the swing vote?
🔗

🔗

🔗

Subsection 7.5.6 Summary

This section has demonstrated some uses of the singular value decomposition. Because the singular values appear in decreasing order, the decomposition has the effect of concentrating the most important features of the matrix into the first singular values and singular vectors.

Because the first left singular vectors form an orthonormal basis for $Col (A),$ a singular value decomposition provides a convenient way to project vectors onto $Col (A)$ and therefore to solve least-squares problems.
🔗

🔗
A singular value decomposition of a rank $r$ matrix $A$ leads to a series of approximations $A_{k}$ of $A$ where

$\begin{aligned} A \approx A_{1} & = σ_{1} u_{1} v_{1}^{T} \\ A \approx A_{2} & = σ_{1} u_{1} v_{1}^{T} + σ_{2} u_{2} v_{2}^{T} \\ A \approx A_{3} & = σ_{1} u_{1} v_{1}^{T} + σ_{2} u_{2} v_{2}^{T} + σ_{3} u_{3} v_{3}^{T} \\ ⋮ \\ A = A_{r} & = σ_{1} u_{1} v_{1}^{T} + σ_{2} u_{2} v_{2}^{T} + σ_{3} u_{3} v_{3}^{T} + \dots + σ_{r} u_{r} v_{r}^{T} \end{aligned}$

In each case, $A_{k}$ is the rank $k$ matrix that is closest to $A .$

🔗

🔗
If $A$ is a demeaned data matrix, the left singular vectors give the principal components of $A,$ and the variance in the direction of a principal component can be simply expressed in terms of the corresponding singular value.
🔗

🔗
The singular value decomposition has many applications. In this section, we looked at how the decomposition is used in image processing through the techniques of compression and denoising.
🔗

🔗
Because the first few left singular vectors contain the most important features of a matrix, we can use a singular value decomposition to extract meaning from a large dataset as we did when analyzing the voting patterns of the second Rehnquist court.
🔗

🔗

🔗

Exercises 7.5.7 Exercises

1.

Suppose that

A = [\begin{matrix} 2.1 & - 1.9 & 0.1 & 3.7 \\ - 1.5 & 2.7 & 0.9 & - 0.6 \\ - 0.4 & 2.8 & - 1.5 & 4.2 \\ - 0.4 & 2.4 & 1.9 & - 1.8 \end{matrix}] .

xxxxxxxxxx
 
​

Find the singular values of $A .$ What is $rank (A) ?$
🔗

🔗
Find the sequence of matrices $A_{1},$ $A_{2},$ $A_{3},$ and $A_{4}$ where $A_{k}$ is the rank $k$ approximation of $A .$
🔗

🔗

🔗

2.

Suppose we would like to find the best quadratic function

β_{0} + β_{1} x + β_{2} x^{2} = y

fitting the points

(0, 1), (1, 0), (2, 1.5), (3, 4), (4, 8) .

xxxxxxxxxx
 
​

Set up a linear system $A x = b$ describing the coefficients $x = [\begin{array}{r} β_{0} \\ β_{1} \\ β_{2} \end{array}] .$
🔗

🔗
Find the singular value decomposition of $A .$
🔗

🔗
Use the singular value decomposition to find the least-squares approximate solution $\hat{x} .$
🔗

🔗

🔗

3.

Remember that the outer product of two vectors

u

and

v

is the matrix

u v^{T} .

Suppose that $u = [\begin{array}{r} 2 \\ - 3 \end{array}]$ and $v = [\begin{array}{r} 2 \\ 0 \\ 1 \end{array}] .$ Evaluate the outer product $u v^{T} .$ To get a clearer sense of how this works, perform this operation without using technology.
🔗

How is each of the columns of $u v^{T}$ related to $u ?$
🔗

🔗
Suppose $u$ and $v$ are general vectors. What is $rank (u v^{T})$ and what is a basis for its column space $Col (u v^{T}) ?$
🔗

🔗
Suppose that $u$ is a unit vector. What is the effect of multiplying a vector by the matrix $u u^{T} ?$
🔗

🔗

🔗

4.

Evaluating the following cell loads in a dataset recording some features of 1057 houses. Notice how the lot size varies over a relatively small range compared to the other features. For this reason, in addition to demeaning the data, we’ll scale each feature by dividing by its standard deviation so that the range of values is similar for each feature. The matrix

A

holds the result.

xxxxxxxxxx
 
import pandas as pd
df = pd.read_csv('https://raw.githubusercontent.com/davidaustinm/ula_modules/master/data/housing.csv', index_col=0)
df = df.fillna(df.mean())
std = (df-df.mean())/df.std()
A = matrix(std.values).T
df.T

Find the singular values of $A$ and use them to determine the variance in the direction of the principal components.
xxxxxxxxxx
Language:
Messages
🔗
🔗
For what fraction of the variance do the first two principal components account?
🔗

🔗
Find a singular value decomposition of $A$ and construct the $2 \times 1057$ matrix $B$ whose entries are the coordinates of the demeaned data points projected on to the two-dimensional subspace spanned by the first two principal components. You can plot the projected data points using list_plot(B.columns()).
xxxxxxxxxx
Language:
Messages
🔗
🔗
Study the entries in the first two principal components $u_{1}$ and $u_{2} .$ Would a more expensive house lie on the left, right, top, or bottom of the plot you constructed?
🔗

🔗
In what ways does a house that lies on the far left of the plot you constructed differ from an average house? In what ways does a house that lies near the top of the plot you constructed differ from an average house?
🔗

🔗

🔗

5.

Let’s revisit the voting records of justices on the second Rehnquist court. Evaluating the following cell will load the voting records of the justices in the 188 cases decided by a 5-4 vote and store them in the matrix

A .

xxxxxxxxxx
 
sage.repl.load.load('https://raw.githubusercontent.com/davidaustinm/ula_modules/master/svd_supreme.py', globals())
A = matrix(RDF, fivefour.values)
v = vector(188*[1])
fivefour

The cell above also defined the 188-dimensional vector $v$ whose entries are all 1. What does the product $A v$ represent? Use the following cell to evaluate this product.
xxxxxxxxxx
Language:
Messages
🔗
🔗
How does the product $A v$ tell us which justice voted in the majority most frequently? What does this say about the presence of a swing vote on the court?
🔗

🔗
How does this product tell us whether we should characterize this court as leaning conservative or progressive?
🔗

🔗
How does this product tell us about the presence of a second swing vote on the court?
🔗

🔗
Study the left singular vector $u_{3}$ and describe how it reinforces the fact that there was a second swing vote. Who was this second swing vote?
🔗

🔗

🔗

6.

The following cell loads a dataset that describes the percentages with which justices on the second Rehnquist court agreed with one another. For instance, the entry in the first row and second column is 72.78, which means that Justices Rehnquist and Scalia agreed with each other in 72.78% of the cases.

xxxxxxxxxx
 
sage.repl.load.load('https://raw.githubusercontent.com/davidaustinm/ula_modules/master/svd_supreme.py', globals())
A = 1/100*matrix(RDF, agreement.values)
agreement

Examine the matrix $A .$ What special structure does this matrix have and why should we expect it to have this structure?
🔗

🔗
Plot the singular values of $A$ below. For what value of $k$ would the approximation $A_{k}$ be a reasonable approximation of $A ?$
xxxxxxxxxx

plot_sv(A)
Language:
Messages
🔗
🔗
Find a singular value decomposition $A = U Σ V^{T}$ and examine the matrices $U$ and $V$ using, for instance, n(U, 3). What do you notice about the relationship between $U$ and $V$ and why should we expect this relationship to hold?
xxxxxxxxxx
Language:
Messages
🔗
🔗
The command approximate(A, k) will form the approximating matrix $A_{k} .$ Study the matrix $A_{1}$ using the display_matrix command. Which justice or justices seem to be most agreeable, that is, most likely to agree with other justices? Which justice is least agreeable?
xxxxxxxxxx
Language:
Messages
🔗
🔗
Examine the difference $A_{2} - A_{1}$ and describe how this tells us about the presence of voting blocs and swing votes on the court.
xxxxxxxxxx
Language:
Messages
🔗
🔗

🔗

7.

Suppose that

A = U_{r} Σ_{r} V_{r}^{T}

is a reduced singular value decomposition of the

m \times n

matrix

A .

The matrix

A^{+} = V_{r} Σ_{r}^{- 1} U_{r}^{T}

is called the Moore-Penrose inverse of

A .

Explain why $A^{+}$ is an $n \times m$ matrix.
🔗

🔗
If $A$ is an invertible, square matrix, explain why $A^{+} = A^{- 1} .$
🔗

🔗
Explain why $A A^{+} b = \hat{b},$ the orthogonal projection of $b$ onto $Col (A) .$
🔗

🔗
Explain why $A^{+} A x = \hat{x},$ the orthogonal projection of $x$ onto $Col (A^{T}) .$
🔗

🔗

🔗

8.

In Subsection 5.1.1, we saw how some linear algebraic computations are sensitive to round off error made by a computer. A singular value decomposition can help us understand when this situation can occur.

🔗

For instance, consider the matrices

A = [\begin{matrix} 1.0001 & 1 \\ 1 & 1 \end{matrix}], B = [\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}] .

The entries in these matrices are quite close to one another, but

A

is invertible while

B

is not. It seems like

A

is almost singular. In fact, we can measure how close a matrix is to being singular by forming the condition number,

σ_{1} / σ_{n},

the ratio of the largest to smallest singular value. If

A

were singular, the condition number would be undefined because the singular value

σ_{n} = 0 .

Therefore, we will think of matrices with large condition numbers as being close to singular.

Define the matrix $A$ and find a singular value decomposition. What is the condition number of $A ?$
xxxxxxxxxx
Language:
Messages
🔗
🔗
Define the left singular vectors $u_{1}$ and $u_{2} .$ Compare the results $A^{- 1} b$ when
1. $b = u_{1} + u_{2} .$
  🔗
  
  🔗
2. $b = 2 u_{1} + u_{2} .$
  🔗
  
  🔗
Notice how a small change in the vector $b$ leads to a small change in $A^{- 1} b .$

🔗
🔗
Now compare the results $A^{- 1} b$ when
1. $b = u_{1} + u_{2} .$
  🔗
  
  🔗
2. $b = u_{1} + 2 u_{2} .$
  🔗
  
  🔗
Notice now how a small change in $b$ leads to a large change in $A^{- 1} b .$

🔗
🔗
Previously, we saw that, if we write $x$ in terms of left singular vectors $x = c_{1} v_{1} + c_{2} v_{2},$ then we have

$b = A x = c_{1} σ_{1} u_{1} + c_{2} σ_{2} u_{2} .$

If we write $b = d_{1} u_{1} + d_{2} u_{2},$ explain why $A^{- 1} b$ is sensitive to small changes in $d_{2} .$

🔗

🔗

Generally speaking, a square matrix

A

with a large condition number will demonstrate this type of behavior so that the computation of

A^{- 1}

is likely to be affected by round off error. We call such a matrix ill-conditioned.

🔗

You have attempted 1 of 1 activities on this page.

🔗

Prev Top Next

Vote count	# of cases
9-0	405
8-1	89
7-2	111
6-3	118
5-4	188

Section 7.5 Using Singular Value Decompositions

Preview Activity 7.5.1.

Subsection 7.5.1 Least-squares problems

Activity 7.5.2.

Proposition 7.5.1.

Subsection 7.5.2 Rank k approximations

Activity 7.5.3.

Subsection 7.5.3 Principal component analysis

Activity 7.5.4.

Subsection 7.5.4 Image compressing and denoising

Activity 7.5.5.

Subsection 7.5.5 Analyzing Supreme Court cases

Activity 7.5.6.

Subsection 7.5.6 Summary

Exercises 7.5.7 Exercises

1.

2.

3.

4.

5.

6.

7.

8.

Subsection 7.5.2 Rank $k$ approximations