03 09 2024 E TS

Page 1

Course: Numerical Analysis for Machine Learning Prof. E. Miglio - September 3rd 2024 Duration of the exam: 2.5 hours. Exercise 1 (13 points) Load the matrixL = [lij] contained in the filematrix_L.txt. This matrix is the Euclidean distance matrix of a set of 50 pointspi where i = 1, . . . ,50. Let us call P the unknown 50 × 3 matrix containing the coordinates of the 50 points (thei-th row is the i-th point). 1. (1 point) Check that the origin of the coordinate system is placed in the centroid of the set of points. 2. (2 points) Use the following relation to compute the elements ofP T P: pT i pj = − 1 2   l2 ij − 1 N NX j=1 l2 ij − 1 N NX i=1 l2 ij + 1 N NX i=1 NX j=1 l2 ij    (1) 3. (4 points) Describe if and how the eigenvalue decomposition can be used to computeP starting from the matrix P T P. 4. (3 points) Compute P using the method described in the previous point. 5. (3 points) Prove relation (1). (Hint: start by noticing thatl2 ij = (pi − pj)T (pi − pj) and then sum only over i, only overj and over bothi and j). Exercise 2 (14 points) Consider the minimization of the 2D quadratic function J(x) = 1 2 (x2 + ϵy2), (2) where x = (x, y) and ϵ > 0. 1. (1 point) How does ϵ impact on the numerical solution of the problem ? 2. (1 point) Let us consider the Gradient Descent (GD) algorithm with variable learning rateτk > 0. Write the recursive relation that describes the method. 3. (2 points) In the convex case, ifJ is of classC 2, in order to have convergence, we must have 0 < τ k < 2 supx ∥HJ (x)∥ , (3) where HJ (x) is the Hessian ofJ. Compute the maximum value ofτk to have convergence. 4. (2 points) Implement the GD method with constant step size. Assumeη = 4 and x0 = (0.9, 0.3). Display the iterations on the contour figure for different values of the step size.…