Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
EE 290 Mathematics of Data Science - Homework 1
Rules:
1. This assignment is due at 11:59pm on Tuesday, October 1. No late submissions accepted.
2. Please submit the homework solution online via Gradescope. The entry code for gradescope is M4DNZ2. Hand-writing homework is allowed but required to convert to image / pdf file first. You can use any programming language. Submit your code as part of the homework. Tables and figures are preferred to help to illustrate your results. There are several subquestions for each question. Make sure that it is easy for readers to figure out which subquestions you are answering.
Problem A) Perturbation bound analysis.
Let A, E be positive definite matrices. Suppose that A = LLT and A+E = (L+G)(L+G)Tare Cholesky factorizations of A and A + E, respectively. In this problem, we investigate the perturbation bound for Cholesky decomposition.
1. Prove that for any two matrices X ∈ Rn×d, Y ∈ Rd×k, ||XY||F≤ ||X||2||Y||F. Use this inequality to justify that ||A||F≥ ||L−1||2−1 ||L||F and||L||F||L−1||2≤ ||A||F||A−1||2
2. Use the above inequality to show that
||E||F/||A||2 /(1 + p 1 + ||E||F/||A||2) ≤ ||G||F/||L||2
and
≤ ||G||F/||L||F ,
where κ(A) = ||A||F ||A−1||2.
Problem B) Orthogonally invariant norms.
Let m, n be given positive integers and q = min(m, n). For any A ∈ R m×n , let A = V ΣW>, where V ∈ R m×m and W ∈ R n×n are orthogonal and Σ ∈ R m×n is a non-negative diagonal matrix whose diagonal entries are the nonincreasingly ordered singular values of A: σ1(A) ≥ · · · ≥ σq(A). Let s(A) = [σ1(A), · · · , σq(A)]>.
We say a norm k · k is orthogonally invariant if kAk = kV ΣW>k = kΣk for any orthogonal matrix V, W. We say a function g : R q → R + is a symmetric gauge function if it is an absolute vector norm such that g(x) = g(P x) for every x ∈ R q and every permutation matrix P ∈ R q×q . In this question, we show that the equivalence between orthogonally invariant norms and symmetric gauge functions.
1. Show that any orthogonally invariant norm can be written as a symmetric gauge function of s(A). Let k · k be an orthogonally invariant norm on R m×n . Then for any A ∈ R m×n , we have kAk = g(s(A)) for some symmetric gauge function g : R q → R +.
2. Show that any symmetric gauge function of s(A) is an orthogonally invariant norm. Let g be a symmetric gauge function on R q . The function k · k : R m×n → R + defined by kAk = g(s(A)) is a orthogonally invariant norm on R m×n . (Hint: you need to show first this definition is a valid norm, and then the norm is orthogonally invariant.)
Problem C) Maximum clique. Read Section 1.2 of http://www.stat.yale.edu/˜yw562/ teaching/684/lec01.pdf and prove the following generalized result. Let ωn denote the clique number (i.e. the size of the maximum clique) in the Erdos-R ˝ enyi graph ´ G(n, p). Show that as n → ∞, ωn log(n) converges in probability to a constant. Find the limit.
Problem D) Weyl’s inequality.
1. Prove the following Courant-Fischer’s variational representation of eigenvalues: Let A be an n×n real symmetric matrix, with eigenvalues λ1(A) ≥ · · · ≥ λn(A). Then for each i ∈ [n], λi(A) = sup dim(V )=i inf v∈V :kvk2=1 v >Av. (Hint: use the eigenvalue decomposition of A.)
2. Prove that: if A, B are both real symmetric, then |λi(A) − λi(B)| ≤ kA − Bk2. Problem E) Experiments for planted clique. Write code to implement the planted clique detection algorithm (Algorithm 1) in Lecture 3. First generate an Erdos-R ˝ enyi graph ´ G(n, 1/2), and then select uniformly at random k points and make it a clique. Conduct experiment under different scenarios as below.
1. Run Algorithm 1 without the last cleaning step. Take n, k pairs as
n = 100, k = 10, 20, 30, · · · , 90
n = 200, k = 10, 30, 50, · · · , 190
n = 500, k = 10, 30, 50, · · · , 450.
For each n, k pair, repeat the process m = 1000 times. Denote Kj as the true clique for j-th experiment, and Kˆ j as the output of the algorithm. Let ebit = 1 m Pm j=1 |Kj/Kˆ j | Kj , eblock = 1 m Pm j=1 1(Kj 6= Kˆ j ). Plot how ebit and eblock changes as k increases. Analyze your results.
2. Run Algorithm 1 with the last cleaning step. Repeat the above process and compare the algorithms with cleaning and without cleaning.
3. Run Algorithm 2 for n = 500, k = 10, 20, 30, · · · , 100. Compare the results with Algorithm 1. Record what s works the best for each (n, k) pair. Analyze your results.