6

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?
Marcus Müller
  • 24,744
  • 4
  • 29
  • 50
user153245
  • 361
  • 1
  • 8

1 Answers1

6

Apart from a sign error, your result looks correct. The term with $(1-a_{1k})$ should have a positive sign. Also note that $\text{sgn}(x)$ as the derivative of $|x|$ is of course only valid for $x\neq 0$. If you take this into account, you can write the derivative in vector/matrix notation if you define $\text{sgn}(\mathbf{a})$ to be a vector with elements $\text{sgn}(a_i)$:

$$\nabla g=(\mathbf{I}-\mathbf{A}^T)\text{sgn}(\mathbf{x}-\mathbf{Ax})$$

where $\mathbf{I}$ is the $n\times n$ identity matrix.

Matt L.
  • 78,282
  • 5
  • 66
  • 149
  • 1
    nice, but I wonder in what way this is really related to DSP ;) – Marcus Müller Feb 08 '16 at 21:41
  • Thanks a lot. I correct the sign error. But in the paper I study, there is $A^T$ instead $A$ in the first parenthesis. – user153245 Feb 09 '16 at 05:16
  • 2
    @Marcus Müller, $L_1$ norm is used as a regularization term in reconstructing signal and image. – user153245 Feb 09 '16 at 05:18
  • @user153245: It should indeed be $A^T$; I corrected it. – Matt L. Feb 09 '16 at 07:37
  • @MarcusMüller : It certainly looks like a valid signal processing question to me. More about the tools used, but still very valid. – Peter K. Feb 09 '16 at 20:15
  • 1
    @PeterK., user153245: That question came out of interest about the background of the original question; I'm very well aware the needs to find a derivate of some norm, metric etc, but usually, when questions like OP's are asked, there's a whole interesting problem to solve behind that :) – Marcus Müller Feb 09 '16 at 20:48
  • Ah! Point taken! @MarcusMüller I agree! Some of the most interesting real-world problems lead to interesting maths... And both are worthwhile explaining --- context may help color the answer. – Peter K. Feb 10 '16 at 11:12