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 '16 at 14:10
  • $\begingroup$ @ClementC., Please note that, in that case $g=|x|$, and the derivative is $sing(x)$. $\endgroup$ – user153245 Feb 8 '16 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 '16 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 '16 at 15:16
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 '16 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.