How to take the subgradient of matrix inside of squared Euclidean norm? I have following expression, I would like to take the sub-gradient of it with respect to $Z$.
Would someone help me with this ?
$$\|Y-Z\|^2_2$$
where $Y$ and $Z$ both are $\in\mathbb R^{m \times n}$
 A: Let's answer it this way. For a norm defined on any vector space, we have
$$\partial \|X\| = \left\{ W \,\middle|\, \|W\|_*\leq 1, ~\langle W,X \rangle = \|X\| \right\}$$
where $\|\cdot\|_*$ is the dual norm (and Y is drawn from the dual vector space). For the matrix norm $\|X\|_2=\sigma_\max(X)$, we have $\|W\|_*=\sum_i \sigma_i(w)$, so
$$\partial \|X\|_2 = \left\{ Y \,\middle|\, \sum_i \sigma_i(Y) \leq 1, ~\langle W,X \rangle = \sigma_\max(X) \right\}$$
I'm going to skip the proof here but I believe we have this:
$$\partial \|X\|_2 = \mathop{\textrm{Conv}} \left\{ uv^T \,\middle|\, \|u\|_2=\|v\|_2=1, ~ u^TXv = \sigma_\max(X) \right\}$$
where $\mathop{\textrm{Conv}}$ denotes the convex hull.
The subdifferential of the squared norm follows simply:
$$\partial \|X\|^2 =2  \|X\| \cdot \partial \|X\|$$
This is true for any norm, not just the matrix norm.
Now, as for subdifferentiability vs. differentiability. As a convex function defined on all of $\mathbb{R}^{m\times n}$, the subdifferential exists everywhere. But a convex function it is differentiable only where the cardinality of that subdifferential is 1. For the non-squared norm, I believe that is everywhere $\sigma_1(X)>\sigma_2(X)$; that is, where the maximum singular value has a multiplicity of one. At those points, there is only one dyad $uv^T$ that obtains $u^TXv=\sigma_\max(X)$.
On the other hand, the squared norm is differentiable at one other location: the origin, because the subdifferential is $\{0\}$ there.
Now, you asked about $\|Y-Z\|^2=\|Z-Y\|^2$, not just $\|X\|^2$, but that's simple enough:
$$\partial \|Z-Y\|^2 = 2\|Z-Y\|\cdot \partial \|Z-Y\| =2\|Z-Y\|\cdot\left.\partial\|X\|\right|_{X=Z-Y}$$
$$\partial \|Z-Y\|^2 = 2\|Z-Y\|\mathop{\textrm{Conv}}\left\{uv^T\,\middle|\,\|u\|_2=\|v\|_2=1, ~ u^T(Z-Y)v^T=1\right\}$$
