7
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ I am maybe mistaken, but are you sure this derivative exists? For the case $n=1$ and $A=0$, it is certainly not everywhere... $\endgroup$
    – Clement C.
    Feb 8, 2016 at 14:10
  • $\begingroup$ @ClementC., Please note that, in that case $g=|x|$, and the derivative is $sing(x)$. $\endgroup$
    – user153245
    Feb 8, 2016 at 14:43
  • $\begingroup$ 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. $\endgroup$
    – Clement C.
    Feb 8, 2016 at 15:02
  • $\begingroup$ @ClementC. you're right. But that is what I want. It is common in signal processing. Thanks. $\endgroup$
    – user153245
    Feb 8, 2016 at 15:16

2 Answers 2

5
$\begingroup$

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$}.

$\endgroup$
1
  • $\begingroup$ +1, Thanks a lot. But I don't understand the first sentence and equation; Can you introduce some reference to me? $\endgroup$
    – user153245
    Feb 9, 2016 at 5:09
3
$\begingroup$

$\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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .