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,

n

(f (xi) │ yi)2 ,

i=1

is minimized.

(a) When f (x) = β0 + β1x, there are simple formulas for optimizing β0  and β 1 .  See for

example the formulas

βˆ1  = n      yixi │ (     yi) (     xi)

n      xi(2) │ (     xi)2                .

Use the design matrix A as in

┐'

A =  '            ' ,

'          '

'         '

and the pseudo-inverse At = (AT A)二1 AT  to derive the formulas in (1).        (b) Under what conditions on x1 , . . . , xn  does the inverse (AT A)二1  above exist?

(c)  See now the following formula

(1)

[2] [1]

1           (xi │ )2      

It presents an expression for Hii,  the diagonal elements of the projection matrix

A(AT A)二1 AT . 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:  βˆ = Aty (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 your fit model graphically.                                                                                           [2]

(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 + . . . + an二1un二1 + un .

The n = n companion matrix associated with this polynomial is,

    ┐'

'                                                     '

Cp =  '(')    '(') .

'  0        0        0      . . .       1     '

│a0     │a1     │a2     . . .   │an二1

(a)  Present the companion matrix for the polynomial p(u) = (2 │ u)(7 │ 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) =    (u │ i).  Its roots are clearly 1, 2, . . . , 10.

Expand p(u) analytically to obtain the coefficients of p(u) = a0 +a1u+ . . . +a9u9 +u10 . 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) = x1 (n │ 1) + x2 (n │ 1)

x2 (n) = │ x1 (n │ 1) + x2 (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 │ 1).

What is the matrix A?                                                                                                [1]

(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

(f)  Determine limnoo  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 │ 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 │ 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]