21
$\begingroup$

I am a little confused about taking derivatives w.r.t. the norms.

$L_0$-norm: $L_0$ means number of non-zero elements in a vector. Say, I am interested in an $x_i$.

$$\displaystyle\min_{i}(y_i-x_i)^2+c\|x_i \|_{0}$$ The answer depends on $x_i=0$ or not?
My work: take the norm of $x_i$, which is a constant, then, derivative, so it's 0.

$L_1$-norm: Manhattan distance. What should I do? $$\displaystyle\min_{i}(y_i-x_i)^2+c\|x_i \|_{1}$$

$L_2$-norm:Euclidean distance. What should I do?
$$\displaystyle\min_{i}(y_i-x_i)^2+c\|x_i \|_{2}$$

$\endgroup$

2 Answers 2

16
$\begingroup$

I'm going to assume that you're talking about partial derivatives and gradients. All of the norm functions that you stated are non-differentiable somewhere:

  • [$L_0$] This is zero (as you pointed out), but only in places where it isn't interesting. Where it is interesting it's not differentiable (it has jump discontinuities).
  • [$L_1$] This norm is not differentiable with respect to a coordinate where that coordinate is zero. Elsewhere, the partial derivatives are just constants, $\pm 1$ depending on the quadrant.
  • [$L_2$] Usually people use the 2-norm squared so that it's differentiable even at zero. The gradient of $\|x\|_2^2$ is $2x$, but without the square it's $x/\|x\|$ (i.e. it just points away from zero). The problem is that it's not differentiable at zero.

If you're trying to do gradient descent with these formulations, the only one that will really work is the squared $L_2$ norm, because that's the only one that's differentiable everywhere.

$\endgroup$
9
  • $\begingroup$ I have no background in gradients. You are correct, the answer for L0-norm is discontinuous. And what is a coordinate? Can you point to me a link on all these? $\endgroup$
    – user13985
    May 14, 2013 at 4:30
  • $\begingroup$ Gradients; Gradient Descent $\endgroup$ May 14, 2013 at 4:33
  • $\begingroup$ By coordinate I mean one of the individual $x_i$. $\endgroup$ May 14, 2013 at 4:34
  • $\begingroup$ Got you, but I found a similar L1-norm, they solved it. I hope for a similar answer. stats.stackexchange.com/questions/17781/… $\endgroup$
    – user13985
    May 14, 2013 at 4:42
  • $\begingroup$ At this point, I could care less, could you just solve the discontinuous case? As a noob, I want to see how it is done, thanks! $\endgroup$
    – user13985
    May 14, 2013 at 4:54
1
$\begingroup$

For $L_2$ and $L_1$ you can do gradient descent or whatever, the methods are called Ridge Regression and LASSO, respectively.

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