Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: zz-x2580
COMP8535-2022-S1 Homework #4
General Instruction
Full marks for this homework = 100 points.
Estimated time needed to complete this homework is about 8–10 hours time including
self-study.
Please work on 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.
Make sure that you submit all your solutions in a single PDF file, with filename of
uxxxxxxx-hw-3.pdf (note: replace the uxxxxxxx with your own Uni-ID), and submit the
single PDF file to Wattle before the deadline. It is also a good idea to include a cover page
with your Full-Name and Uni-ID in your submission, which will help the Tutor to identify
your submission.
Your solution must be typed. ( No hand-written submission will be accepted, or results
in a zero mark).
Academic Integrity: All your homework must be completed individually and indepen-
dently. You must comply with the University Policy on Academic Integrity. ANU is using
TurnItIn to detect and report submission duplications. Plagiarism will lead to severe conse-
quences, including academic misconduct.
You are allowed to discuss with other students about those problems. Your solutions
may share ideas with others. However, you must solve the problems by yourself, i.e., your
final submission must be your own work, and it must be written in your own language.
HW4 Problems
1. (20 points) (Kurtosis of a sum) Recall that the kurtosis of a random variable X with
zero mean is
kurt(X) = E
[
X4
]− 3 (E [X2])2 (1)
One way to understand the importance of the factor 3 in Equation 1 is to consider a
sum of two independent random variables. Let X and Y be two independent random
variables with zero mean and unit variance, i.e.
E[X] = 0 E [X2] = 1
E[Y ] = 0 E [Y 2] = 1
1
Show that
kurt(X + Y ) = kurt(X) + kurt(Y )
Can you see the importance of the factor 3 in the above fomula ? Hint: Use the Binomial
formula and the linearity of expectation.
2. (20 points) (Under-constrained equations)
Solve the following minimization problems by hands. Please list your key steps. Please
also verify that your solutions are correct by drawing the graphs for the problems.
Let Φ =
[
4 1
]
and y = 1.
(a) (10 points) Solve min
x∈R2
‖x‖2 subject to Φx = y.
(b) (10 points) Solve min
x∈R2
‖x‖1 subject to Φx = y.
3. (20 points) (Sparsity) Assume we have:
Φ =
[
1 1/
√
2 0 −1/√2
0 1/
√
2 1 1/
√
2
]
(a) (10 points) Suppose that for some fixed b ∈ R2, the equation Φx = b has a 1-
sparse solution. Show this solution is unique, and so we can recover any 1-sparse
solution x ∈ R4.
(b) (10 points) Let b a vector in R2. Show that the equation Φx = b can have as many
as six distinct 2-sparse solutions.
4. (30 points) (Sparsity) Consider the underdetermined linear equation Φx = b, where Φ
is the matrix in Question 3, x ∈ R4, and b = [0, 3]t (here the superscript t denotes the
transpose).
(a) (10 points) Verify that the vector x = [0, 0, 3, 0]t is a 1-sparse solution.
(b) (10 points) Find the minimum norm solution to ΦX = b using the `
2 norm. (Sug-
gestion: Solve Φx = b for x1 and x3 in terms of x2 and x4, then express ‖x‖22 in
terms of just x2 and x4 and minimize in these two variables.) What’s the sparsity
of this solution?
(c) (10 points) Find the minimum norm solution to Φx = b using the `1 norm ‖x‖1
and the same approach as part (b). Although ‖x‖1 is not differentiable, it is easy
to find the minimum graphically after you’ve expressed ‖x‖1 as a function of two
variables, by plotting ‖x‖1 as a function of x2 and x4.
5. (10 points) (OMP)
(a) (5 points) List the key steps of the OMP algorithm.
(b) (5 points) Does the OMP algorithm achieve global optimality? If not, does OMP
always achieve local optimality? Explain why.
END of all HW4 questions.
