SCHOOL OF MATHEMATICAL SCIENCES

MTH3320

Computational Linear Algebra

Assignment 2

Due date: Thursday 30 April, 2020, 9pm (submit

the electronic copy of your assignment and the

matlab code via Moodle)

This assignment contains four questions for a total of 50 marks (equal to 7.5% of the

final mark for this unit).

Late submissions will be subject to late penalties (see the unit guide for full

details).

The relevant output of the programming exercises are to be submitted as part of your

electronic submission. You can either include the outputs as a part of your pdf file (if

you can edit the pdf document), or include them in a separate word document (you need

to label the figures and outputs consistently with the question number). In addition,

collect all your Matlab m-files in one zip file and submit this file through Moodle.

1. Householder reflection in R2. (10 marks)

Let

A =

[

~a1 ~a2

]

=

[

8 10

6 20

]

.

(a) Construct the first Householder reflection matrix, Q1, which reflects the first col-

umn of A, ~a1, to a vector

Q1~a1 =

[±‖~a1‖

0

]

,

i.e., choose the sign according to the rule used to ensure numerical stability, de-

termine vector ~v1 and its normalised version ~u1, and then the matrix Q1.

(b) Verify that Q1 is an orthogonal matrix.

(c) Compute

Q1

[

2

−6

]

,

the image of the vector (2,−6)T under the reflection.

School of Mathematical Sciences Monash University

(d) Compute

Q1

[−3

4

]

,

the image of the vector (−3, 4)T under the reflection.

(e) Make a sketch (by hand) in the R2 plane indicating the vectors ~x = (x, y)T ∈

R2 that arise in parts (a)-(d): the original vector ~a1, its image Q1~a1 under the

reflection, the vectors ~v1 and ~u1, and the vectors (2,−6)T and (−3, 4)T and their

images under the reflection. Also indicate the line about which the vectors are

reflected.

(f) Compute Q1A and write down the QR decomposition of A.

Note: Do all computations by hand. (You can verify the results by Matlab if you want.)

2. Eigenvalues of a Householder reflector matrix. (10

marks)

Determine the m eigenvalues of an m×m Householder reflector matrix

Q = I − 2~u~uT ,

where ~u ∈ Rm with ‖~u‖2 = 1, and find m corresponding eigenvectors.

(Hint: Some of the m eigenvalues may occur multiple times. Rather than trying to

compute the eigenvalues by the determinant formula, it is more straightforward to think

geometrically. Consider that a Householder reflection is a reflection of vectors in Rm

about a hyperplane that is orthogonal to ~u. What does the reflection do to a vector

in the hyperplane? (I.e., what does the reflection do to any vector orthogonal to ~u?)

What is the dimension of the hyperplane? What does the reflection do to ~u? Sketching

a picture of the situation in R3 may help.)

3. Implementation of QR decomposition by modified Gram-

Schmidt and Householder reflection. (15 marks)

Download the Matlab files test grams.m and myGramSchmidt.m. You need to write two

new functions myGramSchmidtMod.m and myHouseholder.m, and extend test grams.m

in this questions.

(a) The file myGramSchmidt.m contains an implementation of the classical Gram-

Schmidt algorithm (Algorithm 3.2). Make a modified version myGramSchmidtMod.m

that implements the more stable modified Gram-Schmidt algorithm (Algorithm

3.6). (It is, indeed, just a tiny change.)

In the template file test grams.m, we generate the following Vandermonde matrix:

m=100;

2020 2

School of Mathematical Sciences Monash University

n=15;

t=(0:m-1)’/(m-1);

A=[];

for i=1:n

A = [A t.^(i-1)];

end

This matrix arises in the context of polynomial interpolation and is notoriously

ill-conditioned.

You can modify the provided template file test grams.m to test the correctness

of your solution.

[Q,R]=myGramSchmidt(A);

[Qm,Rm]=myGramSchmidtMod(A);

[Qmatl,Rmatl]=qr(A);

Compare the orthogonality and the accuracy by displaying

norm(Q’*Q-eye(n))

norm(A-Q*R)

and the same for the modified and Matlab results.

You will see that the classical Gram-Schmidt algorithm loses all orthogonality

(have a look at Q’*Q) (no correct digits), the modified version is substantially

better (about half of the digits are correct), and the MATLAB version (which uses

Householder) maintains orthogonality close to machine precision. Interestingly,

though, all methods are still accurate for A − QR. (Understanding this fully is

quite complicated and the ramifications of this are quite involved; see the Trefethen

and Bau book p. 67, p. 115, p. 137.)

(b) Implement the QR algorithm using Householder reflections for A ∈ Rm×n in

Matlab according to the pseudocode discussed in class. Your implementation

myHouseholder.m should return the full versions of the factors, i.e. Q ∈ Rm×m

