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