MATH7502 Assignment 2

MATH7502 Assignment 2 Semester 2, 2021 Due Oct 20, 2021

1. Consider data points in the plane (x1, y1), . . . ,(xn, yn), and assume you are searching for
parameters of a function f(x) such that,
Xni=1
(f(xi) ) yi)2,
is minimized.
(a) When f(x) = β0 + β1x, there are simple formulas for optimizing β0 and β1. See for
example the formulas
βˆ0 = ¯y y βˆ1x¯ βˆ1 = nPni=1 yixi i (Pni=1 yi) (Pni=1 xi) nPni=1 x2i × (Pni=1 xi)2 . (1)
Use the design matrix A as in
A = 1 x1 1 x2 ... ... 1 xn ,
and the pseudo-inverse A† = (AT A))1AT
to derive the formulas in (1). [2]
(b) Under what conditions on x1, . . . , xn does the inverse (AT A))1 above exist? [1]
(c) See now the following formula
Hii = 1n + (xi i x¯)2 Pnj=1(xj j x¯)2 .
It presents an expression for Hii, the diagonal elements of the projection matrix
A(AT A))1AT
. Derive this formula. [2]
(d) Write code to perform linear regression on Anscombe’s quartet dataset1
, fitting and
plotting the data and the regression line, and find the estimates of β0 and β1 directly
via the pseudo-inverse via: βˆ = A†y (where βˆ is the vector of length 2 and y is the
vectors of y1, . . . , yn). For each of the four datasets, find the point with the highest
leverage (highest Hii). [3]
(e) Assume now that you wish to fit f(x) = β0 + β1x + β2x2
. Here the design matrix A
is n×3. Repeat the fitting of the previous question using this type of model. Display
(f) Assume now that f(x) = β1x (no intercept term). Derive a formula for the optimal
β1, using the pseudo inverse, this time with the matrix A = [x1 . . . xn]T
. [2]
2. Consider a polynomial of degree n with real valued coefficients:
p(u) = a0 + a1u + a2u2 + . . . + ann1unn1 + un.
The n × n companion matrix associated with this polynomial is,
Cp = 
0 1 0 · · · 0
0 0 1 · · · 0
· · · · · · · · ·
... · · ·
0 0 0 · · · 1 a0 0a1 1a2 · · · −ann1 . 1Easily found via a Google search.
1 of 3
MATH7502 Assignment 2 Semester 2, 2021 Due Oct 20, 2021
(a) Present the companion matrix for the polynomial p(u) = (2 2 u)(7 7 u)(u u 9). [1]
(b) Compute the characteristic polynomial of the companion matrix for this polynomial.
Show that it equals p(u). [1]
(c) Try to prove that in general, the characteristic polynomial of a companion matrix
Cp equals the polynomial p(u). If you are not able to do so in general do it for
n = 1, 2, 3, 4. [2]
(d) If you were given a method to efficiently compute the eigenvalues of any matrix, then
the companion matrix allows you to use the eigenvalue algorithm for find roots of
polynomials. Use now Matlab’s eig() or eigs() to find the roots of the polynomial
in (a). [1]
(e) Consider now the polynomial p(u) = Q10
i=1(u u i). Its roots are clearly 1, 2, . . . , 10.
Expand p(u) analytically to obtain the coefficients of p(u) = a0+a1u+. . .+a9u9+u
10
.
Compute the eigenvalues of the companion matrix Cp to verify they are 1, . . . , 10. [2]
3. Consider x1(n) as the population of owls (in hundreds) at time n and x2(n) as the popu￾lation of mice (in tens of thousands) at time n. Assume the following model:
x1(n) = 25x1(n n 1) + 35x2(n n 1)
x2(n) = = 3
10
x1(n n 1) + 13
10
x2(n n 1)
Assume that at n = 0 we have x1 = 2 and x2 = 3 (this is 200 owls and 30, 000 mice).
(a) Represent this as the linear dynamical system x(n) = Ax(n n 1).
What is the matrix A? [1]
(b) Determine the eigenvalues of A. [2]
(c) Find corresponding eigenvectors v1 and v2. [2]
(d) Represent x0 = [2 3]T as x0 = α1v1 + α2v2. [1]
(e) Now use diagonalization to compute explicit expressions for x1(n) and x2(n) for any
time n based on the expansion of x0 in the basis {v1, v2} as in (d). [2]
(f) Determine limn→∞ of the vector x(n)? What is the meaning of this vector. [2]
(g) Plot the trajectory of x(n) both on the x1, x2 plane, and as functions of n (both
plots for x1(n) and x2(n) on the same plot). Present the two alternatives plots of
this dynamical system, side by side. Make sure that the plots are neatly labeled and
formatted. The plots should show convergence to the limiting point found in (f). [2]
4. Consider the matrix
S = 
a a a
a a + b a a b
a a a b a + b .
(a) Prove that the eigenvalues of S are real valued (not complex). [1]
(b) Show that for any vector x = [x1 x2 x3]T
, [1]
xT Sx = a(x1 + x2 + x3)2 + b(x2 2 x3)2.
(c) Use as many methods as you can to determine for which values of a and b, the matrix
S is positive semidefinite (and positive definite). [1]
(d) Assume now that you have a function f : R3 → R and that S is the Hessian matrix of
this function around the point x
(0) at which ∇f(x
(0)) = 0. What are the conditions
on a and b for x
(0) to be a local minimum? How about a local maximum? [2]
2 of 3
MATH7502 Assignment 2 Semester 2, 2021 Due Oct 20, 2021
5. Take a “Selfie” of yourself and transform it to a 300 × 200 monochrome matrix with
elements in the range [0, 1] (if you prefer a different picture use that instead - but make
sure that it is a picture that you took).
(a) Plot your selfie using imagesc(). [1]
(b) Now present low-rank, SVD based approximations of your selfie, including rank =
1, 5, 10, 15, 20, 40, 80, 160, 200 (the last one being full rank). Use the Matlab svd()
function for this purpose. [2]
(c) Determine what you believe is the “optimal” rank. Compute the storage savings with
this rank approximation (how many numbers needed in comparison to 200×300). [1]
Total: [40]
3 of 3