Problem 5 [30 points] Consider a graph on 2n vertices which is the union of two complete graphs, each on n vertices. In other words, there exists a subset S C [2n] := {1,...,2n} of size |S| =n such that for any vertices i,j) [2n], we have i ~ j (i is connected to j) if either 1,79 S or t,j7 S*. Let Ag denote the adjacency matrix of this graph (with ones on the diagonal). Assume that we observe a noisy version of As., where S* is unknown and each edge (including self-edges and non-edges) is flipped independently with probability 1/4. Let Y denote the adjacency matrix of this noisy graph. The goal of this problem is to estimate Ag. using the mean squared error: 1 (2n)? JA a As: I : MSE(A) = 5.1 [5pts] Find a 0 such that E[Y] = alla, + Avuv', where Ib, denotes the all-ones matrix of size 2n x 2n, and |v|2 = 1. Compute a, A and v. 5.2 [5pts] Propose an estimator of A of As- based on singular value thresholding and prove that MSE(A)