CS596 - Homework #2 -Solved

Foundations of Computer and Data Science 

matrix A

  .

a) Is A diagonalizable? Give explanations on your YES/NO answer, otherwise it will be considered incorrect!. b) Compute An,n > 1. c) Compute eA.

Problem 2: If V is the space of all random variables (including the deterministic variables that are regarded as random with 0 variance) then a) Show that this is a vector space. b) If x,y two random variables then show that the expectation of the product E[xy] defines an inner product in V. c) Consider the random variables 1,z1,...,zk which define a linear subspace Ω in V. If x is any random variable, find the best approximation ˆx of x that lies in Ω. d) What is the physical meaning of the problem you have solved in c)?

Problem 3: Form your own random matrix of size 20 × 5 which must be of rank equal to 3 (You must explain how you do it, to receive full grade). From the 100 elements of this matrix, start deleting at random positions first N = 2 elements, then N = 3,4,5 by replacing them with 0.

a) After you have deleted N elements, apply an SVD on the resulting matrix and examine its rank. Is it still 3? If not what is the maximum value the rank can attain?. b) Apply matrix filling using SVD and using the information that the original was of rank 3. c) Compare the reconstructed matrix with the original one (the one that has all the elements) for the different values of the number of deletions N and compute a measure of the error. When would you characterize the reconstruction method satisfactory?

Problem 4: a) Show that the smallest distance of a point (x∗,y∗) on the plane from a linear√

 

manifold (line) with equation Ax+By+C = 0 is equal to |Ax∗+By∗+C|/ A2 + B2. b) Suppose now that you are given a collection of points {(x1,y1),...,(xn,yn)}. Define a cost function by considering the sum of the squares of the distances of each point from the manifold. By taking the derivative with respect to C, express C as a function of A and B and compute the new form of the cost. Put the resulting cost under a form which is suitable to apply the known result that computes the minimum value of the ratio minX XX||ΩXX for a symmetric matrix Ω. c) Repeat questions a) and b) for a circular manifold with the circle defined by the coordinates of its center (A,B) and its radius C > 0. For question c) you need to compute first the shortest distance of a point from the circle as a function of A,B,C. Then define a cost by considering the sum of squares of the distances of the points from the circle. Next you must express C in terms of A,B by taking the derivative with respect to C and equating it to 0. Finally you must derive the new cost function that now depends only on A,B. d) Write the steepest descent algorithm for A,B that minimize this final cost function.