The Sub Differential of a Matrix $ {L}_{1} $ Norm

Question

Given a matrix $ A \in \mathbb{R}^{m \times n} $ what is the Sub Differential (Sub Gradient) of

$$ g \left( A \right) = \lambda {\left\| A \right\|}_{1} $$

Answer 1

There is a fair amount of ambiguity in what you're precisely referring to by $\|A\|_1$. I'll break it down into two possible cases.

Case A:

If you mean $\|A\|_1 = \|\text{vec}(A)\|_1$ for any tensor $A$, then WLOG assume $A$ is a vector $v$ of appropriate length.

Now, by definition, $\|v\|_1 := \sum_{j}|v_j|$, and by separability of the sum, we have $\partial \|v\|_1 = \Pi_{j}\partial |v_j| := \partial |v_1| \times \partial|v_2| \times \ldots $.

Thus it suffices to compute $\partial |u|$ for a scalar $u \in \mathbb R$. Now, one can rewrite $|u| = \max \{zu | |z| \le 1\}$, and by the Bertsekas-Danskin Theorem for subdifferentials (Proposition A.22 of the PhD thesis of Bertsekas), we obtain $$ \begin{split} \partial |u| &= \text{conv}\{\nabla_u(zu) \mid z \in [-1, 1], zu = |u|\} = \text{conv}\{z \in [-1, 1] | zu = |u|\} \\ &= \begin{cases}[-1,1], &\mbox{ if }u = 0,\\ \text{sign}(u) := u/|u|,&\mbox{ otherwise.}\end{cases} \end{split} $$

For example, $\partial \|(-1, 0, 0, \pi)\|_1 = \{(-1, x, y, 1) | x, y \in [-1, 1]\}$.

Case B: induced norm

Here, $\|A\|_1 = \|A\|_{1,1} := \max_{\|x\|_1 \le 1} \|Ax\|_1$.

Fact: If $\varphi$ is a norm (on vectors, on matrices, etc.) with dual norm $\varphi^\star : a \mapsto \max_{\varphi(z) \le 1} \langle z, a \rangle$, and unit ball $B_*$ then $$ \partial \varphi(a) = \begin{cases}B_*, &\mbox{ if }a = 0,\\\{z \mid z \in B_*, \langle z, a\rangle = \varphi(a) \}, &\mbox{ otherwise.}\end{cases} $$

This is an elementary consequence of the Bertsekas-Danskin Theorem.

Now, use the fact listed above to get

$$\partial \|A\|_1 = \{B \text{ s.t } \|B\|_\infty \le 1, \langle A, B\rangle_F = \|A\|_1\}. $$

It's possible the above set can be made more explicit, but I didn't yet look into that. Hope this all helps!