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.
 A: 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$}. 
A: $\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
\begin{equation}
f(x+y)\geq f(x)+y^*s.
\end{equation}
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
\begin{equation}
\partial \|x\|_1=\{s~\big|~ s_i=sign(x_i)~\forall~i\in S,~\|s\|_{\infty}\leq 1\}
\end{equation}
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
