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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.