# Derivative of $l_1$ norm

I want to compute the following derivative with respect to $n\times1$ vector $\mathbf x$. $$g = \left\lVert \mathbf x - A \mathbf x \right\rVert_1$$

My work:

$$g = \left\lVert \mathbf x - A \mathbf x \right\rVert_1 = \sum_{i=1}^{n} \lvert x_i - (A\mathbf x)_i\rvert = \sum_{i=1}^{n} \lvert x_i - A_i \cdot \mathbf x \rvert = \sum_{i=1}^{n} \lvert x_i - \sum_{j=1}^n a_{ij} x_j\rvert$$ So the $k$th element of derivative is:

$$\frac{\partial g}{\partial x_k} = \frac{\partial }{\partial x_k}\sum_{i=1}^n \lvert x_i - \sum_{j=1}^n a_{ij} x_j\rvert$$ $$= \frac{\partial }{\partial x_k}\bigg(\lvert x_1 - \sum_{j=1}^n a_{1j} x_j\rvert +\cdots+ \lvert x_k - \sum_{j=1}^n a_{kj} x_j\rvert + \cdots\lvert x_n - \sum_{j=1}^n a_{nj} x_j\rvert \bigg)$$ $$=-a_{1k}sign(x_1 - \sum_{j=1}^n a_{1j} x_j)-\cdots+(1-a_{kk})sign(x_k - \sum_{j=1}^n a_{kj} x_j)-\cdots -a_{nk}sign(x_n - \sum_{j=1}^n a_{nj} x_j)$$

And my questions:

• Is this derivation correct?
• How I can represent the answer compactly?
• Can you introduce me a source to master this material?

Thanks.

• I am maybe mistaken, but are you sure this derivative exists? For the case $n=1$ and $A=0$, it is certainly not everywhere... – Clement C. Feb 8 '16 at 14:10
• @ClementC., Please note that, in that case $g=|x|$, and the derivative is $sing(x)$. – user153245 Feb 8 '16 at 14:43
• But no... $x\mapsto \lvert x\rvert$ is not differentiable at $0$. It has a left-derivative and a right-derivative, but that's all. – Clement C. Feb 8 '16 at 15:02
• @ClementC. you're right. But that is what I want. It is common in signal processing. Thanks. – user153245 Feb 8 '16 at 15:16

The differential of the Holder 1-norm (h) of a matrix (Y) is $$dh = {\rm sign}(Y):dY$$ where the sign function is applied element-wise and the colon represents the Frobenius product.
Now substitute $Y=(X-AX)$ \eqalign{ dY &= (I-A)\,dX \cr dh &= {\rm sign}(Y):(I-A)\,dX\cr &= (I-A)^T\,{\rm sign}(Y):dX\cr &= (I-A)^T\,{\rm sign}(X-AX):dX\cr } Since $dh = \big(\frac{\partial h}{\partial X}:dX\big),\,$ the gradient must be \eqalign{ \frac{\partial h}{\partial X} &= (I-A)^T\,{\rm sign}(X-AX) \cr } The result is unchanged if the matrices {$X,Y$} are replaced by vectors {$x,y$}.
$\ell_1$ norm does not have a derivative. It is a nonsmooth function. It has subdifferential which is the set of subgradients. A vector $s$ is a subgradient of a function $f$ at a point $x$ if for all $y$, $s$ satisfies $$f(x+y)\geq f(x)+y^*s.$$ The subdifferential of $\ell_1$ norm is connected to nonzero entries of the vector $x$. In particular, let $sign(x)$ return $+1,-1,0$ for $x_i>0$, $x_i<0$ and $x_i=0$ respectively. Let $S$ be the set of nonzero coordinates of $x$. Then, you can verify that the $\ell_1$ subdifferential $\partial \|x\|_1$ is given by $$\partial \|x\|_1=\{s~\big|~ s_i=sign(x_i)~\forall~i\in S,~\|s\|_{\infty}\leq 1\}$$ that is the vectors $s$ which are equal to $sign(x)$ over $S$ and that have infinity norm (maximum absolute value) less than $1$.
Regarding your question: You should calculate the subdifferential of your function which will involve the nonzero pattern of the vector $(I-A)x$. For more info: https://en.wikipedia.org/wiki/Subderivative