COMS4771 HW 0 Solved

Description

This is a calibration assignment (HW0). The goal of this assignment is for you to recall basic concepts, and get familiarized with the homework submission system (Gradescope). Everyone enrolled must submit this assignment by the due date. The score received on this assignment will not count towards your final grade in this course. You must show your work to receive full credit. You should cite all resources (including online material, books, articles, help taken from specific individuals, etc.) you used to complete your work.

This homework assignment is to be done individually. All homeworks (including this one) should be typesetted properly in pdf format. Handwritten solutions will not be accepted. You must include your name and UNI in your homework submission.

1.1 [Probability and Statistics] Let X and Y be discrete random variables, and consider the joint distribution (X,Y ) given by

	Y=1	Y=2	Y=3
X=1	0.1	0.2	0.3
X=2	0.2	0.1	0.1

• What is the marginal distribution of X?
• What is Pr[Y = 1|X = 2]?
• Let f : x 7→ x². What is E[f(X)|Y = 1]?

1.2 Fix some θ > 0, and consider the function g_θ : [0,∞) → R defined as.

• Verify that g_θ is a probability distribution.
• Let X be a random variable distributed as g_θ. What is E[X]?
• What is Variance(X)?

1.3 You live with your cat in an apartment in a relatively safe neighborhood with a crime rate of 5%. Being a cautious person, you have invested in a good quality burglar alarm that is rated to be 99% effective at the time of a break-in. Over time you have observed that your cat likes to play with the alarm causing it to trip 10% of the time. One day while you are at work your neighbor calls you telling that the alarm is ringing. What is the probability that there was a break-in?

2.1 [Linear Algebra] Consider the subspace S spanned by vectors.

• What is the dimension of the subspace S.
• Compute the orthogonal linear projection of the point , onto the subspace S.

2.2 Prove that for any m × n real matrix A and any ρ > 0, the matrix A^TA + ρI is invertible (where I is the n × n identity matrix). (Hint: show that all eigenvalues of A^TA + ρI are real and analyze the smallest eigenvalue.)

3.1 [Calculus and optimization] Let A ∈ R^d×D be a real matrix, and b ∈ R^d be a real vector. Define the function

f :R^D → R

x 7→ kAx − bk² + kxk².

• What is ∇f(x)?
• What value of x minimizes f, that is, find argmin_x f(x)? (Hint: compute the stationary points of f.)

4.1 [Programming practice] Download the Matlab data file hw0data.mat (instructions on Piazza on where to download the file). Write a script that does the following.

Special note for those who are not using Matlab: Python users can use scipy to read in the mat file, R users can use R.matlab package to read in the mat file, Julia users can use JuliaIO/MAT.jl. Octave users should be able to load the file directly.

• Load the data in hw0data.mat. It contains one matrix variable is called M.
• Print the dimensions of M.
• Print the 4th row and 5th column entry of M.
• Print the mean value of the 5th column of M.
• Compute the histogram of the 4th row of M and show the figure.
• Compute and print the top three eigenvalues of the matrix M^T

4.2 We will try to understand the geometry of eigenvectors and eigenvalues of a matrix via exper-

imentation. Let L  be a 2 × 2 matrix. To understand eigenvectors and

eigenvalues, we will study the action of L on random vectors and relate it to eigenvectors and eigenvalues. Write a script that does the following.

• Create the 2 × 2 matrix L (as defined above).
• Create 500 random, unit length, two-dimensional vectors. (Hint: to generate a random d-dimensional unit length vector, draw d independent samples from the Gaussian distribution N(0,1) and assign each sample as one component of the vector. Now, normalize the vector to have length one.) Let R be the set of these 500 random 2-dimensional unit vectors.
• For each vector r ∈ R, compute how the matrix L “distorts” r, that is, compute ˜r :=
• Compute the eigenvalues of L. Let λ_max and λ_min denote the maximum and the minimum eigenvalue respectively.
• For each distorted vector ˜r, compute the length k˜rk.
• Create a histogram of values of k˜rk (use 50 bins) and compare it to λ_max and λ_min.
• What relationship can you infer between k˜rk, λ_max and λ_min?
• Now, compute the eigenvectors of L. Let v_max denote the eigenvector corresponding to the maximum eigenvalue λ_max.
• Make a two-dimensional plot of all the distorted vectors ˜r (in blue color) and the eigenvector Lv_max (in red color). (make sure that the x- and the y-axis are displayed at the same scale).
• What can you infer about the v_max from studying this plot?