Description
1. Consider the following non-smooth function on the real line:
f(x) = max
!
(x + 1)
2
,(x − 3)
2
”
Describe the subdifferential ∂f(x) at every point x ∈ R.
2. Prove or disprove: the subdifferential ∂f(x) of a convex function is a convex set at
every x ∈ R.
3. Recall the subdifferential for the nuclear norm for an n1 × n2 matrix X.
∂ $X$ ” = #
UV T + W : UW = 0,WV = 0, $W$ ≤ 1
$
In the expression above, X has rank r and its SVD is X = UΣV T , where U is n1 × r, Σ
is r × r and V is n2 × r. Recall that
x+ = proxt!cdot!!(X)
= arg min
Z
%
$Z$ ” +
1
2t
$Z − Z$ F2
&
if and only if
X − X+ ∈ t∂
‘
‘X+’
‘ ”
Show that we can compute the prox operator above by singular value thresholding:
X+ = UΣ+V T ,where+[i, i] = max(σit, 0).
