Blog

QBUS1040 Assignment 5
Semester 1, 2022
Out: 12th May 2022
Due: 27th May 2022 at 11:59pm
Instructions
This assignment consists of six problems, some involving multiple parts. Some parts require a written
response and others involve coding. The parts that require a written response are described in this
document, while the coding questions are described in the associated Jupyter notebook (.ipynb file).
You should submit a PDF to GradeScope for the written questions and match the page number with
the questions that you answered. You can find the detailed instructions on how to scan and submit
your assignments through GradeScope on Canvas. If you fail to match the page to the corresponding
question, the marker will not be able to view your response and thus you will be awarded 0 marks for the
question.
You may not use notation, concepts or material from other classes (say, a linear algebra class you may
have taken) in your solutions. All the problems can be done using only the material from this class, and
we will deduct points from solutions that refer to outside material.
Question: 1 2 3 4 5 6 Total
Points: 10 15 10 20 20 20 95
i
QBUS1040 Assignment 5 Due 27th May 2022
1. (10 points) Algorithm 12.1 in the textbook uses the QR factorization to compute the least squares approx-
imate solution x = A b, where the m× n matrix A has linearly independent columns. It has a complexity
of 2mn2 flop

s. In this exercise we consider an alternative method: First, form the Gram matrix G = ATA
and the vector h = AT b, then compute x = G 1h (using algorithm 11.2 in the textbook). What is the
complexity of this method Compare it to algorithm 12.1.
2. In this question, we examine computing k-fold cross-validation on a least squares problem ∥Ax b∥2, where
A is a N×p matrix and b is a N -vector. The least squares problem can arise, for example from a data-fitting
model with N data points and p basis functions, and we wish to use k-fold cross validation to assess our
choice of basis functions.
We assume for convenience that N can be split into k even-sized folds of size N/k (so k divides N).
Let A1, . . . , Ak denote the (N/k) × p blocks of data corresponding to each fold, and b1, . . . , bp denote the
corresponding right hand sides for each fold. We also assume N is much larger than p, i.e., N p, and
that columns of A remain linearly independent even when we remove one block Ai.
(a) (5 points) Analyse the complexity of the following na¨ ve method of performing k-fold cross-validation:
for each fold i = 1, . . . , k
Construct A i to be the matrix A but with rows corresponding to Ai removed. (Note that A i has
size ((k 1)N/k)× p.)
Construct b i to be the right-hand side vector b but with entries corresponding to bi removed. (Note
that b i is a ((k 1)N/k)-vector.)
Compute θi = A