$ {L}_{1} $ Norm Differentiablility

Question

I am trying to understand the Least Absolute Deviation algorithm, which basically is

min l1-norm(z) 
subject to z=Ax-b

I want to understand how is the l1-norm not differentiable, we have a function which is a linear function, shouldn't it be once differentiable? How is using l1 norm in the objective function more robust than using l2 morm?

Answer 1

The $l-1$ norm is not differentiable, as it involves absolute values. But luckily you can cast the problem as a linear program. Firstly, you can write

$$ \begin{array}{ll} \min &\sum t_i\\ s.t.&\\ & t_i \geq |z_i|,\quad i=1,\ldots\\ &z = Ax -b,\\ &t_i\geq 0,\quad i=1,\ldots, \end{array} $$

then you just split the absolute value in two linear inequalities:

$$ t_i\geq |z_i| \Rightarrow \left\{ \begin{array}{l} t_i\geq z_i,\\ t_i\geq -z_i. \end{array} \right. $$

Thus summarizing:

$$ \begin{array}{ll} \min &\sum t_i\\ s.t.&\\ &t_i\geq z_i,\\ &t_i\geq -z_i,\\ &z = Ax -b,\\ &t_i\geq 0,\quad i=1,\ldots, \end{array} $$

That would do.