6
$\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?
$\endgroup$

1 Answer 1

6
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ nice, but I wonder in what way this is really related to DSP ;) $\endgroup$ Feb 8, 2016 at 21:41
  • $\begingroup$ Thanks a lot. I correct the sign error. But in the paper I study, there is $A^T$ instead $A$ in the first parenthesis. $\endgroup$
    – user153245
    Feb 9, 2016 at 5:16
  • 2
    $\begingroup$ @Marcus Müller, $L_1$ norm is used as a regularization term in reconstructing signal and image. $\endgroup$
    – user153245
    Feb 9, 2016 at 5:18
  • $\begingroup$ @user153245: It should indeed be $A^T$; I corrected it. $\endgroup$
    – Matt L.
    Feb 9, 2016 at 7:37
  • 1
    $\begingroup$ @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 :) $\endgroup$ Feb 9, 2016 at 20:48

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.