How can I find the derivative of $L_1$ norm?

Question

There is a related question here Link, but the answer does not give any proof.

I use the following definition of the derivative:

Let $E,F$ be linear normed spaces. $f:E\to F$ is a mapping. The derivative $Df_a$ at point $a$ (if it exists) is defined to be the linear mapping $Df_a\in L(E,F)$ such that $$\forall h\in E,f(a+h)=f(a)+Df_a(h)+r_a(h) $$ where $r(h)=o(\|h\|)$.

I am NOT having problems evaluating the derivative of $\|\cdot\|_1$. I already know the answer. But how can I fit the answer rigorously into the definition above? See here for the formula of the derivative.

How can I prove the formula on Wikipedia $\partial\|x\|/\partial x=\text{sign}(x)$ satisfies the above definitions? I really don't know how to connect something very abstract (linear normed space) to some special functions $\text{sign}(x)$.

Answer 1

For simplicity, consider the two-dimensional case. Let $x=(x_0,y_0),\ h=(h,k)$ such that $\|h\|=|h|+|k|=1.$ We want a linear transformation $D:\mathbb R^2\to \mathbb R$ such that

$\lim_{t\to 0}\frac{|x_0+th|+|y_0+tk|-|x_0|-|y_0|-D(th,tk))}{t(|h|+|k|)}=\lim_{t\to 0}\frac{|x_0+th|+|y_0+tk|-|x_0|-|y_0|-D(th,tk))}{t}=0.$

If $x_0,y_0\neq 0$ then taking $D(th,tk)=t(\text{sgn}\ x_0+\text{sgn}\ y_0)$ works becauae

$\lim_{t\to 0}\frac{|x_0+th|-|x_0|}{t}=\text{sgn}\ x_0$ and $\lim_{t\to 0}\frac{|y_0+tk|-|y_0|}{t}=\text{sgn}\ y_0.$

If either $x_0$ or $y_0$ is zero, say $x_0$, then we have

$\lim_{t\to 0}\frac{|th|+|y_0+tk|-|y_0|-D(th,tk))}{t}=0.$

If this holds, then in particular, it must hold for $k=0.$ Then, $h=1$ and then

$\lim_{t\to 0}\frac{|t|-D(0,tk))}{t}=0.$ Taking the limit from the right gives $D(0,k)=1$ and from the left $D(0,k)=-1$ so the derivative does not exist in this case.

The extension to $\mathbb R^n$ follows the same pattern: if any coordinate of a given point $x$ is zero, then the derivative does not exist. Otherwise, it is equal to the sum of the signum functions of the coordinates.

Answer 2

The $l_1$ norm is differentiable at $x$ iff $x_k \neq 0$ for all $k$.

Note that if $x \neq 0$ then $|x+h| = |x| + ( \operatorname{sgn} x )h$ for all $|h| < |x|$.

It follows that if $\min_k |x_k| >0$, then $\|x+h\|_1 = \sum_k |x_k + h_k| = \|x\|_1+\sum_k ( \operatorname{sgn} x_k )h_k = \|x_1\|_1 + g^T h$, for all $\|h\|_\infty < \min_k |x_k|$ (with $g_k = \operatorname{sgn} x_k$).

If any $x_{k} = 0$, then the norm is not differentiable, as we have $\|x+t e_{k}\|_1 = \|x\|_1 + |t|$, which is not differentiable.