Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Why l1 Norm is non-differentiable?

  1. Jul 2, 2012 #1
    Can anyone explain Why l1 Norm is non-differentiable in terms of matrix calculus ?
     
  2. jcsd
  3. Jul 3, 2012 #2
    Because L1 norm is based on the absolute value of the difference, and absolute value |x| has a kink at x=0. It is not differentiable at the kink.
     
  4. Jul 3, 2012 #3
    I believe venki1130 may have answered your question, but I am personally not sure. When you say l1 norm, do you mean norm of ##(x_1,\dots,x_n)## is ##|x_1|+\cdots+|x_n|##? That is the first definition I found on wikipedia. I believe this is also called the taxicab metric.

    If I try to recall my education, ##\ell1## and ##L1## are different, the first one is called little ell one. The second I believe is the integral version, ##|f(x)|_1=\int|f(x)|dx##. Compare to ##L2##, ##|f(x)|_2=(\int|f(x)|^2dx)^{1/2}##. Little ell two, is ##|(x_1,\dots,x_n)|_2=\sqrt{x_1^1+\cdots+x_n^2}##. This is sort of a distance as the crow flies, as opposed to how a taxi drives.

    I believe the ##\ell2##-norm has a familiar representation as a matrix, so that is what is confusing me. You asked for a matrix definition of ##\ell1##-norm, when I only know of one for ##\ell2##-norm.

    Further, I could not tell you quickly how to use the matrix representation to show you the norm is not differentiable. I would guess that venki1130 pointed you in the right direction. In general, you could show it is not differentiable along any ##x_i=0## face. It would be easiest to check for ##x_2=\cdots=x_n=0##, and ##x_1## near 0. In other words, show ##|x_1|## is not differentiable near zero. Simply care the slopes from the left and right of 0.
     
  5. Jul 3, 2012 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    I think he means this: http://en.wikipedia.org/wiki/Matrix_norm
     
  6. Jul 4, 2012 #5
    Thank you very much micromass, algebrat and Chogg for your response. I and using L1 norm in the optimization problem.

    for example: For least squares optimization using L2 norm for regularization the equation I am using is

    min ||Ax-b||22 + λ||x||22

    Calculating first derivative(using matrix calculus) and equating it to zero results

    x= At(AtA+λI)-1b

    similarly for L1 norm

    min ||Ax-b||22 + λ||x||1

    But, People always say it is non differentiable. In fact, I understand the concept (intuitively, the unit circle in l1 has the sharp corner where the function doesn't change so there is no derivative for it) but I want to learn step by step using matrix derivatives.

    Again I thank you very much for your help.

    Venki
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook