代写COMP/ENGN8535 Homework Assignment #2代做迭代

COMP/ENGN8535 Homework Assignment #2

General Instructions

. Due Date: Friday 5 April 2024, 23:59pm (AEDT).

. Full marks for this homework = 100 points.

.  Please complete as many problems as you can, and answer the questions clearly and concisely. In all your solutions, you need to show the key steps for how you reach your answers. The clarity of your answers may affect the final marks.

.  Submit your answers in a single “pdf” file, with file name U4056789-HW-1.pdf (Note: replace the U4056789 with your own university ID) to Wattle before the deadline.  It is a good idea to also include a cover page with your full name and university ID so that we can identify your submission easily when marking.

. In preparing your PDF submission, both typed and handwritten-and-scanned answers are acceptable, though the former is preferred due to its clarity.

.  Late submissions will not be accepted and incur a Mark of 0.

Academic Integrity: Your homework must be completed individually and independently. You must comply with the University Policy on Academic Integrity. Plagiarism will lead to severe consequences, including academic misconduct. You are allowed to discuss the problems and solution ideas with other students, but your final solutions must be your own work and written in your own words.

Problems

1.  (30 points)  Consider the network of 4 webpages shown below.

(a)  (5 points)  What is the transition matrix P under the Random Surfer Model for this network?

(b)  (5 points)  What is the Google matrix G under the Modified Surfer Model for this network with α = 0.85?

(c)  (10 points)  Using the Google matrix G and α above, rank the webpages with the (full) PageRank algorithm.  Use the power method to approximate the stationary distribution π∞ with two iterations from π0  =l0.25   0.25   0.25   0.25]T .

(d)  (10 points)  How does the ranking of the pages change if the link from Page 3 to Page 1 is removed?

2.  (20 points)  Consider the matrix

(a)  (10 points)  Find the SVD of X .

(b)  (5 points)  What is the best rank-1 approximation of X in the sense of minimising the approximation error under the Frobenius norm?

(c)  (5 points)  What is the approximation error associated with the best rank-1 approx- imation of X under the Frobenius norm?

3.  (30 points)  Consider the following dataset, containing 4 data points:

(a)  (10 points)  What is the first principal component of the data?

(b)  (10 points)  Use PCA to compute lower-dimensional 1-d representations {yj   ∈ R : 1 ≤ j ≤ 4} of the original 2-dimensional points {xj   ∈ R2  : 1 ≤ j ≤ 4}.

(c)  (5 points)  Compute 2-dimensional reconstructions  {x(ˆ)j   ∈ R2   :  1  ≤ j  ≤ 4} of the

data points from the 1-d representations {yj  ∈ R : 1 ≤ j ≤ 4} found in Part (b).

(d)  (5 points)  What is the reconstruction loss ∥x4 − x(ˆ)4 ∥ for the point x4 ?

Hint for Problem 3:  We typically assume that the principle components are normalized (∥u∥ = 1) and that we need to center the data before we perform PCA. It may also help to plot the data before you start this question.

4.  (20 points)  Consider  a data matrix X  ∈ Rd ×n  whose columns are d-dimensional data points that have already had their mean subtracted (the mean vector of the data points in X is µ = 0).   In PCA, the dimensionality of each data point  (d) is reduced to a lower dimension (k ≤ d) through an eigendecomposition of the data covariance matrix C = XX T . Show how singular value decomposition (SVD) of the data matrix X can be used to perform PCA.

Hint for Problem 4:  Recall that the  SVD  of X  is  X  =  UΣVT    where  U,  V,  and Σ all have special properties.  Note  also  that the properties  of transpose imply that XT  = V ΣTUT .  You may need to seek additional material from a textbook or online to answer this question.