and R ∈ Rm×n. You should use the function header given below. Also, include

a printout of your code in the assignment package submitted to the assignment

boxes.

function [Q,R] = myHouseholder(A)

% Usage: [Q,R] = myHouseholder(A)

% Compute the QR factorization of matrix A using

% Householder reflections and return the resulting

% factors Q and R.

(c) Check the correctness of your implementation myHouseholder.m as follows. Ex-

tend test grams.m by adding a test that computes the QR factorisation of the

ill-conditioned matrix using myHouseholder.m. Compute and report the norm of

QTQ − I and A − QR. You will see that QTQ − I is almost as accurate as for

Matlab’s built-in QR decomposition, and much more accurate than for any of the

versions of Gram-Schmidt orthogonalisation.

2020 3

School of Mathematical Sciences Monash University

4. Implementation of the ALS Algorithm for Movie

Recommendation. (15 marks)

Read the pdf notes on movie recommendation (sections 1.3 and 3.5), and make

sure you understand the solutions of Questions 6, 7 and 8 from Tutorial 4.

(a) Download the files (will be released on 23 April)

system_movie_j.m

driver_ALS_test.m

from Moodle.

– Write a Matlab function with header

function [Ai bi]=system_user_i(Q,M,lambda,i)

that computes the matrix Ai and RHS vector ~bi for updating user vector ~ui in

the second phase of an ALS iteration (with M fixed) according to Eq. (3.17)

in the pdf notes, based on the transpose of the ratings matrix, Q = RT ,

current approximation for the user matrix M , and regularisation parameter

λ.

Note: This is the dual to function system movie j.m, and is, in fact, very

similar to it.

– Write a Matlab function with header

function [U M]=myALS(R,U,M,lambda)

which performs one ALS iteration, by first calling system movie j for each

column ~mj of M and solving the system, with U fixed, and by then calling

system user i for each column ~ui of U and solving the system.

– Write a Matlab function with header

function g=gValue(R,U,M,lambda)

to compute the value of the function we optimise, g(U,M) (as in Eq. (3.11)

in the notes).

– Test these implementations by executing the script driver ALS test.m, which

carries out 500 ALS iterations for the small toy problem of Question 6 of Tuto-

rial 4, and displays the error and value of g(U,M) as a function of iterations.

Hand in printouts of the error and iteration plots, along with printouts of

your Matlab files.

(b) In this question, we will apply the ALS recommendation algorithm to some

real-life movie rating data. We will use the data gathered by the non-

commercial MovieLens project, see https://grouplens.org/datasets/movielens/.

– Download the data set

ml-latest-small.zip

from https://grouplens.org/datasets/movielens/. This data set con-

tains 100,836 ratings from 610 users who have rated 9,742 movies between

1995 and 2018 with rating values between 0.5 and 5.0 (in increments of 0.5).

2020 4

School of Mathematical Sciences Monash University

– Read the README file on the website, which contains information about the

data files.

– Have a look a the data files (you can use xcel or any editor to read the csv

format). The ratings are contained in ratings.csv. The movie titles and

tags are in movies.csv.

– Download the files

movielens_load_data.m

getTitle.m

from Moodle. This is the same code you were given for Question 8 of Tutorial

4. If you have not done this as part of Tutorial 4, please take a close look at

the code in movielens load data.m and analyse what each part of the code

does. Run the code and investigate the output and the figures it generates.

Make sure you can relate the output to the code parts that generate it. Note

that movielens load data.m writes several files to disk that contains parts

of the Movielens data processed into the format of Matlab arrays.

– Write a Matlab function

driver_ALS.m

that runs the ALS algorithm on the Movielens dataset. Model driver ALS.m

after driver ALS test.m, and after parts of movielens load data.m (see

below). At the beginning of the file, you should load the Movielens data that

you will need:

load Rsp

load titles

load mov_index_from_column_to_global

Use the parameters

lambda=0.01;

nits=200;

f=20;

and the initialisation

U = ones(f, nUsers);

Then driver ALS.m should run 200 iterations of ALS on the Movielens data.

Hand in a plot of the value of g(U,M) as a function of the number of iterations,

along with printouts of all the Matlab code you write.

– Complete driver ALS.m with the following additional tasks:

∗ For user 123, list the title, categories and rating of the 10 movies that

the user ranked highest in the original ratings matrix. (Use getTitle.m

as in movielens load data.m.)

∗ For user 123, list the title and categories of the 10 movies that are most

highly recommended for the user.

2020 5

School of Mathematical Sciences Monash University

Hand in printouts of these lists. (Note that the highest predicted ratings

are a bit higher than 5, which is not surprising because the model does not

explicitly limit the predicted ratings between 0.5 and 5.)

2020 6