## Description

1. Write a 2 × 2 Givens rotation

c s

−s c

as a product of two Householder reflections. Hint: one

way to do this involves making one of the two Householder reflectors represent the reflection

across a coordinate axis.

2. Prove or disprove: any square orthogonal matrix can be written as a product of Householder

reflectors.

3. Prove or disprove: any square orthogonal matrix can be written as a product of Givens rotations.

4. What are the eigenvalues and eigenvectors for a Householder reflector of the form I − 2uuT

where u

T u = 1?

5. Let P =

c s

s −c

, with c

2 + s

2 = 1. Prove or disprove: P is an orthogonal transformation. Is

this a Givens rotation, a Householder transformation, or neither? If a Givens rotation, write it

as a Givens rotation. If a Householder transformation, write it in the form I − 2uuT

for some

unit vector u.

6. Paul, Jane, and Ann, share information about their likes and dislikes of movies in order to make

decisions about selecting films to see. They rates films they see with a scale of 0 to 10, (10

means they liked the movie very much). Here is the status of their table of ratings when Ann

was interested in a new film which soon came to a ’theater near her’ (titled ’Title 6’ in the table):

movie Paul Jane Ann

Title-1 4 8 4

Title-2 9 3 8

Title-3 2 6 1

Title-4 7 4 4

Title-5 8 3 6

Title-6 3 8 x

Ann generally follows a combination of Paul and Jane’s ratings. Ann wants to predict how well

she will like the movie Title-6, which Paul and Jane have already seen. Ann reasons as follows:

she will give her ’similarity’ coefficients α and β for Paul and Jane respectively. If the missing

rating (call it x) were known then the column of Ann’s ratings should be the closest in the

least-squares sense to the combination of Paul’s and Jane’s ratings:

min

α,β

Paul’s ratings

· α +

Jane’s ratings

· β −

Ann’s ratings

2

2

= min

α,β

Paul’s ratings

Jane’s ratings

·

α

β

!

−

Ann’s ratings

2

2

1

Determine, α, β using the first 5 movie ratings, and from that the combination of Paul’s and

Jane’s ratings that is closest to Ann’s, in a least squares sense. Use the resulting best combination

to infer the induced rating for Ann for Title-6. Should Ann see ’Title 6’? Is her taste closer to

Paul’s or to Jane’s?

7. The data in the file lsidata.m∗

contains the term-frequency matrix A for a collection of 2340

documents, using a dictionary of 21839 words. Load this data into matlab and design a query

to retrieve all documents containing the word “bipolar”. Apply this query to the original term

frequency matrix (with columns scaled to unit length) and then repeat this procedure using the

best rank-50 approximation A50 to the term-frequency matrix A. Only the document headlines

are provided, but the word counts are based on the document contents which can be found at

the web site mentioned within the datafile.

Hints: use svds to obtain the singular value decomposition A = UΣV

T

instead of svd, because

(a) the matrix A is too big for svd and (b) you can get the rank 50 approximation A50 directly

from svds. Do not try to form the rank-50 approximation explicitly – rather work directly with

the factors U, Σ, V obtained from svds. Do not forget to normalize the columns to unit length

before applying a query or computing the SVD. A skeleton matlab script for this problem is

given in LSIpreamble.m∗

.

The query vector is a vector with 1’s in the positions corresponding to the words in your query

and zeros for all other words. So if your query is only one word, then the query vector has only

one nonzero element. If n is the number of words, and m the number of documents, then q is

an n-vector with only a few nonzero elements. The term-frequency matrix A is an n × m with

the j-th column corresponding to the j-th document. If each column aj (for j = 1, . . . , m) is

normalized to length 1 in the usual 2-norm, and the query vector q is also normalized to unit

length, then the inner product q ◦ aj is the cosine of the angle between the two vectors. If the

vectors are almost the same, then the angle will be small and the cosine will be very close to 1.

If all the columns of A are normalized in this fashion, then all the cosines can be computed at

once with the formula q

T A. So your task is to compute q

T A and also q

T A50. Once you have

computed these two vectors of similarities, you need to sort each of them to find the positions

of the 10 biggest values, and then print out the document headlines corresponding to those

positions.

You will need to use the sort function in matlab, which returns two results. The first result is

the values sorted, and the second result consists of the indices of the positions of those values.

You can use that second result to retrieve the document headlines.

A sample script which carries out all of this on a toy example is given in LSItoy.m∗

.

∗All external links are located in http://www-users.cselabs.umn.edu/classes/Fall-2014/csci5304/Notes/

MatlabDemos/.

2