7

As the title, is the euclidean norm differentiable at $0$? I tried that prove by contradiction and apply the definition but can't really get a contradiction. Any hints?

Royi
  • 8,711
Johnny
  • 231
  • 6
    Hint: If it were in $\mathbb R^n$ then show that $|x|$ would be differentiable at $x=0$ in $\mathbb R$. – Thomas Andrews Feb 21 '13 at 16:53
  • A side comment on L0. Optimization of the L0 norm is an NP-hard problem. See this. E. Amaldi and V. Kann. On the approximability of minimizing non zero variables or unsatisfied relations in linear systems. Theoretical Computer Science, 209:237–260, 1998. – Nivedita Rethnakar Apr 15 '21 at 05:24

3 Answers3

10

It isn't. The definition of differentiable is that the derivative of the norm function (let me call it $N$) at zero would be a vector $v$ such that $$\lim_{x\to 0} \frac{N(x)-x \cdot v}{\left\|x\right\|}=0.$$

(Here, $\left\|x\right\|$ is also the Euclidean norm of $x$, but it plays a different role from $N$, so I used different notation.)

If you let $x\to 0$ along vectors orthogonal to $v$, the limit is $1$, a contradiction.

Omar Antolín-Camarena
  • 5,492
5

Assume, for a contradiction, that $f(x)=\|x\|$ is differentiable at $0$, ie $$ f(x)=f(0)+df(0)x+\|x\|\epsilon(x) $$ for all $x\in\mathbb{R}^n$ with $\lim_{\|x\|\rightarrow 0}\epsilon(x)=0$.

Now fix $x$ such that $\|x\|>0$.

Then for all $t\in\mathbb{R}$ $$ |t|\|x\|=f(tx)=tdf(0)x+|t|\|x\|\epsilon(tx) $$ so $$ |t|=t\frac{df(0)x}{\|x\|}+|t|\epsilon(tx) $$ which proves that $$ t\longmapsto |t| $$ is differentiable at $0$ with derivative $df(0)x/\|x\|$.

As is well-known, the latter is not differentiable at $0$. Contradiction.

Note: this proof works in general for the norm of a normed vector space. No need to restrict to inner product spaces.

Julien
  • 44,791
2

Another approach, that seems to work:

$g(x)=(\underbrace{1,0,...,0}_\text{n})^T x$ is linear and therefore differentiable (at $0$).

Then $|x_1| = (f \circ g)(x)$

Suppose for a contradiction, that $f$ is differentiable at $0$. Then by the chain rule $|x_1|$ is differentiable at $0$. However, the first partial derivative $\frac{\partial}{\partial x_1} |x_1|$ does not exists. So $|x_1|$ not differentiable. Contradiction.

Alex
  • 2,354